• Rainbow 2-connectivity of edge-comb product of a cycle and a Hamiltonian graph

• # Fulltext

https://www.ias.ac.in/article/fulltext/pmsc/130/0009

• # Keywords

Cycle; edge-comb product; Hamiltonian graph; rainbow 2-connectivity; rainbow path

• # Abstract

An edge-colored graph $G$ is rainbow $k$-connected, if for every two verticesof $G$, there are $k$ internally disjoint rainbow paths, i.e., if no two edges of each path are colored the same. The minimum number of colors needed for which there exists a rainbow $k$-connected coloring of $G$, $rc_{k} (G)$, is the rainbow $k$-connection number of $G$. Let $G$ and $H$ be two connected graphs, where $O$ is an orientation of $G$. Let $\vec{e}$ be an oriented edge of $H$. The edge-comb product of $G$ (under the orientation $O$) and $H$ on $\vec{e}$, $G^{o} \vartriangleleft_{\vec{e}} H$, is a graph obtained by taking one copy of $G$ and $|E(G)|$ copies of $H$ and identifying the $i$-th copy of $H$ at the edge $\vec{e}$ to the $i$-th edge of $G$, where the two edges have the same orientation. In this paper, we provide sharp lower and upper bounds for rainbow 2-connection numbers of edge-comb product of a cycle and a Hamiltonian graph. We also determine the rainbow 2-connection numbers of edge-comb product of a cycle with some graphs, i.e. complete graph, fan graph, cycle graph, and wheel graph.

• # Author Affiliations

1. Department of Applied Mathematics, Technical University, Košice, Slovak Republic
2. Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jl. Ganesa 10, Bandung 40132, Indonesia

• # Proceedings – Mathematical Sciences

Volume 130, 2020
All articles
Continuous Article Publishing mode

• # Editorial Note on Continuous Article Publication

Posted on July 25, 2019