Article ID Journal Published Year Pages File Type
5776782 Discrete Mathematics 2017 5 Pages PDF
Abstract
An edge-coloured graph G is called properly connected if any two vertices are connected by a path whose edges are properly coloured. 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. Our main result is the following: Let G be a connected graph of order n and k≥2. If |E(G)|≥n−k−12+k+2, then pc(G)≤k except when k=2 and G∈{G1,G2}, where G1=K1∨(2K1+K2) and G2=K1∨(K1+2K2).
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , , ,