FORK-DECOMPOSITION OF TOTAL GRAPH OF CORONA GRAPHS

FORK-DECOMPOSITION OF TOTAL GRAPH OF CORONA GRAPHS

A. S. Issacraj, J. P. Joseph

[PDF]

Abstract

Let G = (V;E) be a graph. Then the total graph of G is the graph T(G) with vertex set V (G) [ E(G) in which two elements are adjacent if and only if they are either adjacent or incident with each other. The corona of two graphs G1 and G2, is the graph formed from one copy of G1 and jV (G1)j copies of G2 where the ith vertex of G1 is adjacent to every vertex in the ith copy of G2 and is denoted by G1   G2. Fork is a tree obtained by subdividing any edge of a star of size three exactly once. A de- composition of G is a partition of E(G) into edge disjoint subgraphs. If all the members of the partition are isomorphic to a subgraph H; then it is called a H-decomposition of G: In this paper, we investigate the existence of necessary and su cient conditions for the fork-decomposition of Total graph of certain types of corona graphs which gives a partial solution for the conjecture of Barat and Thomassen [4] for graphs of small edge connectivity.

Keywords

Graph decomposition, Total graph, Corona graph, Fork decomposition.