On conflict-free connection of graphs
On conflict-free connection of graphs
复制标题
论图的无冲突连接
DOI：
10.1016/j.dam.2018.08.006
复制
发表时间：
2019-02
影响因子：
1.1
通讯作者：
Zhao Haixing
中科院分区：
文献类型：
--
作者：
Chang Hong;Huang Zhong;Li Xueliang;Mao Yaping;Zhao Haixing
An edge-colored graph G is conflict-free connected if, between each pair of distinct vertices of G, there exists a path in G containing a color used on exactly one of its edges. The conflict-free connection number of a connected graph G, denoted by c f c (G), is defined as the minimum number of colors that are required in order to make G conflict-free connected. In this paper, we firstly determine all trees T of order n for which c f c (T)= n− t, where t≥ 1 and n≥ 2 t+ 2. Secondly, we prove that let G be a graph of order n, then 1≤ c f c (G)≤ n− 1, and characterize the graphs G with c f c (G)= 1, n− 4, n− 3, n− 2, n− 1, respectively. Finally, we get the Nordhaus–Gaddum-type result for the conflict-free connection number of graphs, and prove that if G and G¯ are connected graphs of order n (n≥ 4), then 4≤ c f c (G)+ c f c (G¯)≤ n and 4≤ c f c (G)⋅ c f c (G¯)≤ 2 (n− 2), moreover, c f c (G)+ c f c (G¯)= n or c f c (G)⋅ c f c (G¯)= 2 (n− 2) if and only if one of G and G¯ is a tree with maximum degree n− 2 or a path of order 5, and the lower bounds are sharp.
登录
查看更多内容
图的彩虹连接：一项调查
影响因子：
0.7
作者：
Li X.;Shi Y.;Sun Y.
通讯作者：
Sun Y.
DOI：
10.1137/120880471
发表时间：
2010-02
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
Panagiotis Cheilaris;Balázs Keszegh;Dömötör Pálvölgyi
通讯作者：
Panagiotis Cheilaris;Balázs Keszegh;Dömötör Pálvölgyi
DOI：
10.1016/j.dam.2014.12.009
发表时间：
2012-12
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Xueliang Li;Y. Mao
通讯作者：
Xueliang Li;Y. Mao
DOI：
10.1016/j.dam.2011.06.016
发表时间：
2011-09
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Daobin Li;Baoyindureng Wu;Xu Yang;Xinhui An
通讯作者：
Daobin Li;Baoyindureng Wu;Xu Yang;Xinhui An
DOI：
10.1155/s016117127900020x
发表时间：
1979
影响因子：
1.2
作者：
J. Akiyama;F. Harary
通讯作者：
J. Akiyama;F. Harary