The Vertex-Rainbow Index of A Graph
The k-rainbow index rxk(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduce the concept of k-vertex-rainbow index rvxk(G) in this paper. In this paper, sharp upper and lower bounds of rvxk(G) are given for a...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2016-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1887 |
| _version_ | 1797704420370153472 |
|---|---|
| author | Mao Yaping |
| author_facet | Mao Yaping |
| author_sort | Mao Yaping |
| collection | DOAJ |
| description | The k-rainbow index rxk(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduce the concept of k-vertex-rainbow index rvxk(G) in this paper. In this paper, sharp upper and lower bounds of rvxk(G) are given for a connected graph G of order n, that is, 0 ≤ rvxk(G) ≤ n − 2. We obtain Nordhaus-Gaddum results for 3-vertex-rainbow index of a graph G of order n, and show that rvx3(G) + rvx3(Ḡ) = 4 for n = 4 and 2 ≤ rvx3(G) + rvx3(Ḡ) ≤ n − 1 for n ≥ 5. Let t(n, k, ℓ) denote the minimal size of a connected graph G of order n with rvxk(G) ≤ ℓ, where 2 ≤ ℓ ≤ n − 2 and 2 ≤ k ≤ n. Upper and lower bounds on t(n, k, ℓ) are also obtained. |
| first_indexed | 2024-03-12T05:20:10Z |
| format | Article |
| id | doaj.art-cd2bcea5c0934da6bede64732c66cf9c |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:20:10Z |
| publishDate | 2016-08-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-cd2bcea5c0934da6bede64732c66cf9c2023-09-03T07:47:21ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922016-08-0136366968110.7151/dmgt.1887dmgt.1887The Vertex-Rainbow Index of A GraphMao Yaping0Department of Mathematics Qinghai Normal University Qinghai 810008, ChinaThe k-rainbow index rxk(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduce the concept of k-vertex-rainbow index rvxk(G) in this paper. In this paper, sharp upper and lower bounds of rvxk(G) are given for a connected graph G of order n, that is, 0 ≤ rvxk(G) ≤ n − 2. We obtain Nordhaus-Gaddum results for 3-vertex-rainbow index of a graph G of order n, and show that rvx3(G) + rvx3(Ḡ) = 4 for n = 4 and 2 ≤ rvx3(G) + rvx3(Ḡ) ≤ n − 1 for n ≥ 5. Let t(n, k, ℓ) denote the minimal size of a connected graph G of order n with rvxk(G) ≤ ℓ, where 2 ≤ ℓ ≤ n − 2 and 2 ≤ k ≤ n. Upper and lower bounds on t(n, k, ℓ) are also obtained.https://doi.org/10.7151/dmgt.1887vertex-coloringconnectivityvertex-rainbow s-treevertex- rainbow indexnordhaus-gaddum type |
| spellingShingle | Mao Yaping The Vertex-Rainbow Index of A Graph Discussiones Mathematicae Graph Theory vertex-coloring connectivity vertex-rainbow s-tree vertex- rainbow index nordhaus-gaddum type |
| title | The Vertex-Rainbow Index of A Graph |
| title_full | The Vertex-Rainbow Index of A Graph |
| title_fullStr | The Vertex-Rainbow Index of A Graph |
| title_full_unstemmed | The Vertex-Rainbow Index of A Graph |
| title_short | The Vertex-Rainbow Index of A Graph |
| title_sort | vertex rainbow index of a graph |
| topic | vertex-coloring connectivity vertex-rainbow s-tree vertex- rainbow index nordhaus-gaddum type |
| url | https://doi.org/10.7151/dmgt.1887 |
| work_keys_str_mv | AT maoyaping thevertexrainbowindexofagraph AT maoyaping vertexrainbowindexofagraph |