Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs Original Research Article

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K2,m (m may vary for each edge) by identifying u and v with the two vertices in K2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results. 1. Each non-trivial connected graph G and each supersubdivision graph H∈SS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K2cq+1 and complete bipartite graphs Kmq,nq can be decomposed into edge disjoined copies of H∈SS(G), for all positive integers m,n and c, where q=|E(H)|. 2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous. 3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial. Further, we discuss a related open problem.