Proper connection number and connected dominating sets

DOI10.1016/J.TCS.2015.06.006MaRDI QIDQ896128zbMATHOpenAlexFDO

Authors Xueliang Li, Meiqin Wei, Jun Yue

Publication date 11 December 2015

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

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

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)

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.

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

Cites work

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

Cited in

(16)

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

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)