Publication: Proper-path colorings in graph operations
0
0
Issued Date
2016
Resource Type
File Type
application/pdf
ISSN
8353026
Other identifier(s)
2-s2.0-85045018656
Rights Holder(s)
Scopus
Bibliographic Citation
Journal of Combinatorial Mathematics and Combinatorial Computing. Vol 98, (2016), p.239-252
Suggested Citation
Andrews E., Laforge E., Lumduanhom C., Zhang P. Proper-path colorings in graph operations. Journal of Combinatorial Mathematics and Combinatorial Computing. Vol 98, (2016), p.239-252. Retrieved from: https://hdl.handle.net/20.500.14740/5881
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. An edge coloring is a proper-path coloring of G if every pair u, v of distinct vertices of G are connected by a proper u - v path in G. The minimum number of colors required for a properpath coloring of G is the proper connection number pc(G) of G. We study proper-path colorings in those graphs obtained by some well-known graph operations, namely line graphs, powers of graphs, coronas of graphs and vertex or edge deletions. Proper connection numbers are determined for all iterated line graphs and powers of a given connected graph. For a connected graph G, sharp lower and upper bounds are established for the proper connection number of (i) the k-iterated corona of G in terms of pc(G) and k and (ii) the vertex or edge deletion graphs G - v and G - e where visa non-cut-vertex of G and e is a non-bridge of G in terms of pc(G) and the degree of v. Other results and open questions are also presented. © 2016 Charles Babbage Research Centre. All rights reserved.