2015/07/06 by Fei Huang, Xueliang Li, Huang, Fei +3
Mathematics · #05C15 #05C35 #05C38 #05C40 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C35 #msc:05C38 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1507.01426
14 pages
arxiv created 2015/07/10 · arxiv updated 2015/07/13
A path in an edge-colored graph is called a proper path if no two adjacent edges of the path are colored with one same color. An edge-colored graph is called k-proper connected if any two vertices of the graph are connected by k internally pairwise vertex-disjoint proper paths in the graph. The k-proper connection number of a k-connected graph G, denoted by pck(G), is defined as the smallest number of colors that are needed in order to make G k-proper connected. For k=1, we write pc(G) other than pc1(G), and call it the proper connection number of G. In this paper, we present an upper bound for the proper connection number of a graph G in terms of the minimum degree of G, and give some sufficient conditions for a graph to have 2-proper connection number two. Also, we investigate the proper connection numbers of dense graphs.