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

Xiaxia Guan, Lina Xue, Eddie Cheng and Weihua Yang

Applied Mathematics and Computation, 2019, vol. 352, issue C, 205-210

Abstract: 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.

Keywords: Proper connection number; Minimum degree; Edge number (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319300797
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:352:y:2019:i:c:p:205-210

DOI: 10.1016/j.amc.2019.01.062

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().