Spider と pendant edgeを付けた道のbroadcast domination

宮﨑史郎

目次
• spiderとは• spiderのbroadcast domination• pendant edge とは• pendant edge が ついた木のbroadcast domination

研究動機• 一般の木の broadcast domination number を与える式は知られていない→特別な木についての broadcast domination number を求めたい。

先行研究• 特別な木である道のbroadcast domination number を求める公式は存在する※頂点数 n の道Pのbroadcast domination numbernγ b (Pn ) =  
3
1

1

（Erwin 2004）
11

1

1

11

研究内容
1. spider の broadcast domination number を決定した
2. 道にpendant edge を付け加えた時のbroadcast domination number の変化を調べたspiderとは• 枝分かれが1点しか存在しない木

x

𝑙𝑙3 = 4𝑙𝑙2 = 6𝑙𝑙1 = 9𝑎𝑎2 = 2𝑎𝑎1 = 3𝑎𝑎3 = 1

最長の道から順に道の長さを𝑙𝑙1 , 𝑙𝑙2 ,… とする。
𝑙𝑙1 の本数を𝑎𝑎1 , 𝑙𝑙2 の本数を𝑎𝑎2 ,...とする。

このようなグラフのxに値を割り振り、broadcast dominationを考えていくこととする。

研究結果spiderについて
定理 spider の broadcast domination number は、𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3 と その本数の 𝑎𝑎1, 𝑎𝑎2 のみに依存する。

（𝑙𝑙4, 𝑙𝑙5, ・・・ が存在してもbroadcast domination number に影響しない）

枝分かれする枝の長さの種類が以下の場合を考える。
(i) 𝑙𝑙1 のみ (ii) 𝑙𝑙1, 𝑙𝑙2 (iii) 𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3

研究結果spiderについて
定理 spider の broadcast domination number は、𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3 と その本数の 𝑎𝑎1, 𝑎𝑎2 のみに依存する。

（𝑙𝑙4, 𝑙𝑙5, ・・・ が存在してもbroadcast domination number に影響しない）

枝分かれする枝の長さの種類が以下の場合を考える。
(i) 𝑙𝑙1 のみ (ii) 𝑙𝑙1, 𝑙𝑙2 (iii) 𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3

結果(i)x𝑙𝑙1

𝑙𝑙1......

𝑎𝑎1

定理 1.1𝑙𝑙1 のみのspiderの broadcast domination number は𝛾𝛾𝑏𝑏 𝑆𝑆 = 𝑙𝑙1（証明） （𝑎𝑎1 ≧ 3 に注意）
xに割り振る値として考えられる最大の値は𝑙𝑙1xに𝑙𝑙1 を割り振ったとき 𝛾𝛾𝑏𝑏 𝑆𝑆 = 𝑙𝑙1

結果(i)x𝑙𝑙1

𝑙𝑙1 -1......

𝑎𝑎1

定理 1.1𝑙𝑙1 のみのspiderの broadcast domination number は
γb S = l1（証明） （𝑎𝑎1 ≧ 3 に注意）
xに割り振る値として考えられる最大の値は𝑙𝑙1
𝑙𝑙1 − 1xに𝑙𝑙1 を割り振ったとき 𝛾𝛾𝑏𝑏 𝑆𝑆 = 𝑙𝑙1
これよりも小さい値である (𝑙𝑙1 - 1) を割り振ったとき、
𝛾𝛾𝑏𝑏 𝑆𝑆 = 𝑙𝑙1 − 1 + 𝑎𝑎1≥ 𝑙𝑙1
以下帰納的に証明を続けることでbroadcast domination numberが𝑙𝑙1 より小さくならないことは示される。

研究結果spiderについて
定理 spider の broadcast domination number は、
𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3 と その本数の 𝑎𝑎1, 𝑎𝑎2 のみに依存する。

（𝑙𝑙4, 𝑙𝑙5, ・・・ が存在してもbroadcast domination number に影響しない）

枝分かれする枝の長さの種類が以下の場合を考える。
(i) 𝑙𝑙1 のみ (ii) 𝑙𝑙1, 𝑙𝑙2 (iii) 𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3

結果(ii)定理 1.2
𝑙𝑙1, 𝑙𝑙2 のみのspiderの broadcast domination は......

以下の配置で与えられる。
（１）𝑎𝑎1 = 1 かつ 𝑎𝑎2 > 1 のとき→ x に 𝑙𝑙2 を割り振り、残った部分には道のbroadcast domination の考え方を適用する。
（２）𝑎𝑎1 = 2 のとき→𝑙𝑙1 の値によってxに 𝑙𝑙2 もしくは 𝑙𝑙2 + 1 のどちらかを割り振り、残った部分には道のbroadcastdomination の考え方を適用する。
（３）𝑎𝑎1 ≧ 3 のとき→xに𝑙𝑙1 を割り振る。

x(ii)（１） 𝑎𝑎1 = 1 かつ 𝑎𝑎2 > 1 のとき• xに𝑙𝑙2 を割り振ったとき→このグラフは𝑙𝑙1 −𝑙𝑙23

𝑙𝑙2𝑙𝑙1で支配される。

•𝑙𝑙1 − 𝑙𝑙2

× 𝑎𝑎1 + 𝑙𝑙2

xに 𝑙𝑙2 − 3 を割り振ったとき=

𝑙𝑙1 −(𝑙𝑙2 −3)3
𝑙𝑙1 −𝑙𝑙2
3× 𝑎𝑎1 +𝑙𝑙2 −(𝑙𝑙2 −3)
3× 𝑎𝑎2 + 𝑙𝑙2 − 3

× 𝑎𝑎1 + 𝑎𝑎1 + 𝑎𝑎2 + 𝑙𝑙2 − 3

𝑙𝑙2 と 𝑙𝑙2 - 3 の割り振りの比較

xに 𝑙𝑙2 - 3を割り振ったとき
𝑙𝑙1 −𝑙𝑙2
3

× 𝑎𝑎1 + 𝑎𝑎1 + 𝑎𝑎2 + 𝑙𝑙2 − 3𝑙𝑙1 −𝑙𝑙2
3× 𝑎𝑎1 + 𝑎𝑎1 + 𝑎𝑎2 + 𝑙𝑙2 − 3

xに𝑙𝑙2 を割り振ったとき
𝑙𝑙1 −𝑙𝑙2
3× 𝑎𝑎1 + 𝑙𝑙2

𝑙𝑙1 −𝑙𝑙2
3× 𝑎𝑎1 + 𝑙𝑙2

𝑙𝑙2 -3を割り振ったほうがbroadcast domination number が小さくなるとすると、

𝑎𝑎1 + 𝑎𝑎2<<3

𝑎𝑎1 = 1, 𝑎𝑎2 > 1 より矛盾
→𝑙𝑙2 を割り振ったほうがbroadcast domination number は小さい
同様に𝑙𝑙2 + 3と比較しても𝑙𝑙2 を割り振るほうが良い

(ii) (2) 𝑎𝑎1 = 2 のとき• 𝑎𝑎1 = 2 のとき𝑎𝑎2 の値にかかわらず表の条件に対応する値がxに割り振るとき𝛾𝛾𝑏𝑏 (𝑇𝑇)が最小になる
𝑙𝑙2 ＼𝑙𝑙1

𝑙𝑙1 ≡0 (mod3)

𝑙𝑙1 ≡1 (mod3)

𝑙𝑙1 ≡2 (mod3)

𝑙𝑙2 ≡0 (mod3)

𝑙𝑙2

𝑙𝑙2 + 1𝑙𝑙2 または𝑙𝑙2 + 2

𝑙𝑙2 ≡1 (mod3)

𝑙𝑙2 または𝑙𝑙2 + 2

𝑙𝑙2

𝑙𝑙2 + 1𝑙𝑙2 ≡2 (mod3)

𝑙𝑙2 + 1𝑙𝑙2 または𝑙𝑙2 + 2

𝑙𝑙2

（ii）(3) 𝑎𝑎1 ≥ 3のとき

• 𝑎𝑎2 の値にかかわらず𝑙𝑙1 を割り振るときが最小となる。
証明
𝑙𝑙1 でspider全体を支配できるため𝑙𝑙1 より大きい値は考慮しない。
𝑙𝑙1 - 𝑘𝑘 (𝑘𝑘 = 1,2,…, 𝑙𝑙1 -1)を割り振るとき、
𝛾𝛾𝑏𝑏 𝑆𝑆 = 𝑙𝑙1 − 𝑘𝑘 += 𝑙𝑙1 − 𝑘𝑘 +≥ 𝑙𝑙1

𝑙𝑙1 − 𝑙𝑙1 −𝑘𝑘
3𝑘𝑘𝑎𝑎
3 1× 𝑎𝑎1

研究結果spiderについて
定理 spider の broadcast domination number は、
𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3 と その本数の 𝑎𝑎1, 𝑎𝑎2 のみに依存する。

（𝑙𝑙4, 𝑙𝑙5, ・・・ が存在してもbroadcast domination number に影響しない）

枝分かれする枝の長さの種類が以下の場合を考える。
(i) 𝑙𝑙1 のみ (ii) 𝑙𝑙1, 𝑙𝑙2 (iii) 𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3

(iii) 𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3定理1.3𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3 のみのspiderの broadcast domination は以下の配置で与えられる。
① 𝑎𝑎1 = 1, 𝑎𝑎2 = 1のとき
② 𝑎𝑎1 = 1, 𝑎𝑎2 ≥ 2 のとき③ 𝑎𝑎1 ≥ 2 のとき※いずれのパターンも 𝑎𝑎3 の値によらない。

1.3 ①𝑎𝑎1 = 1, 𝑎𝑎2 = 1のとき

𝑎𝑎3 の値に関わらず
または、𝑙𝑙1 ≡ 0 かつ 𝑙𝑙2 ≡ 0 かつ 𝑙𝑙3 ≡ 2 (mod3)
または、𝑙𝑙1 ≡ 1 かつ 𝑙𝑙2 ≡ 1 かつ 𝑙𝑙3 ≡ 0 (mod3)
または、𝑙𝑙1 ≡ 2 かつ 𝑙𝑙2 ≡ 2 かつ 𝑙𝑙3 ≡ 1 (mod3)

この条件が満たされるとき、xには 𝑙𝑙3 +1 を
それ以外では 𝑙𝑙3 を割り振ればよい….

定理1.3 ②,③②𝑎𝑎1 = 1, 𝑎𝑎2 ≥ 2 のとき②,③ともに 𝑙𝑙3 の本数の値によらない→ xに𝑙𝑙2 を割り振る③𝑎𝑎1 ≥ 2 のとき→ 定理1.2の値の振り方を適用する。
定理 1.2
𝑙𝑙1, 𝑙𝑙2のみのspiderの broadcast domination は以下の配置で与えられる。
（１）𝑎𝑎1 = 1 かつ 𝑎𝑎2 > 1 のとき→ x に 𝑙𝑙2 を割り振り、残った部分には道の broadcast domination の考え方を適用する。
（２）𝑎𝑎1 = 2 のとき→𝑙𝑙1 の値によってxに 𝑙𝑙2 もしくは 𝑙𝑙2 + 1 のどちらかを割り振り、残った部分には道のbroadcast
domination の考え方を適用する。
（３）𝑎𝑎1 ≧ 3 のとき→xに𝑙𝑙1 を割り振る。

𝑎𝑎1 = 2 のときの対応表

Xに𝑙𝑙4 を割り振る

𝑙𝑙4X

𝑙𝑙1 -𝑙𝑙4

𝑙𝑙2 -𝑙𝑙4𝑎𝑎1

𝛾𝛾𝑏𝑏 𝑆𝑆 = 𝑙𝑙4 +𝑎𝑎2

𝑙𝑙3 -𝑙𝑙4

𝑙𝑙4, 𝑙𝑙5, …が存在する場合

Xに𝑙𝑙3 を割り振る
X𝑙𝑙4

𝑎𝑎4

𝑎𝑎3

𝑙𝑙1 − 𝑙𝑙4
𝑙𝑙2 − 𝑙𝑙4
𝑙𝑙3 − 𝑙𝑙4
× 𝑎𝑎1 +× 𝑎𝑎2 +× 𝑎𝑎3
333𝑙𝑙1 −𝑙𝑙43≥

𝑙𝑙1 −𝑙𝑙3
3,𝑙𝑙2 −𝑙𝑙43≥

𝑙𝑙1 -𝑙𝑙3

𝑙𝑙2 -𝑙𝑙3

𝑎𝑎1𝑎𝑎2

𝑙𝑙3

𝑎𝑎3

𝑎𝑎4

𝑙𝑙1 − 𝑙𝑙3
𝑙𝑙2 − 𝑙𝑙3
× 𝑎𝑎1 +× 𝑎𝑎2
𝛾𝛾𝑏𝑏 𝑆𝑆 = 𝑙𝑙3 +33

𝑙𝑙2 −𝑙𝑙3であるから、𝑙𝑙4 を割り振る方が𝛾𝛾𝑏𝑏 が小さくなることはない。
3𝑙𝑙3

研究結果spiderについて
定理 spider の broadcast domination number は、𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3 と その本数の 𝑎𝑎1, 𝑎𝑎2 のみに依存する。

（𝑙𝑙4, 𝑙𝑙5, ・・・ が存在してもbroadcast domination number に影響しない）

𝑙𝑙4, 𝑙𝑙5, …が存在する場合

よって、𝑙𝑙4, 𝑙𝑙5, …と枝分かれが、どれだけ存在しても、ℓ𝑛𝑛 とℓ𝑛𝑛−1の比較を繰り返し行うと𝑙𝑙3 と𝑙𝑙4 の比較に到達し、𝑙𝑙4 を割り振るよりも𝑙𝑙3 を割り振ったほうが適切であるといった結果が得られる。
以上よりspiderのbroadcast domination を考える際、最も長い枝、二番目に長い枝、三番目に長い枝とそれぞれその本数にのみ注目すればよい。

目次• spiderとは• spiderのbroadcast domination• pendant edge とは• pendant edge が ついた道のbroadcast domination

目次• spiderとは• spiderのbroadcast domination• pendant edge とは• pendant edge が ついた道のbroadcast dominationpendant edge とは次数が1の頂点に接続する辺を pendant edge と呼ぶ。
𝑥𝑥1 𝑥𝑥2𝑥𝑥3 𝑥𝑥4𝑦𝑦3𝑥𝑥5 𝑥𝑥6

𝑦𝑦6𝑥𝑥7 𝑥𝑥86……………………..

𝑥𝑥𝑚𝑚−1 𝑥𝑥𝑚𝑚

道上の頂点を端から𝑥𝑥1 , 𝑥𝑥2 , … , 𝑥𝑥𝑚𝑚 とし、𝑥𝑥𝑖𝑖 に接続する道上に無い点を𝑦𝑦𝑖𝑖 とする。

研究内容
道にpendant edge を付け加えた時の broadcast domination
number の変化を調べた
頂点数kの道𝑃𝑃𝑘𝑘
𝑃𝑃𝑘𝑘 にpendant edge を接続した木 を T とする。

このとき 𝛾𝛾𝑏𝑏 𝑇𝑇 = 𝛾𝛾𝑏𝑏 𝑃𝑃𝑘𝑘 + 1 となる最小のpendant edge の本数と、接続する道上の頂点はどこか。

結果
𝛾𝛾𝑏𝑏 𝑇𝑇 = 𝛾𝛾𝑏𝑏 𝑃𝑃𝑘𝑘 + 1 とするために必要なpendant edge の最小の本数eは以下のように決まる。
1e=32（𝑘𝑘 = 3𝑛𝑛 のとき）

（𝑘𝑘 = 3𝑛𝑛 + 1 のとき）

（𝑘𝑘 = 3𝑛𝑛 + 2 のとき）

結果
𝛾𝛾𝑏𝑏 𝑇𝑇 = 𝛾𝛾𝑏𝑏 𝑃𝑃𝑘𝑘 + 1 とするために必要なpendant edge の最小の本数eは以下のように決まる。
1e=32（𝑘𝑘 = 3𝑛𝑛 のとき）

（𝑘𝑘 = 3𝑛𝑛 + 1 のとき）

（𝑘𝑘 = 3𝑛𝑛 + 2 のとき）

以下頂点数がそれぞれ 3n, 3n+1, 3n+2 の道について、どのようにpendant edge をつければ 𝛾𝛾𝑏𝑏 𝑇𝑇 = 𝛾𝛾𝑏𝑏 𝑃𝑃𝑘𝑘 + 1 となるかを,

𝛾𝛾𝑏𝑏 𝑇𝑇 ≠ 𝛾𝛾𝑏𝑏 𝑃𝑃𝑘𝑘 となることを利用して示す。

𝑃𝑃3𝑛𝑛+1 について下のグラフのように、𝑥𝑥3, 𝑥𝑥5, 𝑥𝑥7 にpendant edge をつければ、

𝛾𝛾𝑏𝑏 𝑇𝑇 ≠ 𝛾𝛾𝑏𝑏 𝑃𝑃3𝑛𝑛+1 となる。
𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4

𝑦𝑦3𝑥𝑥5 𝑥𝑥6

𝑦𝑦5𝑥𝑥7 𝑥𝑥86

𝑦𝑦7……………………..

𝑥𝑥3n 𝑥𝑥3n+1

𝛾𝛾𝑏𝑏 𝑃𝑃3𝑛𝑛+1=3𝑛𝑛+1
3𝑃𝑃3𝑛𝑛+1 について= 𝑛𝑛 + 1 である。

𝑛𝑛 + 1で支配できる点は最大3𝑛𝑛 + 3点であり、元の道の頂点数と比較すると2点分多く支配することができる。

このことを利用すると、道に割り振ることのできる値は、
𝑃𝑃3𝑛𝑛 の時のように１のみとならず、最大3を割り振ることができる。
３という値を１ずつ道に割り振ったとき支配できる点は最大9点
３を道に割り振ったとき支配できる点は最大7点
この差 2 を 𝑛𝑛 + 1で余分に支配できることに活用する
𝑥𝑥1 𝑥𝑥2

７点支配

9点支配

11

1

３𝑥𝑥3n 𝑥𝑥3n+1

𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4

𝑦𝑦3𝑥𝑥5 𝑥𝑥6

𝑦𝑦5

𝑃𝑃3𝑛𝑛+1 について

𝑥𝑥7 𝑥𝑥86

𝑦𝑦7……………………..

証明の方針
道上に置くことのできる値は1,2,3のいずれか。
→𝑦𝑦3 が（i） １で支配される（ii） 2で支配される（iii）3で支配される

𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4

𝑦𝑦3𝑥𝑥5 𝑥𝑥6

𝑦𝑦5

𝑃𝑃3𝑛𝑛+1 について

𝑥𝑥7 𝑥𝑥86

𝑦𝑦7……………………..

証明の方針
道上に置くことのできる値は1,2,3のいずれか。
→𝑦𝑦3 が（i） １で支配される（ii） 2で支配される（iii）3で支配される

𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4

𝑦𝑦3𝑥𝑥5 𝑥𝑥6

𝑦𝑦5

𝑃𝑃3𝑛𝑛+1 について

𝑥𝑥7 𝑥𝑥86

𝑦𝑦7……………………..

証明の方針
道上に置くことのできる値は1,2,3のいずれか。
→𝑦𝑦3 が（i） １で支配される① 𝑥𝑥2 に２が置かれy3 が支配される。
② 𝑥𝑥3 に２が置かれy3 が支配される。
（ii） 2で支配される③ 𝑥𝑥4 に２が置かれy3 が支配される。
（iii）3で支配される

𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4

𝑦𝑦3𝑥𝑥5 𝑥𝑥6

𝑦𝑦5𝑃𝑃3𝑛𝑛+1 について

𝑥𝑥7 𝑥𝑥86

𝑦𝑦7……………………..

証明の方針
道上に置くことのできる値は1,2,3のいずれか。
→𝑦𝑦3 が（i） １で支配される① 𝑥𝑥2 に２が置かれy3 が支配される。
② 𝑥𝑥3 に２が置かれy3 が支配される。
（ii） 2で支配される③ 𝑥𝑥4 に２が置かれy3 が支配される。
（iii）3で支配される

𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4

𝑦𝑦3𝑥𝑥5 𝑥𝑥6

𝑦𝑦5

𝑃𝑃3𝑛𝑛+1 について

𝑥𝑥7 𝑥𝑥86

𝑦𝑦7……………………..

証明の方針
道上に置くことのできる値は1,2,3のいずれか。
→𝑦𝑦3 が（i） １で支配される① 𝑥𝑥2 に２が置かれy3 が支配される。
② 𝑥𝑥3 に２が置かれy3 が支配される。
（ii） 2で支配される③ 𝑥𝑥4 に２が置かれy3 が支配される。
（iii）3で支配される
このいずれかで𝑦𝑦3 が支配されるとき、常に 𝛾𝛾𝑏𝑏 𝑇𝑇 ≠ 𝛾𝛾𝑏𝑏 𝑃𝑃3𝑛𝑛+1であることを示す。（今回は赤文字のみ）

𝑃𝑃3𝑛𝑛+1 について(ii) 𝑦𝑦3 が2で支配されるとき② 𝑥𝑥3 に2が割り振られるとき→残る支配されていない点は𝑦𝑦5, 𝑦𝑦7 と𝑥𝑥6 ~𝑥𝑥3𝑛𝑛+1→ 𝑦𝑦5 を支配する値は必ず同時に𝑥𝑥5 も支配するため𝑥𝑥5 も支配されていないと考えてよい→残る形は𝑦𝑦5 𝑥𝑥5 ~𝑥𝑥3𝑛𝑛+1 の道に𝑦𝑦7 がついたグラフと見て取れる。

2𝑥𝑥3 𝑥𝑥4

𝑦𝑦3……………………..
6

𝑦𝑦5

𝑦𝑦7

𝑃𝑃3𝑛𝑛+1 について・𝑦𝑦3 が2で支配されるとき② 𝑥𝑥3 に2が割り振られるとき→残る支配されていない点は𝑦𝑦5 と𝑥𝑥6 ~𝑥𝑥3𝑛𝑛+1→ 𝑦𝑦5 を支配する値は必ず同時に𝑥𝑥5 も支配するため𝑥𝑥5 も支配されていないと考えてよい→残る形は𝑦𝑦5 𝑥𝑥5 ~𝑥𝑥3𝑛𝑛+1 の道に𝑦𝑦7 がついたグラフと見て取れる。
道の頂点数は3𝑛𝑛 − 2でありこれの支配に必要な値は3𝑛𝑛−23= 𝑛𝑛である。

すでに2割り振っているため、残る道には𝑛𝑛 − 1までしか割り振ることはできない。
→𝑦𝑦3 は2で支配できない
𝑥𝑥1 𝑥𝑥2

2𝑥𝑥3 𝑥𝑥4

𝑦𝑦3＋

𝑦𝑦5𝑥𝑥5 𝑥𝑥6

6𝑥𝑥7 𝑥𝑥8 ……………………..

𝑦𝑦7

まとめ
Spider について

定理 spider の broadcast domination number は、𝑙𝑙1, 𝑙𝑙2, 𝑙𝑙3 と その本数の 𝑎𝑎1, 𝑎𝑎2 のみに依存する。

（𝑙𝑙4, 𝑙𝑙5, ・・・ が存在してもbroadcast domination number に影響しない）

まとめ𝛾𝛾𝑏𝑏 𝑇𝑇 = 𝛾𝛾𝑏𝑏 𝑃𝑃𝑘𝑘 + 1 を満たすpendant edge の本数とつけ方は、道Pの頂点数𝑘𝑘によって決まる。
𝑘𝑘 = 3𝑛𝑛のとき → １本 （𝑥𝑥3 につける）
𝑘𝑘 = 3𝑛𝑛 + 1のとき → 3本 （𝑥𝑥3, 𝑥𝑥5, 𝑥𝑥7 につける）
𝑘𝑘 = 3𝑛𝑛 + 2のとき → 2本 （𝑥𝑥3, 𝑥𝑥5 につける）

今後の課題𝛾𝛾𝑏𝑏 𝑇𝑇 = 𝛾𝛾𝑏𝑏 𝑃𝑃𝑘𝑘 + 2 となる pendant edge のつけ方は？

𝑘𝑘 = 3𝑛𝑛のとき 加える pendant edge が5本
𝑘𝑘 = 3𝑛𝑛 + 1のとき 加える pendant edge が6本
𝑘𝑘 = 3𝑛𝑛 + 2のとき ？

また、これらのbroadcast domination number を求める公式

ご清聴ありがとうございました。