{Cn, C4}-DECOMPOSITION OF THE LINE GRAPH OF THE COMPLETE GRAPH

{Cn, C4}-DECOMPOSITION OF THE LINE GRAPH OF THE COMPLETE GRAPH

K. Arthi, C. Sankari, R. Sangeetha

[PDF]

Abstract

For given positive integer n   4, let Cn, Kn and L(Kn) respectively denote a cycle with n edges, a complete graph on n vertices and the line graph of the complete graph Kn. For a given graph G, if H1;H2; :::;Hl are the edge disjoint subgraphs such that E(G) = E(H1) [E(H2) [ ::: [E(Hl), then we say that H1;H2; :::;Hl decompose G. If G has a decomposition into copies of H1 and H2 using atleast one of each, then we say that G has a fH1;H2g-decomposition (or) G is fH1;H2g-decomposable. In this paper, it is proved that L(Kn) is fCn;C4g-decomposable.

Keywords

Complete graph, Line graph, Hamilton Cycle, Perfect Matching, Decompo- sition of Graphs.