Arithmetic Odd Star Decomposition of Graphs

Abstract

Let G = (V, E) be a simple connected graph with p vertices and q edges. If G₁, G₂, …., Gn are connected edge disjoint subgraphs of G with E(G) = E(G₁) \(\cup\)E(G₂)\(\cup\)….\(\cup\)E(G_n), then (G₁, G₂, ……, G_n) is said to be a decomposition of G. A decomposition (G₁, G₂, ……, G_n) of G is said to be continuous monotonic decomposition if each G_i is connected and |E(G_i)| = i for every i = 1, 2, …., n. [1]. In this chapter, we introduced the concept Arithmetic odd star decomposition. A decomposition (G₁, G₂, ……, G_n) of G is said be an Arithmetic decomposition if |E(G_i) = a + (i-1)d, for every I = 1, 2 ……, n and a, d \(\in\) Z. Clearly q=\(\frac{n}{2}\)[2a + (n - 1) d]. If a = 1 and d = 1, then q = \(\frac{n(n+1)}{2}\). In this chapter, we study the graphs with a = 1 and d = 2. Then q = n². That is, the number of edges of G is a perfect square.