共有する隣接頂点数に着目した proper disconnection number の解析
川原遥香

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

はじめに

グラフ理論における彩色数の研究は古くから行われている．グラフ理論の一つのテーマである頂点彩色は非常に多く研究されており，パズルやスケジューリング問題のモデルとしても応用される．辺彩色に関する研究も行われているが，辺彩色指数は最大次数もしくは最大次数 +1 のどちらかであり，辺彩色指数はグラフの特徴を表す指標としては弱いと言える．先行研究 [1] では辺彩色指数をより一般化した proper disconnectionnumber（pd 値）を提唱しており，pd 値によってグラフの特徴付けが行われている．本研究ではより広いグラフクラスに対しての pd 値の解析を目的とし，サイクルの累乗と cograph の pd 値の解析を行なった．

22231323121 2122 11231 212$&

𝑝𝑑 𝐾$,& = max{⎡ . ⎤, ⎡ . ⎤} = 2
図13.131216𝑝𝑑 𝐾2 = ⎡ ⎤ = 32K3,4 と K6

C62 の pd 値

Theorem 5. 6 頂点のサイクルの 2 乗 C62 の pd 値はpd(C62 ) = 2

数学的準備

Proof. C62 の隣接する 2 頂点は 2 個の隣接頂点を共有しているので，補題 1 より pd(C62 ) ≥ 2．ここで，pd(C62 ) = 2 と仮定し，そのような辺彩色がある 1 辺 eを色 1 で彩色していると仮定する．このとき，図 2 左部のように C62 は誘導部分グラフとして K4 − {e} を持つので，補題 4 より K4 − {e} の e とのマッチング辺は色 1 となる．同様の操作を C62 上で確認できる任意の誘導部分グラフ K4 − {e} において行うことができる．K4 − {e} のマッチング辺を色 1 に彩色することを繰り返すと，その結果，C62 の全ての辺が色 1 と彩色される．これは pd(C62 ) = 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) と表記する．
先行研究 [1] では以下の補題を用いて，いくつかのグラフクラスについて pd 値の上下界を一致させている．
Lemma 1. [1] G を自明でない連結グラフとする．Gに t 個の共有隣接頂点を持つ 2 頂点 u,v が存在する
とき，よってそのような辺彩色は存在しないということになり，pd(C62 ) ≥ 3 が言える．また，6 頂点の完全グラフ
K6 の pd 値は 3 であり，C62 も同じ彩色で p-非連結となる．よって pd(C62 ) ≤ 3．以上より上下界が一致した
ので pd(C62 ) = 3．

pd(G) ≥ ⌈t/2⌉
さらに，uv ∈ E(G) のとき，pd(G) ≥ ⌈t/2⌉ + 1

1122 部グラフ，完全グラフについても上下界が一致する結果が知られている．
Theorem 2. [1] n 頂点と m 頂点の排反な頂点集合を持つ完全 2 部グラフ Kn,m の pd 値は1222222121pd(Kn,m ) = max{⌈n/2⌉, ⌈m/2⌉}
Theorem 3. [1] n 頂点の完全グラフ Kn の pd 値はpd(Kn ) = ⌈n/2⌉

図2

完全グラフに関してはさらに特殊な条件下での pd 値の下界解析に応用できる補題が知られている．
Lemma 4. [1] G = K4 − {e} とすると，pd(G) = 2である．さらに任意の p-非連結な辺彩色において G のマッチング辺は必ず同じ色になる．

3𝑉&

𝐶$#

3.2

11

𝑉#

1𝐶"#

C62 と C82

サイクルの累乗の pd 値

先行研究 [1] と同様の議論を用いて任意の位数を持つサイクルにおいて，ある条件を満たす累乗の pd 値に対する上下界を以下のように一致させることができる．
Theorem 6. n ≥ 4m であるとき n 頂点のサイクルのm 乗 Cnm における pd 値は以下の値となる．

サイクルの累乗における pd 値

前章で紹介した既存の補題を利用し，本研究では新たに以下のグラフやグラフクラスに対して pd 値の上下界を一致させることができた．

pd(Cnm ) = m1

11𝑣'𝑣#

00𝑣$

1𝑣" 𝑣# 𝑣$ 𝑣% 𝑣& 𝑣' 𝑣( 𝑣) 𝑣*

こ こ で ，G に 対 す る 辺 彩 色 を 考 え る ． G の 各 辺(vi , vj ) に対し，|i − j| ≡ d mod n とし、d < m である場合に辺 (vi , vj ) を色 d で彩色する．d ≥ m である場合には辺が存在しない．このとき辺彩色数は m となる．この彩色で G が p-非連結となっていることを示す．
V (G) を V1 = {v0 , . . . , v⌈ n2 ⌉−1 }，V2 = V (G) \ V1 に分割して，V1 の頂点と V2 の頂点を分離する edge-cut を考える．n ≥ 4m であるとき，図 2 右部のように，このedge-cut の隣接する辺は全て異なる色であるため，この彩色は proper cut となっている．k = 1, 2, . . . , ⌈ n2 ⌉ − 1として，Vk = {v0+k , . . . , v⌈ n2 ⌉−1+k } と，V (G) \ Vk からなる全ての V (G) の分割について，それぞれ Vk の頂点と V (G)\Vk の頂点を分離する edge-cut を考えると，それらは全て proper cut である．ここで，各頂点変数の添え字は mod n の整数を用いる．このとき G の全ての 2 頂点を分離する proper cut が存在する．よってこの彩色で G は p-非連結となるので pd(G) ≤ m．これと式 1 より上下界が一致し，pd(G) = m である．

4𝑣"

1Proof. G = Cnm と し ，G の 頂 点 集 合 を V (G) ={v0 , . . . , vn−1 } とおく．G の隣接する 2 頂点は 2(m−1)
個の隣接頂点を共有しているので補題 1 より，⌉⌈
2(m − 1)
+ 1 = m．
(1)
pd(G) ≥2𝑣(𝑣%𝑣)

𝑣&𝑣*cotreecograph

図 3 cotree と対応する cograph

G の t 個の共有隣接頂点からなる集合を Vt ，Vt を共有隣接頂点として持つ c 頂点からなる集合を Vc とする．G が p-非連結となるには同じ彩色で G[Vt ∪ Vc ] がp-非連結である必要がある．このとき G[Vt ∪Vc ] の辺集合は Vc , Vt を独立集合として持つ完全 2 部グラフに含まれる辺からなる集合 E1 と完全グラフ G[Vc ] に含まれる辺からなる集合 E2 に分けられる．G[E1 ], G[E2 ] の⌉, ⌈ 2c ⌉ である．
pd 値はそれぞれ定理 2,3 より ⌈ max(c,t)
2G[Vt ∪ Vc ] が p-非連結であるには，G[E1 ] と G[E2 ] の辺彩色は偶数頂点のときは被る色がないように，奇数頂点のときは 1 色だけ被って良い．したがって G[Vt ∪ Vc ]max(c,t)の pd 値は ⌊⌋ + ⌈ 2c ⌉．G[Vt ∪ Vc ] は G の部分グ2ラフであるため pd(G) ≥ pd(G[Vt ∪ Vc ]) となる．
この予想が真であるとき，以下のようにある cographの pd 値の下界を cotree を探索することで求めることができる．
Conjecture 8. ある cograph G の pd 値の下界は，Gの cotree の高さ 2 に存在する 1 ノードそれぞれに対し，c はその葉ノードの個数，t はその親であるそれぞれの1 の自分を含まない子が持つ葉ノード全ての個数としたときの以下の値の最大値となる．

cograph における pd 値

本研究では共有する隣接頂点数に着目し，サイクルの累乗の他に多くの共有する隣接頂点を持つグラフである cograph と呼ばれるグラフクラス [2] の pd 値の解析を行った．
cograph の pd 値の解析を行うにあたり，Lemma1 の拡張として，自明でない連結グラフ G が t 個の共有隣接頂点を持つ c 頂点をもち，さらに c 頂点から誘導される部分グラフがクリークであるときの G の pd 値の下界の検証をした．
cograph は以下のように定義できる．

⌊51. 自明なグラフは cograph である．
2. 複数の cograph の和集合により構成されるグラフも cograph である．
3. n 個の cograph の和集合にその n 個の cograph⌋ ⌈ ⌉max(c, t)
c+2
2

まとめと今後の課題

本研究ではサイクルの累乗と cograph の pd 値の解析を行なった．先行研究 [1] の補題を用いて任意の位数を持つサイクルの累乗が特定の条件を満たすときの pd値の上下界を一致させることができた．補題 1 の拡張に関する予想を立て，これを用いることで cotree からcograph の pd 値の下界を得ることができた．
今後の課題として conjecture7 の証明やより広いグラフクラスの pd 値を解析可能なアプローチの探索が考えられる．の頂点集合を全体の頂点集合の分割とみなした完
全 n 部グラフの辺を追加して構成されるグラフもcograph である．
また図 3 のように，項目 1 を葉，項目 2 を 0 ノード，項目 3 を 1 ノードとして持つ木である cotree からcograph を決定することができる．
Conjecture 7. G を自明でない連結グラフとする．Gに t 個の共有隣接頂点を持つ c 頂点 u1 , u2 , . . . , uc が存在し，この頂点集合から誘導される部分グラフがクリークであるとき，

参考文献[1] Xuqing Bai, You Chen, Meng Ji, Xueliang Li,Yindi Weng, and Wenyan Wu. Proper disconnection of graphs, 2019.
[2] Andreas Brandstät, Van Bang Le, and Jeremy
P.Spinrad. Graph classes : a survey. SIAM, 1999.

⌊⌋ ⌈ ⌉max(c, t)
cpd(G) ≥+22以下のような議論が行われているが，証明としては完成されていない．

2