BibTex RIS Kaynak Göster

The rainbow vertex-index of complementary graphs

Yıl 2015, , 157 - 161, 14.09.2015
https://doi.org/10.13069/jacodesmath.80607

Öz

A vertex-colored graph $G$ is \emph{rainbow vertex-connected} if two
vertices are connected by a path whose internal vertices have
distinct colors. The \emph{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 vertex-rainbow $u-v$ geodesic, then $G$ is \emph{strongly
rainbow vertex-connected}. The minimum $k$ for which there exists a
$k$-coloring of $G$ that results in a strongly
rainbow-vertex-connected graph is called the \emph{strong rainbow
vertex number} $srvc(G)$ of $G$. Thus $rvc(G)\leq srvc(G)$ for every
nontrivial connected graph $G$. A tree $T$ in $G$ is called a
\emph{rainbow vertex tree} if the internal vertices of $T$ receive
different colors. For a graph $G=(V,E)$ and a set $S\subseteq V$ of
at least two vertices, \emph{an $S$-Steiner tree} or \emph{a Steiner
tree connecting $S$} (or simply, \emph{an $S$-tree}) is a such
subgraph $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 said
to be a \emph{rainbow vertex $S$-tree} if the internal vertices of $T$ receive distinct colors. The minimum number of colors that are
needed in a vertex-coloring of $G$ such that there is a rainbow
vertex $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 this
paper, we first investigate the strong rainbow vertex-connection of
complementary graphs. The $k$-rainbow vertex-index of complementary graphs are also studied.

Kaynakça

  • 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
Yıl 2015, , 157 - 161, 14.09.2015
https://doi.org/10.13069/jacodesmath.80607

Öz

Kaynakça

  • 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
Toplam 11 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Bölüm Makaleler
Yazarlar

Fengnan Yanling Bu kişi benim

Zhao Wang Bu kişi benim

Chengfu Ye Bu kişi benim

Shumin Zhang Bu kişi benim

Yayımlanma Tarihi 14 Eylül 2015
Yayımlandığı Sayı Yıl 2015

Kaynak Göster

APA Yanling, F., Wang, Z., Ye, C., Zhang, S. (2015). The rainbow vertex-index of complementary graphs. Journal of Algebra Combinatorics Discrete Structures and Applications, 2(3), 157-161. https://doi.org/10.13069/jacodesmath.80607
AMA Yanling F, Wang Z, Ye C, Zhang S. The rainbow vertex-index of complementary graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. Eylül 2015;2(3):157-161. doi:10.13069/jacodesmath.80607
Chicago Yanling, Fengnan, Zhao Wang, Chengfu Ye, ve Shumin Zhang. “The Rainbow Vertex-Index of Complementary Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 2, sy. 3 (Eylül 2015): 157-61. https://doi.org/10.13069/jacodesmath.80607.
EndNote Yanling F, Wang Z, Ye C, Zhang S (01 Eylül 2015) The rainbow vertex-index of complementary graphs. Journal of Algebra Combinatorics Discrete Structures and Applications 2 3 157–161.
IEEE F. Yanling, Z. Wang, C. Ye, ve S. Zhang, “The rainbow vertex-index of complementary graphs”, Journal of Algebra Combinatorics Discrete Structures and Applications, c. 2, sy. 3, ss. 157–161, 2015, doi: 10.13069/jacodesmath.80607.
ISNAD Yanling, Fengnan vd. “The Rainbow Vertex-Index of Complementary Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 2/3 (Eylül 2015), 157-161. https://doi.org/10.13069/jacodesmath.80607.
JAMA Yanling F, Wang Z, Ye C, Zhang S. The rainbow vertex-index of complementary graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2:157–161.
MLA Yanling, Fengnan vd. “The Rainbow Vertex-Index of Complementary Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications, c. 2, sy. 3, 2015, ss. 157-61, doi:10.13069/jacodesmath.80607.
Vancouver Yanling F, Wang Z, Ye C, Zhang S. The rainbow vertex-index of complementary graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2(3):157-61.