## {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.