Dergiler / Journal of Algebra Combinatorics Discrete Structures and Applications / 2015 / Cilt: 2 Sayı: 3

The rainbow vertex-index of complementary graphs

Sayfa
157–161
Yayın Tarihi
2015-09-14
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

The $k$-rainbow vertex-index of complementary graphs are also studied.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez:A vertex-colored graph $G$ is \emph{rainbow vertex-connected} if two vertices are connected by a path whose internal vertices have distinct colors.
📊
Temel Bulgular & Veri: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.
💡
Sonuç & Katkı:The $k$-rainbow vertex-index of complementary graphs are also studied.
🔬Tür:Makale
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Strong rainbow vertex-connection number · Complementary graph · Rainbow vertex S-tree

Abstract

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.

🔖

Bu Makaleye Atıf Yap

Yanling, F., Wang, Z., Ye, C., Zhang, S. (2015). The rainbow vertex-index of complementary graphs. Journal of Algebra Combinatorics Discrete Structures and Applications, Cilt: 2 Sayı: 3, 157–161. https://doi.org/10.13069/jacodesmath.80607

📄 Tam Metin PDF Okuyucu

📄

PDF görüntüleyici hazırlanıyor...

Kaynakça (11)

  1. J. A. Bondy and U. S. R. Murty, Graph theory, GTM 244, Springer, 2008.
  2. G. Chartrand, G. L. Johns, K. A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem., 133, 85–98, 2008.
  3. G. Chartrand, G. L. Johns, K. A. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks, 54(2), 75–81, 2009.
  4. L. Chen, X. Li and H. Lian, Nordhaus-Gaddum-type theorem for rainbow connection number of graphs, Graphs Combin., 29(5), 1235–1247, 2013.
  5. 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.
  6. X. Cheng and D. Du, Steiner trees in industry, Kluwer Academic Publisher, Dordrecht, 2001.
  7. D. Du and X. Hu, Steiner tree problems in computer communication networks, World Scientific, 2008.
  8. 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.
  9. 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.
  10. 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.
  11. E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly, 63, 175–177, 19