An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,...An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,denoted by cf 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 investigate the relation between the conflict-free connection number and the independence number of a graph.We firstly show that cf c(G)≤α(G)for any connected graph G,and give an example to show that the bound is sharp.With this result,we prove that if T is a tree with?(T)≥(α(T)+2)/2,then cf c(T)=?(T).展开更多
A vertex-colored path P is rainbow if its internal vertices have distinct colors;whereas P is monochromatic if its internal vertices are colored the same.For a vertex-colored connected graph G,the rainbow vertex-conne...A vertex-colored path P is rainbow if its internal vertices have distinct colors;whereas P is monochromatic if its internal vertices are colored the same.For a vertex-colored connected graph G,the rainbow vertex-connection number rvc(G)is the minimum number of colors used such that there is a rainbow path joining any two vertices of G;whereas the monochromatic vertex-connection number mvc(G)is the maximum number of colors used such that any two vertices of G are connected by a monochromatic path.These two opposite concepts are the vertex-versions of rainbow connection number rc(G)and monochromatic connection number mc(G)respectively.The study on rc(G)and mc(G)of random graphs drew much attention,and there are few results on the rainbow and monochromatic vertex-connection numbers.In this paper,we consider these two vertex-connection numbers of random graphs and establish sharp threshold functions for them,respectively.展开更多
A vertex-colored graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex...A vertex-colored graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. If for every pair u, v of distinct vertices, G contains a rainbow u-v geodesic, then G is strong rainbow vertex-connected. The minimum number k for which there exists a k-vertex-coloring of G that results in a strongly rainbow vertex-connected graph is called the strong rainbow vertex-connection number of G, denoted by srvc(G). Observe that rvc(G) ≤ srvc(G) for any nontrivial connected graph G. In this paper, for a Ladder L_n,we determine the exact value of srvc(L_n) for n even. For n odd, upper and lower bounds of srvc(L_n) are obtained. We also give upper and lower bounds of the(strong) rainbow vertex-connection number of Mbius Ladder.展开更多
基金supported by Hunan Education Department Foundation(No.18A382)。
文摘An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,denoted by cf 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 investigate the relation between the conflict-free connection number and the independence number of a graph.We firstly show that cf c(G)≤α(G)for any connected graph G,and give an example to show that the bound is sharp.With this result,we prove that if T is a tree with?(T)≥(α(T)+2)/2,then cf c(T)=?(T).
基金supported by the National Natural Science Foundation of China(Nos.11901196)Natural Science Foundation of Anhui Province(Nos.JZ2020AKZR0295)by the Scholarship Promotion Program of Hefei University of Technology(Nos.JZ2019HGTA0038)。
文摘A vertex-colored path P is rainbow if its internal vertices have distinct colors;whereas P is monochromatic if its internal vertices are colored the same.For a vertex-colored connected graph G,the rainbow vertex-connection number rvc(G)is the minimum number of colors used such that there is a rainbow path joining any two vertices of G;whereas the monochromatic vertex-connection number mvc(G)is the maximum number of colors used such that any two vertices of G are connected by a monochromatic path.These two opposite concepts are the vertex-versions of rainbow connection number rc(G)and monochromatic connection number mc(G)respectively.The study on rc(G)and mc(G)of random graphs drew much attention,and there are few results on the rainbow and monochromatic vertex-connection numbers.In this paper,we consider these two vertex-connection numbers of random graphs and establish sharp threshold functions for them,respectively.
基金Supported by the National Natural Science Foundation of China(11551001,11061027,11261047,11161037,11461054)Supported by the Science Found of Qinghai Province(2016-ZJ-948Q,2014-ZJ-907)
文摘A vertex-colored graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. If for every pair u, v of distinct vertices, G contains a rainbow u-v geodesic, then G is strong rainbow vertex-connected. The minimum number k for which there exists a k-vertex-coloring of G that results in a strongly rainbow vertex-connected graph is called the strong rainbow vertex-connection number of G, denoted by srvc(G). Observe that rvc(G) ≤ srvc(G) for any nontrivial connected graph G. In this paper, for a Ladder L_n,we determine the exact value of srvc(L_n) for n even. For n odd, upper and lower bounds of srvc(L_n) are obtained. We also give upper and lower bounds of the(strong) rainbow vertex-connection number of Mbius Ladder.
