最大次数 3 のグラフに対する proper disconnection number の解析
川原遥香

1(指導教員：長尾篤樹)

はじめにグラフ理論における彩色数の研究は古くから行われている．辺彩色に関する研究も行われているが，辺彩色指数は最大次数もしくは最大次数 +1 のどちらかであり，辺彩色指数はグラフの特徴を表す指標としては弱いと言える．
辺彩色指数をより一般化した指標として，Chartrand
らは [2] で rainbow disconnection を導入した．rainbow disconnection の概念に触発され，Chen らは [1]にて proper disconnection number（pd 値）を提唱しており，pd 値によってグラフの特徴付けが行われている．
本研究では一般のグラフに対しての pd 値の解析を目的とし，最大次数 3 かつ pd 値が 1 となるグラフの特徴について解析を行なった．

2

図1m 乗 Cnm における pd 値は以下の値となる．
m ≤ pd(Cnm ) ≤ pd(Cnm−1 ) + 2
(gcd(n, m) ≡ 0 mod 2)
mm
≤
pd(C)
≤pd(Cnm−1 ) + 3
n
(gcd(n, m) ≡ 1 mod 2)

数学的準備

辺彩色済みグラフ G について，G の辺からなる集合 F ⊆ E(G) を考える．F が G の edge-cut であり，F の隣接する辺の全てのペアに異なる色が割り当てられているとき，F は G の proper cut という．辺彩色済みグラフ G は，G の異なる頂点のそれぞれのペアを分離するような proper cut が存在するとき，properdisconnected （以下，p-非連結とする．）であるという．
連結グラフ G について，G が，p-非連結となるような最小の辺彩色数を G の proper disconnection number（以下，pd 値とする．）といい，pd(G) と表記する．

4

最大次数 3 で pd 値が 2 になるグラフ

最大次数 3 で次数 3 である頂点の集合が独立集合でないグラフのうち，pd 値が 1 でないグラフを発見した．pd 値が 2 以上になるグラフは図 1 のように頂点数n(≧ 3) で一般化できる．

4.1

pd 値が 1 となる必要十分条件

4 節で発見したグラフの特徴を観察することで，最大次数 3 であり、次数 3 の頂点が独立集合とは限らないグラフの pd 値について定理 2 を拡張した結果を示すことができた．
Theorem 5. ∆(G) = 3 であるグラフ G に対し、次数が 3 である頂点のみで構成される集合を S とする。G上の S による誘導部分グラフが持つ連結成分のサイズが高々 3 であるとき，G が三角形か K2,3 を含むならば pd(G) = 2 であり、そうでないならば pd(G) = 1 である。

先行研究 [3] では，最大次数 ∆(G) = 4 である k−辺彩色グラフ G が p-非連結かどうか判定する問題がNP-complete であることがわかっている．
Theorem 1. [3] ある正の定数 k について，G を最大次数 ∆(G) = 4 の k-辺彩色グラフとし，u, v を G の任意のある 2 頂点とする．このとき，G に u − v properedge-cut が存在するかどうか判定する問題は NP 完全である．
また，最大次数 3 のグラフがある条件を満たすときpd 値の上下界を一致させている．この定理はグラフの頂点数に関する帰納法によって示されている．
Theorem 2. [3] G を最大次数 3 で次数 3 である頂点の集合が独立集合を形成している連結グラフとする．Gが三角形か K2,3 を持つならば pd(G) = 2 であり、そうでないならば pd(G) = 1 である。
卒業研究 [4] ではある条件を満たすサイクルの累乗のpd 値に対する上下界を以下のように一致させることができた．
Theorem 3. [4] n ≥ 4m であるとき n 頂点のサイクルの m 乗 Cnm における pd 値 pd(Cnm ) は m となる。

3最大次数 3 で pd 値が 2 になるグラフ

4.23-正則グラフの pd 値が 1 となる十分条件

グラフの pd 値を決定する要素としてグラフの girthに着目し，解析を行った．girth が 3，つまり三角形を含むグラフは必ず pd 値が 2 となることが先行研究 [1]にて示されている．また，最大次数が 3 かつ girth が 4のグラフで pd 値が 2 となるグラフは 4 節にて示した．
さらに，本節では girth が 5 である 3-正則グラフの pd値が 1 であることを示すことができた．
Observation 6. 連結で girth が 5 である 3-正則グラフ G において，G \ {x, y} 上に y でない x の隣接頂点が 2 頂点以上含まれる連結成分が存在するとき，G 上に x が属し y が属さないサイクルが少なくとも 1 つ存在する．
Observation 7. G \ {x, y} の連結成分のうち，x の隣接頂点と y の隣接頂点をちょうど 1 頂点ずつ含む連結成分 Gi が存在するとき，Gi には少なくとも 1 つサイクルが存在する．

サイクルの累乗の pd 値定理 3 のアイディアを応用することで頂点数 4m 未満のサイクルの m 乘の pd 値に対する上界を下げることができた．
Theorem 4. n < 4m であるとき n 頂点のサイクルの1

s, t, u とする．x を含まない s − t パス，t − u パス，u − s パスのうち最も長さの短いパスと，そのパスの端点と y を結ぶ辺の和集合から新たなサイクルを作る．

図2

適当にサイクルをとり，ひげに衝突が生じたら新たなサイクルを取ることを繰り返す．新しいサイクルの長さは元のサイクルの長さより必ず短くなり，5 サイクルに対応するひげは衝突が存在しないのでこの繰り返しは必ず停止する．ひげの衝突が存在しないサイクルが得られたら，サイクルに対応するひげを x − y matchingcut とする．
(2-2)Gi が x の隣接頂点と y の隣接頂点を高々 1 頂点ずつ含むとき
観察 7 より 1 ≤ i ≤ u である全ての i について，Tiには少なくとも 1 つサイクル C が存在する．C の 1 頂点と x を繋ぐパスと C の和集合からなる部分グラフを1 つ選ぶ．(2-1) と同様にひげの衝突が生じたら新たな部分グラフを取ることを繰り返す．新しい部分グラフは元の部分グラフより必ずサイクルの長さかパスの長さが短くなり，長さ 1 のパスと 5 サイクルの和集合に対応するひげには衝突が存在しないのでこの繰り返しは必ず停止する．
同様に全ての i について，x と Ti に属する頂点で適当に x を含むサイクルとパスからなる部分グラフを 1つ選び，ひげに衝突が生じなくなるまで新たな部分グラフを取ることを繰り返す．T1 , T2 , . . . Tu で得られた部分グラフに対応するひげの和集合が x − y matching
cut である．

部分グラフ G1 , G2 に対応するひげDeﬁnition 8. 連結グラフ G において，G のある部分グラフ G1 に属する頂点と属さない頂点を接続する辺の集合を，部分グラフ G1 に対応する”ひげ”と定義する．
また，G1 に対応するひげのうち 2 辺または 3 辺が隣接しているとき，ひげに”衝突”が存在すると定義する．
ある部分グラフに属する頂点 x と部分グラフに属さない頂点を分離する辺集合を 8 のようにひげと定義し，ひげを利用して定理の証明を行う．例えば，図 2 の G1に対応するひげは 2 辺の衝突が存在しており，G2 に対応するひげは衝突が存在しない．
Theorem 9. girth が 5 の 3-正則グラフ G は pd 値 1

Proof. (1) 辺 xy が橋であるとき，辺 xy が x−y matching cut である．
(2) 辺 xy が 橋 で な い と き G \ {x, y} の 連 結成 分 を そ れ ぞ れ G1 , G2 , . . . Gk (k ≤ 1),N (x) ={x1 , x2 , x3 },N (y) = {y1 , y2 , y3 } とおく．
(2-1)G \ {x, y} の連結成分のうち y でない x の隣接頂点が 2 頂点以上含まれる連結成分が存在するとき，その連結成分を Gs とおく．
観察 6 より G には x を含んで y を含まないサイクルが少なくとも 1 つ存在する．適当に x を含んで y を含まないサイクルを 1 つ選ぶと，サイクルに対応するひげの衝突のパターンは 3 種類考えられる．

図35まとめと今後の課題

本研究では最大次数 3 のグラフの pd 値が 1 となるいくつかの条件を示した．定理 2 を拡張した結果として，最大次数が 3 であり，次数 3 の頂点の連結成分の大きさが 4 以下であるグラフの pd 値が 1 となる必要十分条件を示した．また，girth が 5 である 3-正則グラフ最大次数 3 のグラフの pd 値が必ず 1 となることを示した．
今後の課題として，最大次数 3 のグラフに対する pd値が 1 となる場合の必要十分条件を確認できないか検討している．

サイクルに対応するひげの衝突

参考文献[1] Xuqing Bai, You Chen, Meng Ji, Xueliang Li,
Yindi Weng, and Wenyan Wu. Proper disconnection of graphs, 2019.
[2] Gary Chartrand, Stephen Devereaux, Teresa W
Haynes, Stephen T Hedetniemi, and Ping Zhang.
Rainbow disconnection in graphs. Discussiones
Mathematicae Graph Theory, 38(4):1007–1021,2018.
[3] You Chen, Ping Li, Xueliang Li, and Yindi Weng.
Complexity results for the proper disconnection ofgraphs. In International Workshop on Frontiersin Algorithmics, pages 1–12. Springer, 2020.
[4] 川原遥香 and 長尾篤樹. サイクルの累乗に対するproper disconnection number. お茶の水女子大学
卒業研究発表会, 2022.

2 辺のひげの衝突が存在するときを考える．このとき,k 組のひげの衝突のうち 1 組に着目する．衝突する
ひげの 2 辺の端点のうち，サイクルに含まれる頂点をs, t, サイクルに含まれない頂点を z とする．サイクル
上の s − t パスのうち，x が含まれるパスを P1 ,x が含まれないパスを P2 とする．2 辺が y 以外で衝突する場
合はパス P1 とパス s − z − t の和集合によって新たなサイクルを作ることができる．2 辺が y で衝突するときはパス P2 とパス s − z − t の和集合によって新たなサイクルを作ることができる．
2 辺のひげの衝突がなく，3 辺のひげの衝突のみ存在するときを考える．3 辺が y 以外で衝突する場合は最大次数 3 より 3 辺が衝突している端点から他の辺は伸びない．したがって衝突していないひげを x − ymatching cut とする．3 辺が y で衝突する場合は衝突しているひげの端点のうちサイクルに含まれる頂点を2