Rainbow connection number of comb product of graphs
Abstract
An edge-colored graph G is called a rainbow connected if any two vertices are connected by a path whose edges have distinct colors. Such a path is called a rainbow path. The smallest number of colors required in order to make G rainbow connected is called the rainbow connection number of G. For two connected graphs G and H with v ∈ V(H), the comb product between G and H, denoted by G⊳vH, is a graph obtained by taking one copy of G and |V(G)| copies of H and identifying the i-th copy of H at the vertex v to the i-th vertex of G. In this paper, we give sharp lower and upper bounds for the rainbow connection number of comb product between two connected graphs. We also determine the exact values of rainbow connection number of G⊳vH for some connected graphs G and H.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.9
References
L. Accardi, A.B. Ghorbal, and N. Obata, Monotone independence, comb graph, and Bose-Einstein condensation, World Scientific 7(3) (2004), 419–435.
Z.Y. Awanis and A.N.M. Salman, The strong 3-rainbow index of some certain graphs and its amalgamation, Opuscula Mathematica 42(4) (2022), 527–547.
Z.Y. Awanis and A.N.M. Salman, The 3-rainbow index of amalgamation of some graphs with diameter 2, IOP Conference Series: Journal of Physics 1127 (2019), 012058.
Z.Y. Awanis, A. Salman, S.W. Saputro, M. Bača, and A. Semaničová-Feňovčíková, The strong 3-rainbow index of edge-amalgamation of some graphs, Turkish Journal of Mathematics 44 (2020), 446–462.
Z.Y. Awanis, A.N.M. Salman, and S.W. Saputro, The strong 3-rainbow index of edge-comb product of a path and a connected graph, Electronic Journal of Graph Theory and Applications 10 (1) (2022), 33–50.
Z.Y. Awanis, A.N.M. Salman, and S.W. Saputro, The strong 3-rainbow index of comb product of a tree and a connected graph, Journal of Information Processing 28 (2020), 865–875.
S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, Hardness and algorithms for rainbow connection, Journal of Combinatorial Optimization 21 (2011), 330–347.
G. Chartrand, G.L. Johns, K.A. Mc Keon, and P. Zhang, Rainbow connection in graphs, Mathematica Bohemica, 133 (1) (2008), 85–98.
D. Fitriani and A.N.M. Salman, Rainbow connection number of amalgamation of some graphs, AKCE International Journal of Graphs and Combinatorics 13 (1) (2016) 90–99.
T. Gologranc, G. Mekis, and I. Peterin, Rainbow connection and graph products, Graphs and Combinatorics 30 (2014), 591–607.
I.S. Kumala and A.N.M. Salman, The rainbow connection number of a flower (Cm, Kn) graph and a flower (C3, Fn) graph, Procedia Computer Science 74 (2015), 168–172.
S. Klavzar and G. Mekis, On the rainbow connection of Cartesian products and their subgraphs, Discussiones Mathematicae Graph Theory, 32 (4) (2012), 783–793.
X. Li, Y. Shi, and Y. Sun, Rainbow connections of graphs: a survey, Graphs and Combinatorics, 29(1) (2013), 1–38.
X. Li and Y. Sun, Rainbow Connection of Graphs, Springer-Verlag, New York, (2012).
X. Li and Y. Sun, Characterization of graphs with large rainbow connection number and rainbow connection numbers of some graph operations, Discrete Mathematics, to appear.
S. Nabila and A.N.M. Salman, The rainbow connection number of origami graphs and pizza graphs, Procedia Computer Science 74 (2015), 162–167.
D. Resty and A.N.M. Salman, The rainbow connection number of an n-crossed prism graph and its corona product with a trivial graph, Procedia Computer Science 74 (2015), 143–-150.
A.N.M. Salman, Z.Y. Awanis, and S.W. Saputro, Graphs with strong 3-rainbow index equals 2, IOP Conference Series: Journal of Physics 2157 (2022), 012011.
F. Septyanto, K.A. Sugeng, Color code techniques in rainbow connection, Electronic Journal of Graph Theory and Applications 6 (2) (2018), 347–361.
M.A. Shulhany and A.N.M. Salman, The (strong) rainbow connection number of stellar graphs, AIP Conference Proceedings of Mathematics, Science, and Computer Science Education International Seminar 1708, (2016).
B.H. Susanti, A.N.M. Salman, and R. Simanjuntak, The rainbow connection number of some subdivided roof graphs, AIP Conference Proceedings 1707 (2016), 020021.
Susilawati and A.N.M. Salman, Rainbow connection number of rocket graphs, AIP Conference Proceedings 1677 (2015), 030012.
S. Sy, G.H. Medika, and L. Yulianti, The rainbow connection number of fan and sun, Applied Mathematical Sciences 7 (2013), 3155–3159.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.