2015/04/09 by Fei Huang, Xueliang Li, Huang, Fei +3 · 1 citation
Computer Science · Mathematics · #05C15 #05C35 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO #msc:05C15 #msc:05C35 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1504.02414
12 pages
openalex publication_date 2015/04/09 · arxiv created 2015/04/29 · arxiv updated 2015/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A path P in an edge-colored graph G is called a proper path if no two adjacent edges of P are colored the same, and G is proper connected if every two vertices of G are connected by a proper path in G. The proper connection number of a connected graph G, denoted by pc(G), is the minimum number of colors that are needed to make G proper connected. In this paper, we investigate the proper connection number of the complement of graph G according to some constraints of G itself. Also, we characterize the graphs on n vertices that have proper connection number n-2. Using this result, we give a Nordhaus-Gaddum-type theorem for the proper connection number. We prove that if G and G are both connected, then 4≤ pc(G)+pc(G)≤ n, and the only graph attaining the upper bound is the tree with maximum degree Δ=n-2.