Degree sum conditions for graphs to have proper connection number 2.

MaRDI QIDQ5206337zbMATH OpenFDO

Authors Hong Chang, Zhong Huang, Xueliang Li

Publication date 18 December 2019

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

zbMATH Keywords

bridge-block treedegree sum conditionproper connection coloringproper connection number

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: A path $P$ in an edge-colored graph $G$ is a emph{proper path} if no two adjacent edges of $P$ are colored with the same color. The graph $G$ is emph{proper connected} if, between every pair of vertices, there exists a proper path in $G$. The emph{proper connection number} $pc(G)$ of a connected graph $G$ is defined as the minimum number of colors to make $G$ proper connected. In this paper, we study the degree sum condition for a general graph or a bipartite graph to have proper connection number 2. First, we show that if $G$ is a connected noncomplete graph of order $ngeq5$ such that $d(x)+d(y)geqfracn2$ for every pair of nonadjacent vertices $x,yinV(G)$, then $pc(G)=2$ except for three small graphs on 6, 7 and 8 vertices. In addition, we obtain that if $G$ is a connected bipartite graph of order $ngeq4$ such that $d(x)+d(y)geqfracn+64$ for every pair of nonadjacent vertices $x,yinV(G)$, then $pc(G)=2$. Examples are given to show that the above conditions are best possible.

Recommendations

• Minimum degree condition for proper connection number 2
• Minimum degree conditions for the proper connection number of graphs
• On the minimum degree and the proper connection number of graphs
• Minimum degree and size conditions for the proper connection number of graphs
• Proper connection number 2, connectivity, and forbidden subgraphs

Cited in

(8)

• Degree sums and proper connection number of graphs
• Two sufficient conditions for 2-connected graphs to have proper connection number 2
• On the total proper connection of graphs
• On two conjectures about the proper connection number of graphs
• Minimum degree condition for proper connection number 2
• Proper connection number of bipartite graphs.
• Bounds for proper k-connectivity of complete bipartite graphs
• Proper connection number of random graphs

This page was built for publication: Degree sum conditions for graphs to have proper connection number 2.

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