# Characterizations of Graphs Having Large Proper Connection Numbers

Chira Lumduanhom; Elliot Laforge; Ping Zhang

Discussiones Mathematicae Graph Theory (2016)

- Volume: 36, Issue: 2, page 439-453
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topChira Lumduanhom, Elliot Laforge, and Ping Zhang. "Characterizations of Graphs Having Large Proper Connection Numbers." Discussiones Mathematicae Graph Theory 36.2 (2016): 439-453. <http://eudml.org/doc/277127>.

@article{ChiraLumduanhom2016,

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.},

author = {Chira Lumduanhom, Elliot Laforge, Ping Zhang},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {edge coloring; proper-path coloring; strong proper-path coloring},

language = {eng},

number = {2},

pages = {439-453},

title = {Characterizations of Graphs Having Large Proper Connection Numbers},

url = {http://eudml.org/doc/277127},

volume = {36},

year = {2016},

}

TY - JOUR

AU - Chira Lumduanhom

AU - Elliot Laforge

AU - Ping Zhang

TI - Characterizations of Graphs Having Large Proper Connection Numbers

JO - Discussiones Mathematicae Graph Theory

PY - 2016

VL - 36

IS - 2

SP - 439

EP - 453

AB - 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.

LA - eng

KW - edge coloring; proper-path coloring; strong proper-path coloring

UR - http://eudml.org/doc/277127

ER -

## References

top- [1] E. Andrews, E. Laforge, C. Lumduanhom and P. Zhang, On proper-path colorings in graphs, J. Combin. Math. Combin. Comput., to appear.
- [2] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. Zbl1199.05106
- [3] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, 5th Edition (Chapman & Hall/CRC, Boca Raton, FL, 2010).
- [4] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC, Boca Raton, FL, 2008). doi:10.1201/9781584888017[Crossref] Zbl1169.05001
- [5] A.B. Ericksen, A matter of security, Graduating Engineer & Computer Careers (2007) 24-28.
- [6] X.L. Li and Y.F. Sun, Rainbow Connections of Graphs (Springer, Boston, MA, 2012). doi:10.1007/978-1-4614-3119-0[Crossref] Zbl1250.05066
- [7] X.L. Li, Y.F. Sun and Y. Zhao, Characterization of graphs with rainbow connection number m − 2 and m − 3, Australas. J. Combin. 60 (2014) 306-313.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.