Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 7s (2024) 574 https://internationalpubls.com On Decomposing Any Graph G into VDT Graphs M. Sivasankari 1 , M. Yamuna 2 1 Department of Mathematics, SAS, VIT, Vellore, Tamil Nadu, India. Email: sivasankari.2019@vitstudent.ac.in 2 Department of Mathematics, SAS, VIT, Vellore, Tamil Nadu, India. Email: myamuna@vit.ac.in Corresponding author: myamuna@vit.ac.in Article History: Received: 04-06-2024 Revised: 03-07-2024 Accepted: 30-07-2024 Abstract: This article targets to develop an iterative procedure for decomposing any random graph G into subgraphs 1 2 kH ,H ,...,H such that each Hi is a VDT graph, 1 ≤ i ≤ k. This iterative technique is based on developing a rooted tree, and then decompose G into VDT graphs using backtracking. Keywords: Decomposition, BFS, Tree, Domination. 1. Introduction In the literature of graph theory, graph decomposition is one interesting problem where any graph is decomposed into subgraphs [1]. Researchers have made different contributions to this domain. Samuel Issacraj et al. studied forks, trees formed by subdividing a star of size three once, providing conditions for fork-decomposition of some total graphs [2]. Ganguly et al. demonstrated the decomposition of the real line R into complementary sets with empty ratio sets [3]. Hasan et al. explored properties of stiff modules in QT AG modules [4]. Bhatt et al. computed a rank-1 tensor approximation [5]. Gao et al. applied graph theory to crystal structure prediction [6]. Guo et al. characterized hereditary vertex decomposable graphs, including well-known examples [7]. Bonizzoni et al. developed efficient algorithms for hypergraph decomposition [8]. Grohe et al. contributed to graph minor decomposition [9]. Mesady et al. [10] studied edge decomposition on circulant graphs while Dac et al. [11] explored a conjecture on digraph cycles. Most researchers attempt to decompose specific kind of graphs. The questions that arise is “Is it possible to decompose any given graph G? Can we decompose a random graph G into predefined type of graphs”. In this article we develop an iterative technique to decompose any random graph into a specific type of graphs called VDT graphs. 2. Preliminary Note For any set S of vertices in G, the induced subgraph ⟨S⟩ is the maximal subgraph of G with vertex set S. A tree is a connected graph without cycles. Forks are trees formed by subdividing a star of size three exactly once. A path is a sequence of connected vertices. A comb is a graph shaped like a comb with a central path and hanging edges. Graph decomposition involves dividing a graph into smaller graphs such that every edge appears in exactly one of the smaller graphs. A dominating set D of G is a set of vertices of G such that every vertex in V – D is adjacent to a vertex in D. If D has the smallest possible cardinality of any dominating set of G, then D is called a minimum dominating set. The cardinality of any minimum dominating set for G is called a domination number of G and is denoted by γ(G). A γ − set denotes a dominating set for G with minimum cardinality [12]. In this Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 7s (2024) 575 https://internationalpubls.com article we have developed an iterative procedure for decomposing any random graph G into subgraphs 1 2 kH ,H ,...,H such that each Hi is a VDT graphs, 1 ≤ i ≤ k. 3. VDT Graph A graph G is said to be VDT graph if G has at least one γ–set D such that ⟨V –D⟩ is a tree. We shall denote such graphs as VDT graphs and the γ – set D such that ⟨V – D⟩ is a tree as a VDT set.  The graphs in Figure 1 is an example of VDT and non - VDT graph. VDT graph Non – VDT graph Fig 1. VDT and non-VDT graphs Now let us prove few observations to decompose G into VDT graphs. In all these observations, let G be a VDT graph and D a VDT set  for G. Theorem 1 D contains all the pendant vertices. Proof If possible, let v ∈ D such that v is a pendant vertex. Let u be a support vertex with respect to D. We know that both u, v cannot be contained in D since D′ = D − v itself is a γ - set for G, a contradiction to our assumption that D is a VDT set  . So, if v ∈ D, u  D, implies ⟨V − D⟩ is disconnected, a contradiction to our assumption that D is a VDT set  . Hence D contains all the pendant vertices of G. Theorem 2 For any support vertex u ∈ G, |N(u) ∩ X | = 1, where X is the set of all pendant vertices of G. Proof If possible, let u ∈ G such that |N(u) ∩ X | ≥ 2. Without loss of generality let |N(u) ∩ X | = k, k ≥ 2. Let X1 ⊆ X = 1 2 k{v , v ,..., v }be the set of all pendant vertices adjacent to u. Then ⟨V − D⟩ is a disconnected graph with at least k + 1 components, a contradiction to our assumption that D is a VDT set  with respect to G, which implies |N(u) ∩ X | = 1. Theorem 3 The corona graph G ◦ K1 is a VDT graph if G is a tree. Proof Let G be a tree. Consider T ◦ K1. Let T ◦ K1 = Y1 ∪ Y2 = 1 2 k{u ,u ,..., u }∪ 1 2 k{v , v ,..., v } where ⟨Y1⟩ is a tree and ⟨Y2⟩ is a null graph. From Theorem 1, we know that D contains all the pendant vertices, implies Y2 ∈ D. Also, by Theorem 2, we know that every ui, 1 ≤ i ≤ k, is a support vertex. By Theorem 2, we know that Y1 does not belong to D. Also, ⟨Y1⟩ is a tree, implies G ◦ K1 is a VDT graph if G is tree. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 7s (2024) 576 https://internationalpubls.com In general G ◦ K1 need not be a VDT graph for any graph G. The graph in Figure 2 is an example of corona graph that is not VDT. From these observations we know that there exist a family of graphs T ◦ K1 that are VDT for any tree T. For our purpose of decomposition, we shall choose the VDT trees P2, P4, comb graphs. Now we continue further to determine a decomposition of any given graph into P2, P4, comb graphs. Fig 2. Non VDT Corona Graph 4. VDT Graph Decomposition Let G be any graph with n vertices. For our iteration procedure let us consider the graph G in Figure 3 as illustration. Fig 3. Graph G for VDT graph decomposition Step 1 Determine the rooted tree T1 for G from any arbitrary vertex using BFS algorithm. For our example the rooted tree is seen in Figure 4. Step 2 Vertex Labelling of Tree T1 Let us label the tree T1 obtained by BFS algorithm. 1. Label the root vertex as v11. 2. Label the vertices in level 2 as v21, v22, ..., v2r2 from left to right. 3. Label the vertices in level 3 as v31, v32, ..., v3r3 from left to right. 4. Continue this pattern and label the vertices at level k as vk1, vk2, ..., vkrk from left to right. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 7s (2024) 577 https://internationalpubls.com Fig 4. Tree T1 using BFS algorithm Step 3 Include the remaining edges to the tree T1 as seen in Figure 5. Fig 5. T1 with remaining edges added Step 4 Edge Labelling Any edge e = ij ik(v , v ) is labelled as ij ike . Note that here i represents the level of the vertices. 11 32e denotes an edge between vertices 11v and 32v , the edge is between vertices in level 1 and level 3. The partial structure of the tree T1 labelling is as seen in Figure 6. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 7s (2024) 578 https://internationalpubls.com Fig 6. Labelling of T1 Step 5 Starting from vertex k1v trace a longest possible path by back tracking along the tree T1 by choosing a new edge each time. Label the resulting path as k1 k1 k1P : v , PRED(v ), k1 11PRED(PRED(v )), ..., v . Let us now attempt to include edges to the path k1P to generate a comb graph if possible. Step 6 Let ijv be any random vertex in path k1P . a. 1. Include a new edge ij ike to k1P where k is the smallest possible value, i r i 2 k v   (if it exists) such that ijv is adjacent to ikv . Include ikv and ij ike to k1P . Else 2. Choose the smallest possible p, i r i + 1 2 p v   (if it exists) such that ijv is adjacent to i + 1 pv . Include i + 1 pv and ij i + 1 pe to k1P . Else 3. Choose the smallest possible q, i r i - 1 2 q v   (if it exists) such that vij is adjacent to i - 1 qv . Include i - 1 qv and ij i - 1 qe to k1P . Repeat 1, 2 or 3 for every vertex in k1P starting from k1v . If there is at least one vertex say ijv for which step 6a fails, we terminate step 6a. Else we continue step 6 until we reach vertex 11v . If step 6a is true for every vertex in k1P , then we include w vertices and w edges to k1P generated by step 6a where |w| = |V ( k1P )|, 1 ≤ w ≤ k. The resulting graph is a comb say k1 1(P K ) . Else b. Retain the path k1P . Step 7 Starting from vertex k2v trace a longest path by back tracking along the tree T1 by choosing a new edge each time. Label the resulting path as k2 k2 k2 k2P : v , PRED(v ), PRED(PRED(v )), ij ..., v . Repeat step 6a for path k2P to generate a comb k2 1(P K ) if it exists or retain k2P (Step 6b). Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 7s (2024) 579 https://internationalpubls.com Step 8 Repeat step 5 for every kiv , k3 i r   to generate a sequence 1 2 rX , X ,..., X where ki 1 i ki P K or X P     Fig 7. Iteration 1 Step 9 Repeat Step 5 to Step 8 for all the vertices in the level k – 1, k – 2, . . ., 2. Executing step 5 to step 8 once, we finally generate a sequence of subgraphs  1 2 sH , H , ..., H where each ki 1 i ki P K or H P     . For our example iteration 1 is given in Figure 7. If all the edges of G are covered then terminate the procedure here. Else Step 10 Let 1 2 sL G – {H H ... H }.    If L is a connected graph, then repeat step 1 to step 9. Else if L is disconnected graph, then repeat step 1 to step 9 on all the X components say 1 2 xG , G , ..., G . For our example the graph G is disconnected as seen in Figure 8. Summarizing we repeat BFS algorithm multiple times to generate a sequence of trees 1 2 zT , T , ..., T as seen in Figure 9. From these trees we then decompose graph G into subgraphs 1 2 sH , H , ..., H where each ki 1 i ki P K or H P     . Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 7s (2024) 580 https://internationalpubls.com Fig 8. Subgraphs of graph G for VDT graph decomposition Fig 9. Rooted trees T2, T3, T4 using Step 1 Figure 10 shows the decomposition for our example in iteration 2. Fig 11. Iteration 2 Step 11 If step 10 covers all the edges of G, then terminate the iterative procedure. Else repeat step 1 to step 9 on all the resulting graphs until all the edges of G are covered. Our example terminates in iteration 3 as seen in Figure 11 and 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20H ,H , H , H , H , H , H , H , H , H , H , H , H , H , H , H , H , H ,H ,H are the decompositions of graph G. Hence, we conclude the following theorem. Theorem 4 Given any graph G, there exist a decomposition 1 2 sH , H , . . . , H such that each iH , 1 i s  is either comb graph or path. Theorem 5 Given any graph G there exist a decomposition  1 2 kH , H , ..., H for G such that each iH is a VDT graph. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 7s (2024) 581 https://internationalpubls.com Proof Let G be any given graph. Determine a decomposition 1 2 sX H , H , . . . , H for G using Theorem 4. We know that each iH is either a comb or a path. If iH is a comb then it is a VDT graph. If iH is a path nP then we continue as follows. Fig 12. Iteration 3 i. Let n 1 1 2 2 3 n 1 n 1 nP v e v e v ... v e v   where n 1e 0mod3  . Let us decompose nP into paths 1 2 k1P , P , ..., P where 1 1 1 2 2 3 3 4 2 4 4 5 5 6 6 7P v e v e v e v ; P v e v e v e v ;  … k1 n 3 n 3P v e  n 2 n 2 n 1 n 1 nv e v e v .    ii. If n 1e 1mod3  then let us decompose nP into paths 1 2 k2P , P , ..., P where 1 1 1 2 2 3P v e v e v 3 4 2 4 4 5 5 6 6 7 k2 n 1 n 1 ne v ; P v e v e v e v ; .... P v e v .   iii. If n 1e 2mod3  let us decompose nP into paths 1 2 k3P , P , ..., P where 1 1 1 2 2 3 3P v e v e v e 4 2 4 4 5 5 6 6 7 k3 2 n 5 n 5 n 4 n 4 n 3 n 3 n 2 k3 - 1 n 2 n 2v ; P v e v e v e v ; .... P v e v e v e v ; P = v e           n 1 k3 n 1 n 1 nv ; P = v e v .    Hence from the decomposition X we obtain a new decomposition Y =  1 2 kH , H , ...,H , k s  such that each iH is either 2 4 n 1P , P , P K , implies G can be decomposed into VDT graphs. 5. Conclusion Graph decomposition has several significant applications. It reveals patterns and connectivity between vertices within graphs by revealing hierarchical relationships and substructures. Different methods and algorithms exist for graph decomposition. According to the graph, each approach offers unique insights and advantages. In this article, we presented an algorithm for determining a decomposition for any given graph into comb graphs, P4 and P2 which are VDT graphs. This algorithm can be used to study graph decomposition in a variety of contexts. It can help identify and understand the underlying structures of complex networks. Furthermore, it can be used to solve problems related to graph decomposition in an efficient manner. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 7s (2024) 582 https://internationalpubls.com References [1] Narsingh Deo, Graph theory with Applications to Engineering and Computer Sciences, Prentice Hall India, 2016. [2] Samuel Issacraj, A and Paulraj Joseph.J, Fork decomposition of some total graphs, Palestine journal of mathematics, Vol. 12(Special Issue II) (2023), 65–72. [3] Ganguly.D. K. and Dhananjoy Halder, On decomposition of the real line in terms of ratio sets, Palestine journal of mathematics, Vol. 7(2) (2018), 624–627. [4] Ayazul Hasan, Jules Clement Mba and Rafiquddin, Recent decomposition results on QT AG-modules, Palestine journal of mathematics, Vol. 7(2) (2018), 633–640. [5] Vineet Bhatt and Kumar. S., A cas aided survey of CP decomposition and rank-1 approxition of a 3rd-order tensor, Vol. 3(2) (2014), 299–319. [6] Hao Gao, Junjie Wang, Yu Han and Jian Sun, Enhancing crystal structure prediction by decomposition and evolution schemes based on graph theory, Fundamental Research, Vol 1(4) (2021), 466-471. [7] Jin Guo, Meiyan Li and Tongsuo Wu, A new view toward vertex decomposable graphs, Discrete Mathematics, Vol 345(9) (2022), 112953. [8] Paola Bonizzoni and Gianluca Della Vedova, An algorithm for the modular decomposition of hypergraphs, Journal of Algorithms, Vol 32(2) (1999), 65-86. [9] Martin Grohe, Ken-ichi Kawarabayashi, and Bruce Reed, A simple algorithm for the graph minor decomposition logic meets structural graph theory, Proceedings of the 2013 Annual ACM SIAM Symposium on Discrete Algorithms (SODA), (2013), 414- 431. [10] A. El-Mesady, Y.S. Hamed, H. Shabana, On the decomposition of circulant graphs using algorithmic approaches, Alexandria Engineering Journal, Vol 61(10) (2022) 8263-8275. [11] Ngo Dac Tan, A decomposition for digraphs with minimum outdegree 3 having no vertex disjoint cycles of different lengths, Discussiones Mathematicae Graph Theory, Vol 43 (2023), 573 – 581. [12] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.