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/