Publication: Characterizations of graphs having large proper connection numbers
0
0
Issued Date
2016
Resource Type
File Type
application/pdf
ISSN
12343099
Other identifier(s)
2-s2.0-84962799563
Rights Holder(s)
Scopus
Bibliographic Citation
Discussiones Mathematicae - Graph Theory. Vol 36, No.2 (2016), p.439-453
Suggested Citation
Lumduanhom C., Laforge E., Zhang P. Characterizations of graphs having large proper connection numbers. Discussiones Mathematicae - Graph Theory. Vol 36, No.2 (2016), p.439-453. doi:10.7151/dmgt.1867 Retrieved from: https://hdl.handle.net/20.500.14740/5874
Author(s)
Abstract
Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u-v path of length d(u,v), then P is a proper u, - v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u, - v path in G, and c is a strong proper-path coloring if every two vertices u and v are connected by a proper u - v geodesic in G. The minimum number of colors required for a proper-path coloring or strong proper-path coloring of G is called the proper connection number pc(G) or strong proper connection number spc(G) of G, respectively. If G is a nontrivial connected graph of size m, then pc(G) ≤ spc(G) ≤ m and pc(G) = m or spc(G) = m if and only if G is the star of size m. In this paper, we determine all connected graphs G of size m for which pc(G) or spc(G) is m - 1, m - 2 or m - 3.