2016/11/29 by Hong Chang, Chang, Hong, Zhong Huang +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO #msc:05C07 #msc:05C15 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1611.09500
11 pages
arxiv created 2016/11/29 · arxiv updated 2016/11/30
A path P in an edge-colored graph G is a proper path if no two adjacent edges of P are colored with the same color. The graph G is proper connected if, between every pair of vertices, there exists a proper path in G. The 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 n≥ 5 such that d(x)+d(y)≥ (n)/(2) for every pair of nonadjacent vertices x,y∈ V(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 n≥ 4 such that d(x)+d(y)≥ (n+6)/(4) for every pair of nonadjacent vertices x,y∈ V(G), then pc(G)=2. Examples are given to show that the above conditions are best possible.