典型文献
Bounds for the Rainbow Disconnection Numbers of Graphs
文献摘要：
An edge-cut of an edge-colored connected graph is called a rainbow cut if no two edges in the edge-cut are colored the same.An edge-colored graph is rainbow disconnected if for any two distinct vertices u and v of the graph,there exists a rainbow cut separating u and v.For a connected graph G,the rainbow disconnection number of G,denoted by rd(G),is defined as the smallest number of colors required to make G rainbow disconnected.In this paper,we first give some upper bounds for rd(G),and moreover,we completely characterize the graphs which meet the upper bounds of the Nordhaus-Gaddum type result obtained early by us.Secondly,we propose a conjecture that for any connected graph G,either rd(G) =λ+(G) or rd(G) =λ+(G)+ 1,where λ+(G) is the upper edge-connectivity,and prove that the conjecture holds for many classes of graphs,which supports this conjecture.Moreover,we prove that for an odd integer k,if G is a k-edge-connected k-regular graph,then x'(G) =k if and only if rd(G) =k.It implies that there are infinitely many k-edge-connected k-regular graphs G for which rd(G) =λ+ (G) for odd k,and also there are infinitely many k-edge-connected k-regular graphs G for which rd(G) =λ+(G) + 1 for odd k.For k =3,the result gives rise to an interesting result,which is equivalent to the famous Four-Color Problem.Finally,we give the relationship between rd(G)of a graph G and the rainbow vertex-disconnection number rvd(L(G)) of the line graph L(G) of G.
文献关键词：
中图分类号：
作者姓名：
Xu Qing BAI;Zhong HUANG;Xue Liang LI
作者机构：
Center for Combinatorics and LPMC,Nankai University,Tianjin 300071,P.R.China
文献出处：
引用格式：
[1]Xu Qing BAI;Zhong HUANG;Xue Liang LI-.Bounds for the Rainbow Disconnection Numbers of Graphs)[J].数学学报（英文版）,2022(02):384-396
A类：
Disconnection,Nordhaus,Gaddum,rvd
B类：
Bounds,Rainbow,Numbers,Graphs,An,cut,colored,called,rainbow,if,two,edges,are,same,disconnected,distinct,vertices,there,exists,separating,For,disconnection,number,denoted,by,defined,smallest,colors,required,make,In,this,paper,first,some,upper,bounds,moreover,completely,characterize,graphs,which,meet,type,result,obtained,early,Secondly,propose,conjecture,that,either,where,connectivity,prove,holds,many,classes,supports,Moreover,odd,integer,regular,then,only,It,implies,infinitely,also,gives,rise,interesting,equivalent,famous,Four,Color,Problem,Finally,relationship,between,vertex,line
AB值：
0.387956
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
