Geodesic
Characterizations of Graphs Having Large Proper Connection Numbers
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 439-453.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: edge coloring, proper-path coloring, strong proper-path coloring 
@article{DMGT_2016_36_2_a14,
     author = {Lumduanhom, Chira and Laforge, Elliot and Zhang, Ping},
     title = {Characterizations of {Graphs} {Having} {Large} {Proper} {Connection} {Numbers}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {439--453},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a14/}
}
TY  - JOUR
AU  - Lumduanhom, Chira
AU  - Laforge, Elliot
AU  - Zhang, Ping
TI  - Characterizations of Graphs Having Large Proper Connection Numbers
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 439
EP  - 453
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a14/
LA  - en
ID  - DMGT_2016_36_2_a14
ER  - 
%0 Journal Article
%A Lumduanhom, Chira
%A Laforge, Elliot
%A Zhang, Ping
%T Characterizations of Graphs Having Large Proper Connection Numbers
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 439-453
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a14/
%G en
%F DMGT_2016_36_2_a14
Lumduanhom, Chira; Laforge, Elliot; Zhang, Ping. Characterizations of Graphs Having Large Proper Connection Numbers. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 439-453. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a14/

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

[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

[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

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