Ladder图和Mbius Ladder图的彩虹点连通数

展开
  • Department of Mathematics,Qinghai Normal University.
LIU Hui-min(1969-), female, native of Nanyang, Henan, an associate professor of Qinghai Normal University, M.S.D., engages in graph theory and combinatorial optimization.

收稿日期: 2014-07-31

  网络出版日期: 2020-11-03

基金资助

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);

Rainbow Vertex-connection Number of Ladder and MÄobius Ladder

Expand
  • Department of Mathematics,Qinghai Normal University.
LIU Hui-min(1969-), female, native of Nanyang, Henan, an associate professor of Qinghai Normal University, M.S.D., engages in graph theory and combinatorial optimization.

Received date: 2014-07-31

  Online published: 2020-11-03

Supported by

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 Ln,we determine the exact value of srvc(Ln) for n even. For n odd, upper and lower bounds of srvc(Ln) are obtained. We also give upper and lower bounds of the(strong) rainbow vertex-connection number of Mbius Ladder. 

本文引用格式

刘慧敏, 毛亚平 . Ladder图和Mbius Ladder图的彩虹点连通数[J]. 数学季刊, 2016 , 31(4) : 399 -405 . DOI: 10.13371/j.cnki.chin.q.j.m.2016.04.008

Abstract

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 Ln,we determine the exact value of srvc(Ln) for n even. For n odd, upper and lower bounds of srvc(Ln) are obtained. We also give upper and lower bounds of the(strong) rainbow vertex-connection number of Mbius Ladder. 
文章导航

/