Back to Search
Start Over
Note on the Vertex-Rainbow Index of a Graph.
- Source :
- Bulletin of the Malaysian Mathematical Sciences Society; Sep2021, Vol. 44 Issue 5, p2957-2969, 13p
- Publication Year :
- 2021
-
Abstract
- The k-rainbow index r x k (G) of a connected graph G was introduced in 2010. As a natural counterpart of the k-rainbow index, the concept of k-vertex-rainbow index r v x k (G) of a connected graph G was introduced in 2016. In this paper, we mainly investigate the k-vertex-rainbow index of a connected graph G and obtain some sharp bounds for r v x k (G) . In particular, by using Lovasz Local Lemma and dominating sets, we prove that a connected graph G with n vertices and minimum degree δ has r v x 3 (G) < 11 n δ + 16 . In general, the investigation of k-vertex-rainbow index of a graph may be harder than that of k-rainbow index of a graph. For example, it is noticed that r x 2 (G) ≤ r x 3 (G) ≤ ⋯ ≤ r x n (G) for every connected graph G of order n, but we show that this monotonicity of vertex-rainbow index does not hold in some graph classes by illustrating a counterexample which is a cycle of order n. As a byproduct, we get the exact values of k-vertex-rainbow index for a cycle of order n when k = 3 , n - 4 , n - 3 , n - 2 , n - 1 and n, respectively. [ABSTRACT FROM AUTHOR]
- Subjects :
- DOMINATING set
GRAPH connectivity
Subjects
Details
- Language :
- English
- ISSN :
- 01266705
- Volume :
- 44
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- Bulletin of the Malaysian Mathematical Sciences Society
- Publication Type :
- Academic Journal
- Accession number :
- 151759811
- Full Text :
- https://doi.org/10.1007/s40840-021-01092-0