Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs |
| |
Authors: | G Sethuraman P Selvaraju |
| |
Institution: | aSchool of Mathematics, Anna University, Chennai, 600 025, India;bDepartment of Mathematics, SSN College of Engineering, Chennai, 603 110, India |
| |
Abstract: | 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 HSS(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 HSS(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. |
| |
Keywords: | Graph labeling α -Valuation Strongly n-elegant Cordial Decomposition of graph Supersubdivision of graphs |
本文献已被 ScienceDirect 等数据库收录! |
|