Minimum degree and size conditions for the proper connection number of graphs

摘要

An edge-coloured graph G is called properly connected if every two vertices are connected by a proper path. The proper connection number of a connected graph G, denoted by pc(G), is the smallest number of colours that are needed in order to make G properly connected. van Aardt et al. (2017)gave a sufficient condition for the proper connection number to be at most k in terms of the size of graphs. In this note, our main result is the following, by adding a minimum degree condition: let G be a connected graph of order n, k ≥ 3. If |E(G)|≥(n−m−(k+1−m)(δ+1)2)+(k+1−m)(δ+12)+k+2, then pc(G) ≤ k, where m takes the value k+1 if δ=1 and ⌊kδ−1⌋ if δ ≥ 2. Furthermore, if k=2 and δ=2, pc(G) ≤ 2, except G ∈ {G1, Gn} (n ≥ 8), where G1=K1∨3K2 and Gn is obtained by taking a complete graph Kn−5 and K1∨(2K2) with an arbitrary vertex of Kn−5 and a vertex with d(v)=4 in K1∨(2K2) being joined. If k=2, δ ≥ 3, we conjecture pc(G) ≤ 2, where m takes the value 1 if δ=3 and 0 if δ ≥ 4 in the assumption.