DECOMPOSITION OF JUMP GRAPH OF PATHS

International Conference on Algebra and Discrete Mathematics (ICADM-2020) on 24 to 26, June 2020, Department of Mathematics, DDE, Madurai Kamaraj University, Tamil Nadu, India. International Journal of Computer Science (IJCS) Published by SK Research Group of Companies (SKRGC)

Abstract

The Jump graph J(G) of a graph G is the graph whose vertices are edges of G and two vertices of J(G) are adjacent if and only if they are not adjacent in G. Equivalently complement of line graph L(G) is the Jump graph J(G) of G. In this paper, we give necessary and sufficient condition for the decomposition of Jump graph of paths into various graphs such as paths, cycles, stars, complete graphs and complete bipartite graphs.

References

[1] G.T.Chartrand, H.Hevia, E.B.Jarette, and M.Schulty, Subgraph distance in graphs defined by edge transfer, Discrete Mathematics, 170 (1997) 63-79.

[2] F. Harary, Graph Theory, Addison - Wesley, Reading M.A, (1969).

[3] C. Lin and T. W. Shyu, A necessary and sufficient condition for the star de- composition of complete graphs, Journal of Graph Theory, 23 (1996) 361-364.

[4] C. Sunil Kumar, On P4 decomposition of Graphs, Taiwanese Journal of Mathematics, Vol 7 No:4 Dec(2003) 657-664.

[5] Tay- Woei Shyu, Decomposition of complete graphs into paths and stars, Discrete Mathematics, 310 (2010) 2164-2169.

[6] Tay-Woei Shyu, Decomposition of complete graphs into cycles and stars,Graphs and Combinatorics, 29 (2013) 301-313.

Keywords

decomposition of graph, line graph, jump graph.