ON HARMONIOUS COLORINGS OF LEXICOGRAPHIC PRODUCT OF GRAPHS
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Harmonious coloring was rst introduced by Harary and Plantholt in 1982. A harmonious coloring is a proper vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number χH(G) of a graph G is the minimum number of colors needed for any harmonious coloring of G. In this paper, we obtain the harmonious chromatic number of lexicographic product of two graphs G and H, denoted by G[H]. Path and complete graphs are used to obtain extremal properties of graphs and to obtain upper and lower bounds for some graph parameters. Here, we rst consider the graph G[H] where G is the complete graph and H is any simple graph such as the path graph, cycle graph, wheel graph, complete graph, star graph, fan graph or complete bipartite graph. Secondly, we consider G as the path graph and H as the complete graph or path graph respectively. Finally, we consider G as the wheel graph and H as the complete graph.
Abstract
Harmonious coloring was rst introduced by Harary and Plantholt in 1982. A harmonious coloring is a proper vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number χH(G) of a graph G is the minimum number of colors needed for any harmonious coloring of G. In this paper, we obtain the harmonious chromatic number of lexicographic product of two graphs G and H, denoted by G[H]. Path and complete graphs are used to obtain extremal properties of graphs and to obtain upper and lower bounds for some graph parameters. Here, we rst consider the graph G[H] where G is the complete graph and H is any simple graph such as the path graph, cycle graph, wheel graph, complete graph, star graph, fan graph or complete bipartite graph. Secondly, we consider G as the path graph and H as the complete graph or path graph respectively. Finally, we consider G as the wheel graph and H as the complete graph.
참고문헌 (11)
- N. Akgunes, "Some Properties on the Lexicographic Product of Graphs Obtained by Monogenic Semigroups", Journal of Inequalities and Applications, 2013, pp.238~ (2013)[DOI]
- J. A. Bondy, "Graph theory with applications" (1976), MacMillan
- J. P. Georges, "On harmonious coloring of collection of graph", Journal of Graph Theory, 2(2), pp.241~245 (1995)
- R. Hammack, "Handbook of product graph" (2011), CRC press
- J. E. Hopcroft, "On harmonious coloring of graphs", SIAM Jour-nal of Algebraic Discrete Methods, 4, pp.306~311 (1983)
- S. M. Lee, "An upper bound for the harmonious chromatic number of a graph", Journal of Graph Theory, 11, pp.565~567 (1987)
- C. J. H. Mc Diarmid, "Upper bounds for harmonious colorings", Journal of Graph Theory, 15, pp.629~636 (1991)
- J. Vernold Vivin, "Thilagavathi, On harmonious coloring of central graphs", Advances and Applications in Discrete Mathematics, 1(2), pp.17~33 (2008)
- J. Vernold Vivin, "On equitable coloring of corona of wheels", Electronic Journal of Graph Theory and Applications, 4(2), pp.206~222 (2016)
- L. Zhikang, "The harmonious chromatic number of a complete binary and trinary tree", Discrete Mathematics, 118, pp.165~172 (1993)
- P. Zhang, "A kaleidoscopic view of graph colorings, Springer Briefs in Mathematics" (2016), Springer International Publishing