Fengnan Yanling, Zhao Wang, Chengfu Ye, Shumin Zhang

The rainbow vertex-index of complementary graphs

A vertex-colored graph $G$ is \emph{rainbow vertex-connected} if twovertices are connected by a path whose internal vertices havedistinct colors. The \emph{rainbow vertex-connection number} of aconnected graph $G$, denoted by $rvc(G)$, is the smallest number ofcolors that are needed in order to make $G$ rainbowvertex-connected. If for every pair $u,v$ of distinct vertices, $G$contains a vertex-rainbow $u-v$ geodesic, then $G$ is \emph{stronglyrainbow vertex-connected}. The minimum $k$ for which there exists a$k$-coloring of $G$ that results in a stronglyrainbow-vertex-connected graph is called the \emph{strong rainbowvertex number} $srvc(G)$ of $G$. Thus $rvc(G)\leq srvc(G)$ for everynontrivial connected graph $G$. A tree $T$ in $G$ is called a\emph{rainbow vertex tree} if the internal vertices of $T$ receivedifferent colors. For a graph $G=(V,E)$ and a set $S\subseteq V$ ofat least two vertices, \emph{an $S$-Steiner tree} or \emph{a Steinertree connecting $S$} (or simply, \emph{an $S$-tree}) is a suchsubgraph $T=(V',E')$ of $G$ that is a tree with $S\subseteq V'$. For$S\subseteq V(G)$ and $|S|\geq 2$, an $S$-Steiner tree $T$ is saidto be a \emph{rainbow vertex $S$-tree} if the internal vertices of $T$ receive distinct colors. The minimum number of colors that areneeded in a vertex-coloring of $G$ such that there is a rainbowvertex $S$-tree for every $k$-set $S$ of $V(G)$ is called the {\it$k$-rainbow vertex-index} of $G$, denoted by $rvx_k(G)$. In thispaper, we first investigate the strong rainbow vertex-connection ofcomplementary graphs. The $k$-rainbow vertex-index of complementary graphs are also studied.

Keywords:

Strong rainbow vertex-connection number, Complementary graph, Rainbow vertex S-tree, k-rainbowvertex-index,

PDF

___

J. A. Bondy and U. S. R. Murty, Graph theory, GTM 244, Springer, 2008.
G. Chartrand, G. L. Johns, K. A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem., 133, 85–98, 2008.
G. Chartrand, G. L. Johns, K. A. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks, 54(2), 75–81, 2009.
L. Chen, X. Li and H. Lian, Nordhaus-Gaddum-type theorem for rainbow connection number of graphs, Graphs Combin., 29(5), 1235–1247, 2013.
L. Chen, X. Li and M. Liu, Nordhaus-Gaddum-type theorem for the rainbow vertex connection number of a graph, Utilitas Math., 86, 335–340, 2011.
X. Cheng and D. Du, Steiner trees in industry, Kluwer Academic Publisher, Dordrecht, 2001.
D. Du and X. Hu, Steiner tree problems in computer communication networks, World Scientific, 2008.
M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree three, J. Graph Theory, 63(3), 185-191, 2010.
X. Li and Y. Shi, On the rainbow vertex-connection, Discuss. Math. Graph Theory, 33(2), 307–313, 20 X. Li and Y. Sun, Rainbow connections of graphs, SpringerBriefs in Math., Springer, New York, 20 X. Li, Y. Mao and Y. Shi, The strong rainbow vertex-connection of graphs, Utilitas Math., 93, 213– 223, 2014.
X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs–A survey, Graphs Combin., 29(1), 1-38, 20 Y. Mao, The vertex-rainbow index of a graph, arXiv:1502.00151v1 [math.CO], 31 Jan 2015.
E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly, 63, 175–177, 19

Journal of Algebra Combinatorics Discrete Structures and Applications-Cover

Başlangıç: 2015
Yayıncı: İrfan ŞİAP

Arşiv

Sayıdaki Diğer Makaleler

A further study for the upper bound of the cardinality of Farey vertices and application in discrete geometry

Daniel KHOSHNOUDİRAD

The rainbow vertex-index of complementary graphs

Fengnan Yanling, Zhao Wang, Chengfu Ye, Shumin Zhang

Skew cyclic codes over $F_{q}+uF_{q}+vF_{q}+uvF_{q}$

Ting YAO, Minjia Shi, Patrick Solé

Approximate counting with m counters: A probabilistic analysis

Guy LOUCHARD, Helmut PRODİNGER

Some new quasi-twisted ternary linear codes

Rumen DASKALOV, Plamen HRİSTOV