Subdivisions of Graphs.

Subdivisions of Graphs.

Dissertation

submitted in partial fulfillment of the requirements for the degree of

Master of Technology

by

Namrata P. Tholiya

(Roll no. 06305031) under the guidance of

Prof. Ajit A. Diwan

Department of Computer Science and Engineering Indian Institute of Technology Bombay

2008

Dissertation Approval Sheet

This is to certify that the dissertation entitled

Subdivisions of Graphs

by

Namrata P. Tholiya

(Roll no. 06305031)

is approved for the degree of Master of Technology.

Prof. Ajit A. Diwan (Supervisor)

Prof. Sundar Vishwanathan (Internal Examiner)

Prof. Bharat Adsul (Internal Examiner)

Prof. Murali Srinivasan (Chairperson)

Date:

Place:

v

INDIAN INSTITUTE OF TECHNOLOGY BOMBAY

CERTIFICATE OF COURSE WORK

This is to certify that Ms. Namrata P. Tholiya was admitted to the candidacy of the M.Tech. Degree and has successfully completed all the courses required for the M.Tech. Programme. The details of the course work done are given below.

Sr.No. Course No. Course Name Credits

Semester 1 (Jul – Nov 2006)

1. CS699 Software Laboratory 4

2. CS601 Algorithms & Complexity 6

3. CS615 Formal Specification and Verification of Programming 6 4. CS631 Relational Database Management Systems 6

5. IT608 Data Mining 6

6. CS694 Seminar 4

7. HS699 Communication and Presentation Skills (P/NP) 4 Semester 2 (Jan – Apr 2007)

8. CS640 Natural Computing 6

9. CS613 Functional Programming 6

10. CS616 Parallelizing Compilers 6

11. IT628 ITProject Management 6

12. CS686 Object Oriented Systems 6

Semester 3 (Jul – Nov 2007)

13. CS641 (Advanced) Computer Networks 6

14. CS691 R&D Project 6

M.Tech. Project

15. CS696 M.Tech. Project Stage - I (Jul 2006) 22 16. CS697 M.Tech. Project Stage - II (Jan 2007) 28 17. CS698 M.Tech. Project Stage - III (Jul 2008) 40

I.I.T. Bombay Dy. Registrar(Academic)

Dated:

ix

Acknowledgements

I take this opportunity to express my sincere gratitude towardsProf. Ajit A. Diwan for his constant support and encouragement. His excellent guidance has been instrumental in making this project work a success.

I would like to thankProf. Sundar Vishwanathanfor useful insights and guidance towards the project. I would like to thank members of the Algorithms Group at CSE for their valuable suggestions and helpful discussions.

I would also like to thank myfamily andfriends, who have been a source of encour- agement and inspiration throughout the duration of the project. I would like to thank the entire CSE family for making my stay at IIT Bombay a memorable one.

Namrata P. Tholiya

I. I. T. Bombay June 25^th, 2008

xi

Abstract

For certain graphs H, every graph with minimum degree at least |H| −1 contains a subdivision of graph H. For instance, this relation is true if H is a cycle or a tree.

Through this project, we aim to find the general set of graphs that satisfy this property.

We attempt to do this by proving this condition for different cases of graph H using the general techniques which we have developed. The cases that we study are when H isP53

, P63

, P73

, wheel Wd i.e. Cl∗K1 where l ≥ 3 and caterpillars. Also, we show that every graph with minimum degree d contains a subdivision of a graph H with d+ 1 vertices and 3d−3 edges for d ≥2. In addition, the proofs give us a polynomial time algorithm to find a subdivision of H in a graph satisfying the degree condition.

Contents

Abstract i

1 Introduction 1

2 Mader’s Theorem 3

2.1 Mader’s Theorem . . . 3

2.1.1 Example . . . 5

2.2 Generalization of Mader’s Theorem . . . 6

2.2.1 Example . . . 10

3 External Configuration 13 3.1 Definitions . . . 13

3.1.1 Reduction . . . 13

3.1.2 External Configuration . . . 14

3.1.3 General Arguments . . . 14

3.2 General Technique . . . 15

3.3 Different cases of graph H . . . 16

3.3.1 Edge having d−1 triangles . . . 16

3.3.2 P₅³ (P₃∗K₂) . . . 16

3.3.3 P₆³(P₄∗K₂) . . . 19

3.3.4 Subdivision of wheels W_d where d≥3 . . . 19

3.3.5 Caterpillars . . . 21

4 Internal Configuration 23 4.1 Internal Configuration . . . 23

4.2 General Argument . . . 24

4.3 Good-Configuration . . . 25

4.3.1 Example 1 . . . 25

4.3.2 Example 2 . . . 28

4.4 Bad-Configuration Example . . . 29

4.5 List of good configurations . . . 30

4.6 General Result . . . 30 iii

iv Contents

4.7 Applications of Good-Configurations . . . 35

4.7.1 P₅³ . . . 36

4.7.2 P₆³ . . . 36

4.7.3 P₇³ . . . 37

4.7.4 Wheel . . . 38

4.7.5 2-Caterpillar . . . 39

4.7.6 Path through the vertices . . . 40

5 Conclusion and Future Work 43 5.1 Summary . . . 43

5.2 Future Work . . . 43

References 45

Chapter 1 Introduction

The problem of testing if one graph contains a subdivision of another graph has many applications in graph theory. For example, checking for planarity can be done by testing if a given graph contains a subdivision of graph K₅ or K_3,3. One way to test if a graph G contains a subdivision of a fixed graph H is to choose vertices in G, corresponding to vertices in H and then find internally disjoint paths between specified pairs of vertices in G such that paths to be found in G correspond to edges in H. Finding the paths itself is a difficult problem and the number of choices for the vertices is O(n^d) where n is the number of vertices in the graphGandd is the number of vertices in the graphH. Hence, this makes it as a hard problem.

For certain graphs H, every graph with minimum degree at least |H| −1 contains a subdivision of graph H. Our aim is to find for what kind of graphs H, every graph G with minimum degree at least |H| −1 contains a subdivision of graphH. We also develop a polynomial time algorithm to find a subdivision of H in a graph satisfying the degree condition.

In the report, we study Mader’s theorem [1], proof of which helps us to getdinternally vertex disjoint paths between end vertices of an edge of a graph G with minimum degree at least d. We also see how this helps us to solve one case of graph H whereH is a graph with d−1 triangles having a common edge. Two more cases that we study are whenH is a graph with r edges starting from the same vertex and the i^th edge has d_i−1 triangles, for 1≤ i≤r such that Pr

i=1d_i =d and the another case is whenH is a graph that can be obtained from a tree by adding edges joining one vertex to all the other d vertices [2].

We define the concept of reduction based on the proof of Mader’s theorem and two types of configurations ‘External Configuration’ and ‘Internal Configuration’. Using these two concepts we define two different techniques which help us to prove the property being studied for the different cases of the graph H.

The cases that we study are whenH isP₅³ i.e. P₃∗K₂ whereP₃∗K₂ can be defined as the graph obtained by connecting each vertex of P₃ to each vertex of K₂. Also, the cube

2

of a graphG is the graph obtained by adding edges to G between those pairs of vertices that are at distance 2 or 3 in G. Thus the cube of P₅ is the graph with vertices 0, 1, 2, 3, 4 and two vertices are adjacent iff the difference between them is ≤ 3. This is same as K₅ −e. The property has been proved by Pelikan J [3]. Another cases that we study are when H is P₆³ (P₄∗K₂) andP₇³. Also, we see the proof for subdivision of wheels by our technique. We also prove the property when H is a 2 caterpillar with d+ 1 vertices.

Finally, the general result: Every graph of minimum degree ≥dcontains a subdivision of a graph withd+ 1 vertices and 3d−3 edges ford≥2.

Chapter 2

Mader’s Theorem

We have developed a technique to prove for certain cases of graphH, every graphGhaving minimum degree at least|H|−1 contains a subdivision of graphH. This technique is based on the concept of reduction and configuration. To understand the concept of reduction, which is based on the proof of Mader’s theorem, we need to study the theorem. In this chapter, we study this theorem and then generalize it.

2.1 Mader’s Theorem

Theorem 2.1.1. Let G be a graph with minimum degree at least d. There exists an edge xy in G such that there are d internally vertex-disjoint paths between x and y in G [1].

In order to prove this, we prove a slightly stronger result.

Theorem 2.1.2. Let G be a graph and K be a clique in G such that G−K contains an edge. Suppose that every vertex in G−K has degree at least d in G. Then there is an edge xy in G−K such that there are d internally vertex-disjoint paths between x and y in G.

Proof. Let L be a maximal clique of the graph G containing K. Let uv be an edge in G−K.

The base case is whenG−L does not contain an edge. Hence, eitherG−Lis empty or G−L contains vertices with no edge between them.

1. Consider the case when G−L is empty. In this case, both u and v ∈ L. We are given that every vertex in G−K has degree at least d in G. Hence, L contains at least d+ 1 vertices forming a clique of size at least d+ 1. Hence, the vertexuhas at least d−1 neighbours in L other thanv and all these neighbours belong to Lonly.

Also, v ∈ L. Hence, all these neighbours are adjacent to v, form d−1 internally vertex-disjoint paths. Together with an edge uv, we get d vertex-disjoint paths.

2. Consider the other case when G−L is not empty and contains no edge. Hence, eitheru∈G−Landv ∈Loruandv both∈L. In the former case, there is no edge fromu inG−L. Hence, alldneighbours ofu including v are in Land hence, these

3

4 2.1. Mader’s Theorem are adjacent to the vertexv formingd−1 internally vertex-disjoint paths. Together with an edgeuv, we get dinternally vertex-disjoint paths. Consider the latter case.

Let y₁, y₂,· · ·, y_k be the common neighbours of u and v and let x_k+1,· · ·, xd−1 be the neighbours of u that are not adjacent to v other than v. Since, L is a clique, the verticesx_k+1· · ·, xd−1 are not inL. Each of these vertices has d−1 neighbours in L. Hence, we can find vertices y_k+1,· · ·, yd−1 in L such that y_i ∈ {u, v}, y/ _i 6= y_j for i 6=j and x_i is adjacent to y_i for k+ 1≤ i≤ d−1. Hence, uy_iv for 1≤ i ≤k and ux_iy_iv for k+ 1≤i ≤d−1 are d−1 internally vertex-disjoint paths between uand v. Together with an edgeuv, we get requiredd vertex-disjoint paths.

Consider the case when G−L contains an edge. Let the vertices in L be ordered v1, v2,· · ·, vl. Since, L is a maximal clique, for every vertex v ∈ G−L, there is at least one vertex vi inL which is not adjacent to v. Let π(v) =vi where i is the smallest index such thatv is not adjacent tovi andvi ∈L. Remove the vertex v1 from the clique K. Let (G⁰, K⁰) be the tuple obtained by removing v1. This may change the degree of vertices.

As it is given that the vertex present inG−K has degree at least dinG, we need to add an edge for each vertex v ∈ G⁰−K⁰ and adjacent to v1. Hence, we add an edge vπ(v) for each such v. Hence, we get G⁰ = (G−v1)∪ {vπ(v)|v ∈V(G)\V(L), π(v)> 1} and K⁰ =L−v1. Hence,K⁰ is a clique inG⁰ such that G−L=G⁰−K⁰ contains an edge and every vertex in G⁰−K⁰ has degree at least dinG⁰ since we have added an edgevπ(v) for every v ∈G⁰−K⁰ and adjacent to v₁.

By induction, there is an edge xy in G⁰ −L⁰ such that there are d internally vertex disjoint paths betweenx and y inG⁰ . We need to show that we can modify these paths to getdinternally vertex disjoint paths fromxtoyinG. Any path from xtoythat does not contain any of the edges vπ(v) is a path from x to y in G. All such paths are left unchanged.

Let P₁, P₂,· · ·, P_k be the paths from x to y in G⁰ that contain a vertex in L⁰. Divide each path into two paths where it intersects L⁰. We get 2k disjoint paths out of which k paths start from x and end in L⁰ while remaining k paths start from y and end in L⁰. Edges which lie in clique L⁰ do not belong to these paths. Consider an edge in a path which is of the formvπ(v). we call it as a bad edge. The bad edges for this iteration will have exactly one endpoint in L⁰ . We have got these edges because of the removal of the vertex v₁. InG, v was joined with v₁. After removal of v₁, we have added the edge vπ(v) to satisfy the degree constraint. Hence, we can replace such edges with the original one i.e. vv₁.

In other terms, let s_i be the vertex in L⁰ that is nearest to x in P_i and let t_i be the furthest such vertex. We may assume that eithers_i =t_i or s_it_i is an edge in P_i, since L⁰ is a clique. Lets⁻_i andt⁺_i be the predecessor and successor ofs_i and t_i respectively in the path P_i fromx to y.

LetS ={s₁, s₂,· · ·, s_k} and T ={t₁, t₂,· · ·, t_k}.

LetS⁰ ={s_i ∈S|π(s⁻_i ) = s_i} and T⁰ ={t_i ∈T|π(t⁺_i ) =t_i}.

2.1. Mader’s Theorem 5 Let S⁰ ={v_i1, v_i2,· · ·, v_ip} for i₁ < i₂· · ·< i_p.

Let T⁰ ={v_j1, v_j2,· · ·, v_jp} forj₁ < j₂· · ·< j_p.

If π(v) = v_r, by definition of π(v), vv_i is an edge in G for all i < r. For each vertex S = v_ir ∈ S⁰, replace the edge s⁻s in the path containing s by the edge s⁻v_ir−1, where v_i0 =v₁. Similarly, for each vertext=v_jr ∈T⁰ replace the edgett⁺in the path containing t by the edge v_jr−1t⁺, wherev_j0 =v₁. Delete the edge s_it_i if s_i 6=t_i.

This gives 2k internally vertex disjoint paths inGfrom{x, y}toL, exactlyk of which starts from and end in k distinct vertices in L. If two of these paths end in a common vertex in L, their union is a path from x toy inG. Remaining paths can be obtained by pairing up the paths starting from x arbitrarily with the remaining paths starting from y in L and adding in an edge in L joining their endpoints in L. This gives k internally vertex disjoint paths. Hence, in this way, we get d disjoint paths between x and y in G.

2.1.1 Example

Figure 2.1: Graph G

Consider the figure 2.1. Here, the minimum degree of graph G isd= 3. Hence, there exists an edge xy with 2 disjoint paths including xy. We need to find such edge and required disjoint paths between the edge. Follow the procedure which is used to prove Mader’s theorem, to get the required pair of vertices and the vertex-disjoint paths between them. Table 2.3 shows the step by step procedure.

For example, the first step in the table shows that K ={1}, L= {1,2,3}. Vertex 1 is removed. π(3) = 2 and π(5) = 2. Hence, edges 2−3 and 2−5 are added as shown in second figure of figure 2.1. In this way, finally we get K = {4,5}, L={4,5,6,7} and G−L as empty. We stop at this step i.e. step 5. Table 2.2 gives 3 disjoint paths at the current step. For example, step 5 indicates G−L empty. Hence, 3 disjoint paths are 6-7, 6-4-7, 6-5-7. Step 4 indicates transition from step 5 to step 4 by adding vertex 3. 3 disjoint paths in this step are obtained by replacing bad edge 7−5 by 7−3. Hence, 3 disjoint paths are 6-7, 6-4-7, 6-5-3-7. In this way, final paths are 6-7, 6-4-8-2-7, 6-5-3-7.

6 2.2. Generalization of Mader’s Theorem

Step no K L REM π Added edges Figure

1 {1} {1,2,8} {1} π(3) = 2, π(5) = 2

2-3 and 2-5 2^nd fig of figure 2.1 2 {2,8} {2,8} {2} π(3) = 8,

π(5) = 8, π(7) = 8

3-8, 5-8 and 7-8 1^st fig of figure 2.2(a) 3 {8} {8,3,4} {8} π(5) = 4,

π(7) = 4

5-4 and 7-4 2^nd fig of figure 2.2(a) 4 {3,4} {3,4,5} {3} π(7) = 5 5-7 figure 2.2(b)

5 {4,5} {4,5,6,7} {φ} figure

2.2(b) Table 2.1: Finding K, Land π at each step to get 3 disjoint paths in figure 2.1

(a) (b)

Figure 2.2:

2.2 Generalization of Mader’s Theorem

Mader’s Theorem can be generalized to find the internally vertex-disjoint paths from the root of a rooted tree to remaining vertices of that tree.

If S is a subset of vertices and v a vertex in S then a v −S fan is a collection of (|S| −1)(v−(S\ {v})) paths such that any two paths have only the vertexv in common.

Theorem 2.2.1. Let G be the graph with minimum degree δ(G) = d and let T be any tree withd+ 1 vertices, rooted at a vertex r. Then, there is a subtree T⁰ of G isomorphic to T, with root r⁰ , such that G contains a r⁰−V(T⁰) fans [2].

In order to prove this theorem, we prove slightly stronger result. First we look at some definitions which helps us to prove the theorem.

Definition 2.2.1. A subtree T ofGis consistent with the ordered clique K, for every ver- texv_i ∈V(T)∩V(K), v_i has at most one neighbour inT not contained in{v₁, v₂,· · ·, vi−1}, for 1≤i≤k.

2.2. Generalization of Mader’s Theorem 7 Present Step Current Edges vπ(v) V_i0 vv_i0 Final Edges

5 6-7, 6-4-7, 6-5-7

4 6-7, 6-4-7, 6-5-7 7-5 3 7-3 6-7, 6-4-7, 6-5-3-7 3 6-7, 6-4-7, 6-5-7 7-4 8 7-8 6-7, 6-4-8-7, 6-5-3-7 2 6-7, 6-4-7, 6-5-7 7-8 2 7-2 6-7, 6-4-8-2-7, 6-5-3-7

1 6-7, 6-4-7, 6-5-7 1 6-7, 6-4-8-2-7, 6-5-3-7

Table 2.2: Finding 3 disjoint paths in figure 2.1

Theorem 2.2.2. Let G be a graph and T a rooted tree with d+ 1 vertices. Let K be an ordered clique in G such that every vertex in G−K has degree at least d in G. Let d(T) be the degree of the root. Suppose, G−K contains a vertex of degree at leastd(T). Then there is a subtree T⁰ of G isomorphic to T that satisfies the following properties.

1. The root r⁰ of T⁰ and the neighbours of r⁰ in T⁰ are contained inG−K.

2. T⁰ is consistent with the ordered clique K.

3. G contains a r⁰ −V(T⁰) fan.

Proof. Let the vertices ofT be labeled ast₁, t₂,· · ·, t_d+1 in breadth first order witht_d+1 as a root having degree d(T). Hence, every t_i has exactly one neighbourt_j for i < j for 1 ≤ i≤d+ 1 as shown in second figure of figure 2.3. We call this unique neighbour as parent of t_i. All other neighbours are treated as children of t_i. Let d(T) = t and let d₁,· · ·, d_t be the degrees of root’s children. Let d⁰ = Pt

i=1d_i ≤ d. Let L⁰ = L− {v₁,· · ·, vd−d⁰}.

Therefore, in second figure of figure 2.3 d⁰ = 3 + 1 = 4 and d= 6.

Here, the base case is when G−Ldoes not contain a vertex with degree ≥t. Hence, we can have three possibilities. 1. G−Lis empty. 2. G−Lcontains vertices with degree at least t in G−K. 3. G−L does not contain a vertex of degree at least t in G−K. Consider these cases one by one.

1. Let G−L be empty. As every vertex inG−K has degree at least d in G,G must be a clique of size at leastd+ 1. Also,G−K contains a vertex of degree at least tin G−K. Hence,L−K contains at leastt+ 1 vertices. Hence, we can always choose root and children of the root from G−K. Vertex with largest index in L i.e. v_l corresponds to root. Children of the root can be selected from rightmost vertex in L i.e. vl−1 to left. Hence, t_i of T corresponds to vi+l−d−1. This gives an isomorphism from T to a subtree T⁰ of Gthat satisfies all the properties.

2. LetG−Lcontain vertices of degree at least t in G−K. Among these vertices, we choose maximum degree vertex rinG−Las the root of T⁰. Letc₁, c₂,· · ·, c_s be the neighbours ofr inG−L, where s≤t, are children ofr inT⁰. Since, the degree ofr

8 2.2. Generalization of Mader’s Theorem is at least d in G, r has at least d−s neighbours inL. Also, degree of r is at least t inG−K, we can choose c_s+1,· · ·, c_t fromG−K. Also, d⁰−s≤t−s. Let, these neighbours be in L⁰ and let S = {c_s+1,· · ·, c_t} for the vertex c_i where 1 ≤ i ≤ s, each one has at least d⁰ −t neighbours in V(L⁰)\S. As, V(L⁰) contains at least d⁰ vertices. If it has less than d⁰−t neighbours in V(L⁰)\S then it must have at least s+ 1 neighbours in G−L and at least t+ 1 neighbours in G−K, which is not possible. Because, it contradicts the choice of the root. We might have selected s+ 1 neighbours from G−Linstead of S. Thesed⁰−tneighbours are smaller than c_t in V(L⁰)\S.

So, for eachc_i, 1≤i≤t, there will be at leastd⁰−t neighbours in V(L⁰)\S and if c_i ∈L, it has at leastd⁰−t neighbours which are smaller than c_i inV(L⁰)\S. Here, the order is maintained i.e., selection is not done randomly to avoid the problem.

Pt

i=1di−1 =d₁+d₂· · ·d_t−t=d⁰−t, so, we can always find disjoint subsetsS₁,· · ·S_t of vertices in V(L⁰)\S such that |S_i| = di−1 and every vertex in S_i is adjacent to c_i in T⁰. The remaining d−d⁰ vertices are mapped to the vertices v₁, v₂· · ·vd−d⁰

respectively and add the edges joining these to the vertex in T⁰ corresponding to parent.

To get r−V(T⁰) fan in G, r also has d−t neighbours in V(L)\S. If a vertex v in T⁰ is adjacent to r in G, then rv forms a path from r to v in the fan. Else, we can always choose a vertex w that is adjacent to r such that rwv forms a path in the fan andw does not belong to any other path. So, in this way, we getr−V(T⁰) fans in G.

3. Let G−L be not empty but it does not contain a vertex of degree at least t in G−K. In this case, we select a vertex from G−K of degree at least t in G−K and proceed as above.

The inductive step is when G−Lcontains a vertex of degree at least t inG−L. Let the vertices in L be ordered v₁, v₂,· · ·, v_l. Since, L is a maximal clique, for every vertex v ∈ G−L, there is at least one vertex v_i in L which is not adjacent to v. Let π(v) =v_i where i is the largest index in L such that v is not adjacent to v_i. Remove the vertex v_l from the cliqueK. Let (G⁰, K⁰) be the tuple obtained by removing v_l. This may change the degree of vertices. As it is given that the vertex present in G−K has degree at least d in G, we need to add an edge for each vertex v ∈ G⁰ −K⁰ and adjacent to v_l. Hence, we add an edgevπ(v) for each suchv. Hence, we get

G⁰ = (G−v_l)∪ {vπ(v)|v ∈V(G)\V(L), π(v)6=v_l} and K⁰ =L−v_l.

Hence,K⁰ is a clique inG⁰ such thatG−L=G⁰−K⁰ contains an edge and every vertex in G⁰−K⁰has degree at leastdinG⁰since we have added an edgevπ(v) for everyv ∈G⁰−K⁰ and adjacent to v_l.

2.2. Generalization of Mader’s Theorem 9 By induction hypothesis, there is a tree T⁰ in G⁰ isomorphic to T, that is consistent with the ordered clique L⁰ , such that the root r⁰ ofT⁰ and its children are inG⁰−L⁰ and contains r⁰−V(T⁰) fans.

Remove the vertexv_linLand find the largest index vertex in Lwhich is not adjacent to the vertexv inG−L, which is adjacent tov_l. This is required to maintain consistency with the ordered clique. Because, removing the smallest index vertex may affect the children position and the children may get higher position than its parent, which disobey the property of consistency with the ordered clique referred in definition 2.2.1.

So, here we may assume that for the children of the root, the path in the fan is just the edge in T⁰ . Further, any path in the fan that intersects L⁰ contains at most one edge in L⁰ .

The only edges ofG⁰ that are missing inGare edges of the formvπ(v) forv ∈G⁰−L⁰. If neitherT⁰ nor any of the paths in the r−V(T⁰) fan contain any of these edges, thenT⁰ is the required tree in T. Note that T⁰ is a consistent with any ordered sub-clique of L⁰ having the same ordering of vertices as L⁰, in particular K−v_l. Suppose, in treeT⁰ and in path of the fans contains edges of the form vπ(v). We call such edges as bad edges.

Suppose there is an edge of the form vπ(v) in subtree T⁰. Let π(v) = v_i where v_i is the largest index vertex in L which is not adjacent to v. Hence, v_i ∈L⁰ . We remove the largest index vertex v_l in L. Hence, v must be parent of v_i. In the base case, root of T corresponds to vertex with the largest index in L and ordering is done from rightmost to innermost. Hence, all children of v_i must be in L⁰ and smaller than the index of v_i. This will get clearer in the example given after the proof. Once, it enters the cliqueL, all other children of that vertex remain in the clique only, with leftmost direction in L. Therefore, T⁰ cannot contain any other edge of the form uπ(u) withπ(u) =π(v) =v_i. We call such bad edge in T⁰ as outgoing edge. Suppose a path in the r−V(T⁰) fan contains an edge of the form vπ(v) with π(v) = v_i. If v_i ∈ V(T⁰) then this path must be terminating in v_i. We call this edges bad incoming edges. So, we get a vertex v_i satisfies the following properties.

• There are no bad edges incident with vi.

• There is exactly one bad edge incident with v_i either bad incoming edge or bad outgoing edge.

• There are exactly two bad edges incident withv_i one of which is bad incoming edge and other one is bad outgoing edge.

This completes the proof of theorem 2.2.2. The proof of the theorem 2.2.1 follows from theorem 2.2.2. Hence, the proof.

10 2.2. Generalization of Mader’s Theorem

Figure 2.3:

2.2.1 Example

Consider the graph G and tree T as shown in figure 2.3. We need to find the treeT and r−V(T) fans inG. Hered(t) = 2. The table shows the step by step procedure to remove the vertex and adding corresponding edges to maintain the degree of vertices inG−L.

Figure 2.4:

Figure 2.5:

We stop at step 5 as G−L does not contain a vertex of degree ≥ t(2). Hence, now we will find the subtree T⁰ and r⁰ −V(T⁰) fans where r⁰ is the root of subtree T⁰ graph G⁰ corresponding to that of tree T. As G−L is empty, a vertex t_i of T corresponds to vertex vi+l−d−1 of graph G⁰. Therefore, here root r⁰ is the vertex 11. Hence, we get the tree T⁰ as shown in figure 2.6.

2.2. Generalization of Mader’s Theorem 11

Step no K L REM π Added edges Figure

1 {1} {1,2,5} {5} π(4) = 2, π(6) = 2, π(9) = 1, π(10) = 2

2-4, 2-6, 1-9 and 2-10 1^st fig of figure 2.4

2 {1,2} {1,2,7,8,9} {9} π(6) = 7, π(3) = 8

3-8 and 6-7 2^nd fig of figure 2.4 3 {1,2,7,8} {1,2,7,8} {8} π(6) = 1,

π(3) = 7, π(10) = 7

3-7, 1-6 and 7-10 1^st fig of figure 2.5 4 {1,2,7} {1,2,7,6} {6} π(3) = 2,

π(4) = 1, π(11) = 1

2-3, 1-4 and 1-11 2^nd fig of figure 2.5 5 {1,2,7} {1,2,7,3,

4,10,11}

{φ} figure 2.6

Table 2.3: FindingK, L and π at each step to get 3 disjoint paths in figure 2.3

Figure 2.6:

Going back to step 4 from step 5, there are two bad edges 11−1 and 2−3 and removed vertex is 6. So, replacing bad edge with actual one, we will get the edges 11−6 and 6−3.

So, the final path is 11−6−3 and the another path is obtained by joining 1 and 2 to get 11−2−1−3 shown in figure 2.7. Hence, going back to step 3,2 and 1, there are no bad edges. Hence, the final paths are as shown in figure 2.7.

Let say if we remove the vertex in ascending order i.e., from the smallest index inK, moving from the base case to the previous graph, if we find the bad edge in a tree as shown in figure 2.8(a), then replacing bad edge with the original one, we get parent index small than that of its children. This may result some inside portion of the tree in a clique and their children outside the clique, in some later stage. This creates a problem and also does not satisfy the constraint. Hence, the removal of a vertex is done from rightmost i.e., with the largest index vertex in L i.e., v_l.

If there are more than two incoming or outgoing edges, then also it creates problem in a selection of tree. Consider the figure 2.8(b). There are two outgoing edges. Replacing

12 2.2. Generalization of Mader’s Theorem

Figure 2.7:

(a) If smallest index vertex removed

(b) More than two bad edges present

Figure 2.8:

them by actual edges, shift both to the same point which creates a problem in forming a tree i.e., tree gets destroy. Hence, the removal of vertex is done with the largest index in Li.e. the last vertex inLand also, while selecting edges, if an edge enters the clique, care is taken so that remaining part of tree remain in a clique only. Till there are no vertex outside the clique, a vertex is not selected from the clique. This gives the required result.

Corollary 1. Let G be a graph with minimum degree δ(G)≥d. Then, for all 1≤r ≤d, there is a vertex v in G and a set S of r neighbours of v, such that v is d-linked to S in G i.e., there are d internally vertex disjoint paths with exactly d_i of them end in v_i.

This is the specific case of theorem 2.2.1.

Chapter 3

External Configuration

In this chapter, we extend the technique used to prove Mader’s theorem and define the concepts of reduction and internal configuration. Using these concepts, we develop a general technique which helps us to prove the property “Every graph G with minimum degree at least |H| −1 contains a subdivision of the graph H” for the different cases of the graph H. The cases that we study are whenH isP₅³,P₆³, wheel W_d i.e., C_d∗K₁ for d≥3 and caterpillars.

To understand the technique which we have developed, first we study the following definitions and concepts and then see the technique.

3.1 Definitions

3.1.1 Reduction

LetGbe a graph andK be an ordered clique of the graphG. Letv₁, v₂· · ·v_kbe the vertices of the ordered clique K. LetL=v₁, ..., v_k, v_k+1, ..., v_l be a maximal clique containing K. As we have seen in the proof of Mader’s theorem in section 2.1, π(v) = v_i where i is the smallest index inL such that v_i is not adjacent to the vertex v and v ∈G−L. Let G⁰ be a new graph obtained by removing vertex v₁ from the clique L of the tuple (G, K) and K⁰ = L−v₁. This might change the degree of the vertices present in G⁰ −K⁰. Hence, an edge vπ(v) is added for each v ∈ G⁰ −K⁰ and v ∈ adj(v₁) so that the degree of the vertices in G⁰−K⁰ remain unchanged. Hence, we can define reduction as the process of adding vertices v_k+1· · ·v_l in the cliqueK of the graph G and then removing a vertex v₁ from the clique K such that the degree of vertices in G−Lremains unchanged.

Definition 3.1.1. (Reduction) If (G⁰, K⁰) is a tuple obtained by applying reduction on the tuple (G, K) so that either G⁰ =G and K⁰ =K+v₁ or G⁰ = (G−v₁)∪ {vπ(v)|v ∈ V(G)\V(L), π(v) > 1} and K⁰ = K −v₁, then we can say that (G⁰, K⁰) is obtained by applying reduction on the tuple (G, K).

13

14 3.1. Definitions

3.1.2 External Configuration

Definition 3.1.2. A configurationC is an arbitrary graphH(C)with non-negative integer weights assigned to the vertices of H(C).

The non-negative weight assigned to the vertex is denoted by w(v). In this chapter, we refer external configuration as ‘configuration’.

Definition 3.1.3. Let G be a graph and K be an ordered clique in G. We say that the pair (G, K) contains a given configuration C if

1. G−K contains a subdivision H⁰ of H(C). Let v⁰ denote the vertex in H⁰ corre- sponding to the vertex v in H(C).

2. For every vertex v of H(C), there are w(v) paths from v⁰ to K in G that pairwise intersect in v⁰ and are internally disjoint from H⁰ and K also. Denote this set of paths by P(v).

3. For different vertices u and v of H(C), the set of paths P(u)∪P(v) are internally disjoint.

(a) C1 (b) (G, K)

Figure 3.1: ConfigurationC₁ and Tuple (G, K)

3.1.3 General Arguments

Let G be a graph and K be an ordered clique of the graph G. Let (Gi, Ki) be a tuple obtained by applying successivelyireductions on the tuple (G, K). Let (Gi+1, Ki+1) be a tuple obtained by applying reduction on the tuple (Gi, Ki). Hence, eitherGi+1 =Gi−v1

orGi+1 =Gi and Ki =Ki+1−vl.

Lemma 3.1.1. If (G_i+1, K_i+1)contains an arbitrary configurationC and ifG_i is obtained by adding a vertex to G_i+1, then (G_i, K_i) will also contain the same configuration.

Proof. LetP₁, P₂, .., P_kbe the paths inP(v) for a vertexv inH(C). Let the endpoint ofP_i inK_i+1 bet_i and lett⁻_i be the vertex that precedest_i inP_i. LetT⁰ ={t_i ∈T|π(t⁻_i ) = t_i}.

LetT⁰ ={v_i1,· · ·v_ip} where i₁ <· · ·< i_p.

3.2. General Technique 15 Ifπ(v⁰) =v_r, by definition ofπ(v⁰), v⁰v_i is an edge in G_i for all i < r. For each vertex v_ir ∈T⁰, replace the edge t⁻t in the path containingt by the edge t⁻v_ir−1 where v_i0 =v₁. Hence, P(v) to the cliqueK_i from the vertex v ∈G_i−K_i remains same as inG_i+1−K_i+1. Hence, we get the same configuration. Hence, we can say that ifG_i is obtained by adding a vertex to G_i+1, thenG_i will contain the same configuration as that of G_i+1.

Lemma 3.1.2. Let (Gi+1, Ki+1) contain an arbitrary configuration C. If Ki is obtained by removing a vertex vl from Ki+1 and if S is the set of vertices {v| Some path in P(v) terminates in vl}, then (Gi, Ki) will contain a configuration obtained by adding a vertex v, corresponding to the vertex vl, and, joining it to vertices of S, reducing their weights by 1 and assigning maximum of all these weights in C to the new vertex vl.

Proof. Sis the set of vertices{v|Some path ofP(v) terminates inv_l}. Hence, on removing v_l, the number of paths entering the clique K_i starting from vertices in S will reduce by 1. Let w be the maximum of the weights assigned to the vertices in C. Then there will be at least wvertices present in the clique K_i. Also, v_l was in the cliqueK_i+1. Hence,v_l is connected to all the vertices present in the clique K_i. As there are at least w vertices, v_l will have weight at least w. Hence, the proof. Also, G_i−K_i will contain a subdivision of the graph obtained by adding a new vertex v and joining it to vertices in S.

Corollary 2. Let (G_i+1, K_i+1) contain an arbitrary configuration C. If K_i is obtained by removing a vertex v₁ from K_i+1 and if v_l is not the endpoint of any path in P(v) for any v in C, then (G_i, K_i) will also contain the same configuration.

Proof. If S is the set of vertices {v| Some paths in P(v) terminates in v_l}, then S = φ.

Hence, from lemma 4.2.2, weights of the vertices in the configurationCremain unchanged.

Therefore, we will get the same configuration.

Corollary 3. Let (G_i+1, K_i+1) contain an arbitrary configuration C where C contains at least two vertices with maximum weight. If K_i is obtained by removing a vertex v_l from K_i+1 and v_l is the endpoint of a path in P(v) for exactly one vertex v in C, then (G_i, K_i) will also contain the same configuration.

Proof. If S is the set of vertices {v| Some paths of P(v) terminates in v_l}, then |S| = 1.

Letw is the maximum weight. From lemma 4.2.2, weight of the vertexv inS will reduce by 1 and v_l will get assigned the maximum weightw. At least one vertex in K_i is not the endpoint of any path in P(v). Continuing the path from v_l to this vertex, gives the set of paths P(v) in G_i. Hence, we will get the same configuration.

3.2 General Technique

We have to prove that for certain graphs H, every graph with minimum degree at least

|H| −1 contains a subdivision ofH. For proving this property for a particular case of H,

16 3.3. Different cases of graph H let the number of vertices in the graph H be d+ 1. Let G be a graph having minimum degree at leastd. LetK be an ordered clique of the graphG. The following steps describe our technique which is based on the above definitions and arguments.

1. Choose a set S_c(H) of configurations that depend on H such that the only con- figuration in S_c(H) that can be contained in (G, φ) is H with 0 weights to the vertices.

2. Start with (G, φ).

3. Apply the reduction on (G, φ) till the reduced graph G_t is a clique.

4. Gt will be a clique of size at least d+ 1. Hence, show that Gt contains one of the configurations inSc(H).

5. Prove if (G_i+1, K_i+1) contains one of the configurations in S_c(H) then (G_i, K_i) also contains one of the configurations in S_c(H) where 1 ≤i≤t−1.

6. Hence, (G, φ) contains one of the configuration in S_c(H). The only possible config- uration that can be contained in (G, φ) is H with 0 weights to the vertices i.e., the subdivision of H, as K isφ.

3.3 Different cases of graph H

We now prove the property being studied for different cases of graphHusing the technique defined in the previous section.

3.3.1 Edge having d − 1 triangles

We have to prove that ifHis a graph obtained by addingd−1 triangles having a common edge, then every graph Ghaving minimum degree at least d contains a subdivision ofH.

There exists a proof given by Mader in section 2.1.

Configurations

For this case, the configurations are as shown in figure 3.2.

3.3.2 P

(P

∗ K

)

We have to prove that if H is the maximal planar graph with 5 vertices i.e. P₅³(P₃∗K₂), then every graph G having minimum degree at least 4 contains a subdivision of H.

Configurations

Different configurations that are possible for this case are as shown in figure 3.3. We denote the set of these configurations by S_c(H) where S_c={C₁,· · ·C₇}.

3.3. Different cases of graph H 17

(a) C1 (b) C2

(c) C₃ (d)C₄

Figure 3.2: Configurations forH

(a) C1 (b) C2 (c) C3

(d)C4 (e) C5

(f) C₆ (g) C₇

Figure 3.3: Configurations forP₅³

Theorem 3.3.1. Let G be a graph with minimum degree d ≥ 4, then G contains a subdivision of a graph P₅³.

Proof. 1. Let K be a clique of a graph G represented as a tuple (G, K). Initially, assume K as empty set. Let L be a maximal ordered clique containing K. Let (G_t, K_t) be a tuple obtained by applying successively t reductions on the tuple (G, K) so that G_t is a clique.

2. Since, degree of every vertex inG_t−K_t is 4, G_t will be a clique of size at least 5.

3. If G_t−K_t contains one vertex v, then it will have 4 (v, K_t) paths. Hence, it will containC₁ configuration. IfG_t−K_tcontains 2 verticesuandv, then there will be 3 (u, K_t) and 3 (v, K_t) paths. Hence, (G_t, K_t) will containC₂ configuration. Similarly

18 3.3. Different cases of graph H for other cases, we can prove that (G_t, K_t) will contain one of the configurations in S_c(H).

4. Assuming that (G_i+1, K_i+1) contains any of the configurations in S_c(H), we need to prove that (G_i, K_i) will also contain one of the configurations in S_c(H).

5. Let (G_i+1, K_i+1) contain a configuration C fromS_c(H). IfG_i is obtained by adding a vertex to G_i+1, then from lemma 4.2.1, we can show that we will get the similar configuration.

6. Consider the other possibility whenG_i =G_i+1 andK_i =K_i+1−v_l. LetS be a set of vertices{v|Some path inP(v) terminates inv_l}. Now, we will see the configuration obtained for all possible cases ofC and S.

(a) If S =φ, from corollary 2, we will get the same configuration.

(b) If |S| = 1 and C ∈ {C₂· · ·C₇}, then from corollary 3, we will get the similar configuration.

From lemma 4.2.2, we can see that following configurations are obtained for remaining cases of C and S.

(c) C =C₁, S ={x₁} ⇒C₂. (d) C =C₂, S ={x₁, x₂} ⇒C₃.

(e) C =C₃, S ={x₁, x₂} ∨ {x₂, x₃} ∨ {x₁, x₃} ⇒C₄. (f) C =C₃, S ={x₁, x₂, x₃} ⇒C₅.

(g) C = C₄, S = {x₁, x₂} ∨ {x₂, x₄} ⇒ C₄. In this case, when x₅ joins to x₂ and x₄, from lemma 4.2.2, x₂ will have 0 path entering the clique, x₄ will have one path while x₅ will have 2 paths entering the clique K_i. We will get the similar configuration by removing the edge x₂−x₃ and contracting the edge x₁−x₃. (h) C =C4, S ={x1, x4} ⇒C5.

(i) C =C4, S ={x1, x2, x4} ⇒C5.

(j) C =C₅, S ={x₁, x₂} ∨ {x₂, x₄} ⇒C₆. (k) C =C₅, S ={x₁, x₂, x₄} ⇒C₇.

(l) C =C₆, S ={x₁, x₅} ⇒C₇.

7. Hence, (G, K) will contain one of these configurations. As K isφ, the only possible configuration is the final configurationC₇ i.e. subdivision of H.

3.3. Different cases of graph H 19

3.3.3 P

(P

∗ K

)

We have to prove that if H is P₆³, then for every graph G having minimum degree at least 5 contains a subdivision of H.

Configurations

(a) C1 (b) C2 (c) C3 (d)C4

(e) C5 (f) C6 (g) C7

(h)C8 (i) C9 (j) C10

Figure 3.4: Configurations forP₆³

The configurations for this case are as shown in the figure 3.4. We denote the set of these configurations by Sc(H) whereSc(H) ={C1,· · ·C10}.

Theorem 3.3.2. If H is P₆³ (P₄ ∗K₂), then every graph G having minimum degree at least 5 contains a subdivision of H.

Proof. The proof of this is similar toP₅³. Let (G_i+1, K_i+1) be a tuple obtained by applying reduction on the tuple (G_i, K_i) whereK_iis a clique of a graphG_i. If (G_i+1, K_i+1) contains one of the configuration C in S_c(H) and S is the set of vertices {v| Some path in P(v) terminates inv_l}whereK_i =K_i+1−v_l, then possible configurations that can be contained in (G_i, K_i) for all possible cases of C and S are as shown in table 3.1. We can see that the remaining configurations in table 3.1 from 3 to 19 are obtained from lemma 4.2.2.

3.3.4 Subdivision of wheels W

where d ≥ 3

We have to prove that if H is a wheel W_d i.e. C_d∗K₁ whered≥3, then for every graph G with minimum degree at least d contains a subdivision ofH.

20 3.3. Different cases of graph H

Sr.no. C S New Configuration

1 C ∈ {C₁,· · ·C₁₀} φ C from corollary 2 2 C ∈ {C₂,· · ·C₁₀} |S|= 1 C from corollary 3

3 C₁ x₁ C₂

4 C₂ {x₁, x₂} C₃

5 C₃ {x₁, x₂} ∨ {x₂, x₃} ∨ {x₁, x₃} C₄

6 C₃ {x₁, x₂, x₃} C₅

7 C₄ {x₁, x₂} ∨ {x₂, x₄} C₄

8 C₄ {x₁, x₄} C₅

9 C₄ {x₁, x₂, x₄} C₅

10 C₅ {x₁, x₂} ∨ {x₂, x₄} C₆

11 C₅ {x₁, x₂, x₄} C₇

12 C₆ {x₁, x₅} C₇

13 C₆ {x₄, x₅} C₈

14 C₆ {x₁, x₄, x₅} C₉

15 C₇ {x₁, x₄} ∨ {x₁, x₅} ∨ {x₄, x₅} C₉

16 C₇ {x₁, x₄, x₅} C₁₀

17 C₈ {x₁, x₆} ∨ {x₁, x₅} C₉

18 C₈ {x₁, x₅, x₆} C₉

19 C₉ {x₁, x₆} C₁₀

Table 3.1: Configurations obtained forP₆³

Theorem 3.3.3. If G is a simple graph with d≥3, then G has a subdivision of W_d i.e., C_d∗K₁.

There exists a proof by Galen E Turner [4]. The proof by our technique is given below.

Configurations

The configurations are as shown in figure 3.5. We denote the set of these configurations byS_c(H).

Proof. The proof of this is similar to P₃ ∗K₂. Let (G_i+1, K_i+1) be a tuple obtained by applying reduction on the tuple (G_i, K_i) whereK_i is a clique of a graphG_i. If (G_i+1, K_i+1) contains one of the configurationsC in S_c(H) and S is the set of vertices {v| Some path inP(v) terminates in v_l}where K_i =K_i+1−v_l, then possible configurations that can be contained in (G_i, K_i) for all possible cases ofC and S are as shown in table 3.2. For the configurationsC_r⁰ andC_r⁰⁰, one ofv₁/v_rhasd−r−1 paths and the other hasd−r. Ifw₁is the weight assigned to the vertexv₁ andw_r to the vertexv_r, then{w₁, w_r}={d−r−1, d−r}.

Hence, rather than having two different configurations, we can have a single configuration with{w₁, w_r}={d−r−1, d−r}. We can see that the remaining configurations in table

3.3. Different cases of graph H 21

(a) C1 (b) C2 (c) Cr (d) C_r⁰ (e) C_r⁰⁰

(f) C_d−2 (g)C_d−2⁰ (h) C_d−2⁰⁰ (i) C_d−1 (j) C_d−1⁰

(k)Cf₁ (l) C_f⁰

1 (m) Cf₂ (n) Cf

Figure 3.5: Configurations forW_d whered ≥3 3.2 from 3 to 25 are obtained from lemma 4.2.2.

3.3.5 Caterpillars

A caterpillar graph is a tree such that if all leaf vertices and their incident edges are removed, the remainder of the graph forms a path. We have to prove that ifH is a graph obtained by addingd_i−1 triangles on every edgeiin the caterpillar graph, then for every graphGhaving minimum degree at leastdcontains a subdivision of H. The proof of this is similar to the above proof.

Proving above result automatically implies for a graph with d+ 1 vertices such that there exists a path between r + 1 vertices and i^th edge has d_i −1 triangles such that 1≤i≤r and Pr

i=1d_i =d.

Configurations

(a) C1 (b) C2 (c) C3 (d) C4

Figure 3.6: Configurations

The configurations are as shown in figure 3.6. We denote the set of these configurations

22 3.3. Different cases of graph H

Sr.no. C S New Configuration

1 C∈ {C₁,· · ·C_f} φ C from corollary 2 2 C∈ {C₂,· · ·C_f} |S|= 1 C from corollary 3

3 C₁ {v₁} C₂

4 C₂ {v₁, v₂} C_r

5 C_r {v₁, v_r} C_r⁰

6 C_r {v, v₁} ∨ {v, v_r} C_r+1

7 C_r⁰ {v₁, v_r} C_r⁰⁰

8 C_r⁰ {v, v₁} C_r+1⁰

9 C_r⁰ {v, v_r} C_r+1

10 C_r⁰⁰ {v₁, v_r} C_r⁰⁰

11 C_r⁰⁰ {v, v₁} ∨ {v, v_r} C_r+1⁰

12 C_d−2 {v₁, v_d−2} C_d−2⁰

13 C_d−2 {v, v₁} ∨ {v, v_d−2} C_d−1 14 C_d−2⁰ {v₁, v_d−2} C_d−2⁰⁰

15 C_d−2⁰ {v, v₁} C_d−1⁰

16 C_d−2⁰ {v, v_d−2} C_d−1

17 C_d−2⁰⁰ {v₁, v_r} C_d−2⁰⁰

18 C_d−2⁰⁰ {v, v₁} ∨ {v, v_d−2} C_d−1⁰

19 C_d−1 {v₁, v_d−1} C_f2

20 C_d−1 {v, v₁} ∨ {v, v_d−1} C_f1

21 C_d−1⁰ {v₁, v_d−1} C_f2

22 C_d−1⁰ {v, v₁} C_f⁰

1

23 C_d−1⁰ {v, v_d−1} C_f1 24 C_f1 ∨C_f⁰

1 {v₁, v_d} C_f

25 C_f2 {v, v_d} C_f

Table 3.2: Configurations obtained for C_d∗K₁ where d≥3

byS_c(H).