Isomorphic and Non-Isomorphic Detour Self-Decomposition of Graphs

Abstract

In a connected graph G, between any pair of vertices, say x and y, the longest x - y path is the detour path, and its length is its detour distance D(x, y). A subset S of V (G) where every vertices of G lie on some detour path joining a pair of vertices in S. The minimum cardinality of such S is the detour number dn(G). A decomposition II = (G1, G2, ..., Gn) is said to be detour self-decomposition of G, if dn(G) = dn(G_i), 1 \(\le\) i \(\le\) n. If any pair of subgraphs in II is isomorphic to each other, such II is called an isomorphic detour self-decomposition. If any pair of subgraphs in II is non-isomorphic to each other, such II is called a nonisomorphic detour self- decompoition. Graphs satisfying these decompositions are studied here.