Proper connection number and connected dominating sets

DOI10.1016/J.TCS.2015.06.006zbMATH Open1333.05227arXiv1501.05717OpenAlexW1929795508MaRDI QIDQ896128FDOQ896128

Authors: Xueliang Li, Meiqin Wei, Jun Yue 

Publication date: 11 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The proper connection number $pc(G)$ of a connected graph $G$ is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of $G$ is connected by at least one path in $G$ such that no two adjacent edges of the path are colored the same, and such a path is called a proper path. In this paper, we show that for every connected graph with diameter 2 and minimum degree at least 2, its proper connection number is 2. Then, we give an upper bound $frac3ndelta+1-1$ for every connected graph of order $n$ and minimum degree $delta$. We also show that for every connected graph $G$ with minimum degree at least $2$, the proper connection number $pc(G)$ is upper bounded by $pc(G[D])+2$, where $D$ is a connected two-way (two-step) dominating set of $G$. Bounds of the form $pc(G)leq4$ or $pc(G)=2$, for many special graph classes follow as easy corollaries from this result, which include connected interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs and chain graphs, all with minimum degree at least $2$. Furthermore, we get the sharp upper bound 3 for the proper connection numbers of interval graphs and circular arc graphs through analyzing their structures.

Full work available at URL: https://arxiv.org/abs/1501.05717

Recommendations

• Proper connection numbers of complementary graphs
• Proper connection number 2, connectivity, and forbidden subgraphs
• Upper bounds of proper connection number of graphs
• The domination number of connected graphs
• scientific article; zbMATH DE number 3873384
• Rainbow connection number and connected dominating sets
• Rainbow connection number and connected dominating sets
• Connected domsaturation number of a graph
• The connected hub number and the connected domination number
• Proper connection number of random graphs

zbMATH Keywords

diameterproper-path coloringconnected dominating setproper connection number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Cites Work

• Graph theory
• Rainbow connections of graphs
• Rainbow connection number and connected dominating sets
• Rainbow connection in graphs
• Rainbow connection in 3-connected graphs
• Proper connection of graphs

Cited In (16)

• Minimum degree condition for proper connection number 2
• On the (di)graphs with (directed) proper connection number two
• Two sufficient conditions for 2-connected graphs to have proper connection number 2
• On two conjectures about the proper connection number of graphs
• The \((k,\ell )\)-proper index of graphs
• Some results on the total proper \(k\)-connection number
• The \(k\)-proper index of graphs
• Some upper bounds for the 3-proper index of graphs
• On the (di)graphs with (directed) proper connection number two
• On strong proper connection number of cubic graphs
• Optimal proper connection of graphs
• The optimal proper connection number of a graph with given independence number
• Proper connection number 2, connectivity, and forbidden subgraphs
• Proper connection number of bipartite graphs
• Graphs with (strong) proper connection numbers \(m - 3\) and \(m - 4\)
• Proper connection number of graph products

This page was built for publication: Proper connection number and connected dominating sets

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