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

Abstract

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

How to cite

top

Chira 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. [1] E. Andrews, E. Laforge, C. Lumduanhom and P. Zhang, On proper-path colorings in graphs, J. Combin. Math. Combin. Comput., to appear. Zbl1347.05055
  2. [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. [3] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, 5th Edition (Chapman & Hall/CRC, Boca Raton, FL, 2010). 
  4. [4] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC, Boca Raton, FL, 2008). doi:10.1201/9781584888017[Crossref] Zbl1169.05001
  5. [5] A.B. Ericksen, A matter of security, Graduating Engineer & Computer Careers (2007) 24-28. 
  6. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.