Rainbow connection number of generalized composition

Fendy Septyanto, Kiki Ariyanti

Research output: Contribution to journalArticlepeer-review

Abstract

Let G be a connected graph with [Formula presented]. The rainbow connection number rc(G) is the smallest k for which there is a map [Formula presented] such that any two vertices can be connected by a path whose edge colors are all distinct. The generalized composition [Formula presented] is obtained by replacing each vi with the graph Hi. We prove [Formula presented] if each Hi has at least diam(G)≥4 vertices, improving known upper bounds of Basavaraju et al. and Gologranc et al. (2014). We prove the same result when diam(G) = 3 but with some additional conditions. When diam(G) = 2, we show that the largest possible value of [Formula presented] is related to whether every vertex of G is contained in a triangle or not.

Original languageEnglish
JournalAKCE International Journal of Graphs and Combinatorics
DOIs
Publication statusAccepted/In press - 1 Jan 2018

Keywords

  • Composition
  • Lexicographic product
  • Rainbow connection

Fingerprint Dive into the research topics of 'Rainbow connection number of generalized composition'. Together they form a unique fingerprint.

Cite this