Distance proper connection of graphs

MaRDI QIDQ6274820zbMATH OpenFDO

Authors Xueliang Li, Colton Magnant, Meiqin Wei, Xiaoyu Zhu

Publication date 21 June 2016

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: Let $G$ be an edge-colored connected graph. A path $P$ in $G$ is called a distance $ell$-proper path if no two edges of the same color appear with fewer than $ell$ edges in between on $P$. The graph $G$ is called $(k,ell)$-proper connected if every pair of distinct vertices of $G$ are connected by $k$ pairwise internally vertex-disjoint distance $ell$-proper paths in $G$. For a $k$-connected graph $G$, the minimum number of colors needed to make $G$ $(k,ell)$-proper connected is called the $(k,ell)$-proper connection number of $G$ and denoted by $p{c}_{k,ell}(G)$. In this paper, we prove that $p{c}_{1,2}(G)leq5$ for any $2$-connected graph $G$. Considering graph operations, we find that $3$ is a sharp upper bound for the $(1,2)$-proper connection number of the join and the Cartesian product of almost all graphs. In addition, we find some basic properties of the $(k,ell)$-proper connection number and determine the values of $p{c}_{1,ell}(G)$ where $G$ is a traceable graph, a tree, a complete bipartite graph, a complete multipartite graph, a wheel, a cube or a permutation graph of a nontrivial traceable graph.

This page was built for publication: Distance proper connection of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6274820)