Maximum and minimum degree in iterated line graphs by Manu Aggarwal A thesis submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Master of Science Auburn, Alabama August 3, 2013 Keywords: iterated line graphs, maximum degree, minimum degree Approved by Dean Ho man, Professor of Mathematics Chris Rodger, Professor of Mathematics Andras Bezdek, Professor of Mathematics Narendra Govil, Professor of Mathematics Abstract In this thesis we analyze two papers, both by Dr.Stephen G. Hartke and Dr.Aparna W. Higginson, on maximum [2] and minimum [3] degrees of a graph G under iterated line graph operations. Let k and k denote the minimum and the maximum degrees, respectively, of the kth iterated line graph Lk(G). It is shown that if G is not a path, then, there exist integers A and B such that for all k>A, k+1 = 2 k 2 and for all k>B, k+1 = 2 k 2. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 An elementary result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Maximum degree growth in iterated line graphs . . . . . . . . . . . . . . . . . . 10 4 Minimum degree growth in iterated line graphs . . . . . . . . . . . . . . . . . . 26 5 A puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 iii List of Figures 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 : Disappearing vertex of degree two . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 : Disappearing leaf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.6 : When CD is not a single vertex . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.7 : When CD is a single vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 iv 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.6 : When CD is not a single vertex . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.7 : When CD is a single vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.8 : Path from wB to vB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.9 : Path from wB to vB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.10 : vB+1n 1 2NhCB+1i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.11 : vB+1n 1 2CB+1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 v Chapter 1 Introduction The line graph L(G) of a graph G is the graph having edges of G as its vertices, with two vertices being adjacent if and only if the corresponding edges are adjacent in G. Please note that all graphs in this discussion are simple. We restrict our discussion to connected graphs. Refer to [4] for basic de nitions of graph theory. One of the most important resutls in line graphs has been by Beineke, who provides in [1], a new characterization of line graphs in terms of nine excluded subgraphs, also unifying some of the previous characterizations. We provide only the theorem here without the proof. Figure 1.1 Theorem 1.1. A graph G is a line graph of some graph if and only if none of the nine graphs in Figure 1.1 is an induced subgraph of G. 1 The iterated line graph is de ned recursively as Lk(G) = L(Lk 1(G)) where L0(G) = G. Let and be the maximum and the minimum degree, respectively, of a graph G. We denote the minimum degree of Lk(G) by k and the maximum degree by k. Hartke and Higgins [2] show that if G is not a path, then, there exists an integer A, such that, k+1 = 2 k 2 for all k > A. Using similar concepts, they show in [3] that there exists an integer B such that k+1 = 2 k 2 for all k > B. Rather than focusing on the vertices of minimum and maximum degrees, they observe the behavior of particular kinds of regular subgraphs, of which, the vertices of maximum and minimum degrees form a special case. However, this proves only the existence and the question of tight bounds of A and B is still open. We now de ne some notation which will be used throughout the proofs. Neighborhood of a vertex v, denoted by N(v), is de ned as the set of all vertices adjacent to v. Then, if S is a set of vertices of G, we use the following notation:- 1. N(S) = Sv2S N(v) 2. N[S] = N(S)[S 2. NhSi= N(S)nS We would rst prove a result in Chapter 2 which was used in [2] and [3] without proof. Then, the result for the maximum degree is proved in Chapter 3 and for the minimum degree is proved in Chapter 4. 2 Chapter 2 An elementary result In this chapter we will prove that for most graphs, minimum degree is unbounded under line graph iteration. Notice that, if G is not a path, then k is de ned for all k. As mentioned in the introduction, all graphs under consideration are simple and we restrict out discussion to connected graphs. A leaf of a graph is a vertex of degree 1. Lemma 2.1. If there exists an integer A such that A > 2, then k > 2 for all k > A. Moreover, k is a strictly increasing sequence for all k A, and hence lim k!1 k =1. Proof: Clearly, the minimum possible value of k+1 is 2 k 2. Now, A > 2 2 A > A + 2 2 A 2 > A: But 2 A 2 is the minimum possible value of A+1, hence, A+1 > A which implies A+1 > 2. Now, let A+i > 2 for some i. Then, following similar set of equations, A+i+1 > A+i and A+i+1 > 2. It follows inductively that k+1 > k > 2 for all k > A and therefore k is a strictly increasing sequence. This also implies that the minimum degree is unbounded under line graph operation. Lemma 2.2. Let sk be the number of vertices of degree 1 in Lk(G). Then, fskg is non- increasing. 3 Proof: Every vertex of degree 1 in a graph L(G) corresponds to an edge in G which is inci- dent with exactly one edge. So, a leaf in Lk(G) corresponds to one leaf in Lk 1(G). Also, a leaf in G will give a single leaf under the line graph operation. Lemma 2.3. Let G be a graph which is not a path or a cycle. If = 2 then lim k!1 k =1. Proof: A vertex of degree 2 in L(G) will correspond to an edge in G which is incident with exactly two edges. It can either be a leaf or an edge in a path or cycle as shown in the e e Figure 2.1 Figure 2.1. But as = 2, G has no leaf. Hence, we only need to consider vertices of degree 2 in G. Now, as G is not a path or a cycle, there exists at least one vertex, say v, of degree greater than 2. Also, as = 2, G is not a K1;3. Let u be a vertex of degree 2 in G. As G is connected, there is a path from u to v, say P0 = (u = y01;y02;:::;y0n = v), as shown in Figure 2.2. Now, P0 induces a path P1 = (y11;y12;:::;y1n 1) in L(G) where dL(G)(y1j) 2 for 1 j n 2 and dL(G)(y1n 1) 3. Now, let Pi = (yi1;yi2;:::;yin i) with dLi(G)(yij) 2 for 1 j n i 1 and dLi(G)(yin i) 3. Then Pi induces Pi+1 in Li+1(G) such that Pi+1 = (yi+11 ;yi2 + 1;:::;yi+1n i 1). 4 y01 = u dG(y01) = 2 dG(y02) ? 2 dG(y03) ? 2 dG(y0n?2) ? 2 y0n = v dL(G)(y11) ? 2 dL(G)(y12) ? 2 dL(G)(y13) ? 2 dL(G)(y1n?2) ? 2 dL(G)(y1n?1) ? 3 dLi(G)(yi1) ? 2 dLi(G)(yi2) ? 2 dLi(G)(yi3) ? 2 dLi(G)(yin?i?1) ? 2 dLi(G)(yin?i) ? 3 dLi+1(G)(yi+11 ) ? 2 dLi+1(G)(yi+12 ) ? 2 dLi+1(G)(yi+13 ) ? 2 dLi+1(G)(yi+1n?i?1) ? 3 dLn?2(G)(yn?21 ) ? 2 dLn?2(G)(yn?22 ) ? 3 dLn?1(G)(yn?11 ) ? 3 dG(y0n) ? 3 dG(y0n?1) ? 2 Figure 2.2: Disappearing vertex of degree two Now, for 1 j k 2, dLi(G)(yi2) 2 dLi(G)(yi2) +dLi(G)(yi1) 2 + 2 dLi(G)(yi2) +dLi(G)(yi1) 2 2 + 2 2 dLi+1(G)(yi+11 ) 2: 5 and, for j = k 1, dLi(G)(yik 1) 2 dLi(G)(yik 1) +dLi(G)(yik) 2 + 3 dLi(G)(yik 1) +dLi(G)(yik) 2 2 + 3 2 dLi+1(G)(yi+1k 1) 3: Also, jPi+1j = jPij 1. Applying inductively, Pn 1 = (yn 11 ) where dLn 1(G)(yn 11 ) 3 as shown in Figure 2.2, and we get that every vertex of degree 2 will de nitely ?disappear? after n 1 line graph iterations. Doing this for every vertex of degree 2, there exists an integer N such that LN(G) has no vertex of degree 2, hence N 3 and we are done from Lemma 2.1. Lemma 2.4. If G is neither a path, cycle nor a K1;3, then the minimum degree is unbounded under line graph iteration and moreover, there exists an integer A such that lim k!1 k =1 for all k>A. Proof: From Lemma 2.1 it is su cient to show that for any graph G, as speci ed, there exists an integer A such that A > 2. As G is neither a path, cycle nor a K1;3, there exists an edge, say e, such that, e = xz is incident with at least three edges. Let (G) = 1. From Lemma 2.2, the number of leaves is a non-increasing sequence over line graph iteration. Moreover, a leaf in L(G) corresponds to exactly one leaf in G. So it would su ce to consider line graph operation on leaves of G and show that it disappears at some iteration. Let v be incident on a leaf of G such that dG(v) = 1. Then, as G is connected, there is a path P0 = (v = y01;y02;:::;y0n 1 = x;y0n = z) from v to the edge e such that dG(y0i ) 2 for 2 i n 2, as shown in Figure 2.3. Now, P0 induces a path, say P1, in L(G) such that P1 = (y11;y12;:::;y1n 1) where y1j corresponds to the edge y0jy0j+1 2E(G) for 2 j n 1, as shown in Figure 2.3. Now, as xz is incident with at least three edges, dG(y1n 1) 3. Also, 6 y01 = v dG (y01 ) = 1 dG (y02 ) ? 2 dG (y03 ) ? 2 dG (y0n?2) ? 2 y0n?1 = x y0n = z e dL(G)(y11 ) ? 1 dL(G)(y12 ) ? 2 dL(G)(y13 ) ? 2 dL(G)(y1n?2) ? 2 y1n?1 = xz dL(G)(y1n?1) ? 3 dLi(G)(yi1) ? 1 dLi(G)(yi2) ? 2 dLi(G)(yi3) ? 2 dLi(G)(yin?i?1) ? 2 dLi(G)(yin?i) ? 3 dLi+1 (G)(yi+11 ) ? 1 dLi+1 (G)(yi+12 ) ? 2 dLi+1 (G)(yi+13 ) ? 2 dLi+1 (G)(yi+1n?i?1) ? 3 dLn?4(G)(yn?41 ) ? 1 dLn?4(G)(yn?42 ) ? 2 dLn?4(G)(yn?43 ) ? 2 dLn?4(G)(yn?44 ) ? 3 dLn?3(G)(yn?31 ) ? 1 dLn?3(G)(yn?32 ) ? 2 dLn?3(G)(yn?33 ) ? 3 dLn?2(G)(yn?21 ) ? 1 dLn?2(G)(yn?22 ) ? 3 dLn?1(G)(yn?11 ) ? 2 Figure 2.3: Disappearing leaf dL(G)(y11) 1, dL(G)(y1j) 2 for 2 j n 2 and dL(G)(y1n 1) 3, as shown in Figure 2.3. Notice that jP1j=jP0j 1. Now, let Pi = (yi1;yi2;:::;yin i) in Li(G), such that, dLi(G)(yi1) 1;dLi(G)(yij) 2 for 2 j n i 1 and dLi(G)(yin i) 3. Then Pi induces a path Pi+1 in Li+1(G) such that Pi+1 = 7 (yi+11 ;yi+12 ;:::;yi+1n i 1) where yi+1j corresponds to the edge yijyij+1 in Pi for 1 j n i 1 as shown in the Figure 2.3. Now, dLi(G)(yi2) 2 dLi(G)(yi2) +dLi(G)(yi1) 2 + 1 dLi(G)(yi2) +dLi(G)(yi1) 2 2 + 1 2dLi+1(G)(yi+11 ) 1: Also, for 2 j k 2, dLi(G)(yij) 2 dLi(G)(yij) +dLi(G)(yij+1) 2 + 2 dLi(G)(yij) +dLi(G)(yij+1) 2 2 + 2 2 dLi+1(G)(yi+1j ) 2; and, for j = k 1, dLi(G)(yik 1) 2 dLi(G)(yik 1) +dLi(G)(yik) 2 + 3 dLi(G)(yik 1) +dLi(G)(yik) 2 2 + 3 2 dLi+1(G)(yi+1k 1) 3: So, dLi+1(G)(yi+11 ) 1;dLi+1(G)(yi+1j ) 2 for 2 j k 2 and dLi+1(G)(yi+1k 1) 3. Also, jPi+1j = jPij 1, then, following inductively starting from P1 we get that Pn 1 = (yn 11 ) where dLn 1(G)(yn 11 ) 2 as shown in the Figure 2.3. Hence, the number of vertices of degree 1 goes down by one. 8 Let G have N vertices, say v1;v2;:::;vN, of degree 1. Then, for every vertex vj of degree 1 there exists an integer Ij such that there is no vertex of degree 1 in LIj(G) corresponding to vj. Then, for the integer I = maxfIj j 1 j Ng, there would be no vertex of degree 1 corresponding to any vj. As there is no other way to get degree 1 vertices under line graph operation, LI(G) will have no vertices of degree 1. Also, as Lk(G) is connected for all k we conclude that I 2 and we are done from Lemma 2.1 and Lemma 2.3. 9 Chapter 3 Maximum degree growth in iterated line graphs In this chapter it will be shown that for any graph G, which is not a path, there exists an integer D such that k+1 = 2 k 2 for all k >D, where k is the maximum degree of Lk(G). If G is a path, then as G is a nite graph, there exists an integer I such that LI(G) is unde ned. If G is a cycle, then for all k2Z+, k+1 = 2 k 2 = 2. If G is a K1;3, then L(G) is a K3 and hence, for all k> 1, k+1 = 2 k 2 = 2. Now we have to prove the theorem for any graph G where it is not a path, a cycle or a K1;3. De nition: A vertex v is a locally maximum vertex or a l.max. vertex if no vertex in the neighborhood of v has degree greater than that of v. De nition: The subgraph of G induced by its l.max. vertices is called the locally maximum subgraph or l.max. subgraph of G and is denoted by LM(G). De nition: A vertex v 2Lk(G) is generated by a vertex u2G if there is a sequence of vertices u = v0;v1;:::;vk = v such that vi+1 2 Li+1(G) corresponds to an edge incident at vi 2Li(G). A subgraph J of Lk(G) is generated by a subgraph H of G if, for each vertex v2J, v is generated by a vertex in H. Lemma 3.1. All vertices in the same component of LM(G) have the same degree in G. Proof: Let v and u be two vertices in a component of LM(G). Then v and u are l.max. vertices of the graph G. As v2N(u), d(v) d(u) from de nition. Similarly, as u2N(v), d(u) d(v). Hence, d(u) = d(v). 10 Lemma 3.2. The vertices of L(G) corresponding to edges of G incident with the same vertex, say v, of G, form a clique in L(G). In particular, all the vertices of LM(L(G)) generated by v are in the same component of LM(L(G)). Proof: It follows from the de nition of line graphs that the vertices of L(G), corresponding to the edges of G that share a vertex, will be adjacent to each other. Lemma 3.3. If w is a l.max. vertex of L(G), then w corresponds to an edge e in G such that at least one end of e, say v, is l.max. in G and the other end of e, say u, has the maximum degree among the neighbors of v in G. Proof: Assume that neither v nor u is a l.max. vertex. Let dG(v) dG(u). Then, as v is not a l.max. vertex, there exists a vertex y2N(v) such that dG(y) >dG(v). u v y w vy G L(G) e Figure 3.1 Now, the edge vy of G corresponds to a vertex vy of L(G), adjacent to w as shown in the Figure 3.1. Also, dG(v) dG(u): But, as dG(y) >dG(v), dG(v) +dG(y) 2 >dG(u) +dG(v) 2 dL(G)(vy) >dL(G)(w); 11 contradicting that w is a l.max. vertex of L(G). Hence, no such y exists, implying that v is a l.max. vertex of G. Now, let there exist a vertex z2N(v) such that dG(z) >dG(u). u v z w vz G L(G) Figure 3.2 Then the edge vz of G corresponds to a vertex vz adjacent to w in L(G) as shown in the Figure 3.2. But, dG(z) >dG(u) dG(z) +dG(v) 2 >dG(u) +dG(v) 2 dL(G)(vz) >dL(G)(w); contradicting that w is a l.max. vertex of L(G). Hence, no such z exists, implying that u has the maximum degree in N(v). Lemma 3.4. Let v be an isolated vertex of LM(G). (a) If v has any neighbor of the same degree as that of v, then, v generates no l.max. vertices of L(G). 12 (b) If all neighbors of v have degree less than that of v, and u is such a neighbor, then the edge uv corresponds to a l.max. vertex of L(G) if and only if u has the maximum degree among the neighbors of v and for all z2N(u)nfvg, dG(z) dG(v). Proof: u v w = vu uz G L(G) z Figure 3.3 (a) As u is not a l.max. vertex of G, there exists a vertex z adjacent to u, such that, dG(z) >dG(u) = dG(v). Then, u and z generate a vertex uz adjacent to w, generated by v and u, as shown in Figure 3.3. Now, dL(G)(uz) = dG(u) + dG(z) 2 > dG(u) + dG(v) 2 = dL(G)(w), therefore, the edge vu does not correspond to a l.max. vertex of L(G), for any u with dG(u) = dG(v). Hence, by Lemma 3.3, v does not generate a l.max. vertex of L(G). (b) Let there exist a vertex z 2 N(u)nfvg such that dG(z) > dG(v). Then the edge uz corresponds to a vertex uz in L(G) adjacent to a vertex w, which corresponds to the edge uv in G, as shown in Figure 3.3. Now, dL(G)(uz) = dG(u) + dG(z) 2 > dG(u) +dG(v) 2 = dL(G)(w), therefore, w will not be a l.max. vertex. Now, let, for all z2N(u)nfvg, dG(z) dG(v). Then, dG(u) +dG(z) 2 dG(u) +dG(v) 2; dL(G)(uz) dL(G)(w); 13 where w corresponds to the edge uv of G. Therefore, the edge uv corresponds to a l.max. vertex of L(G). Moreover, if uz is a l.max. vertex, it would be adjacent to w implying that the number of components will not increase. Lemma 3.5. Let C be a component of LM(G) which is not a single vertex. a) If v1 and v2 are adjacent vertices in C, then the vertex w2L(G), corresponding to the edge v1v2, is a l.max. vertex. b) If u2NhCi, then no edge joining u to a vertex in C corresponds to a l.max. vertex of L(G). Proof: v2 v1 z e eprime w x G C L(G) Figure 3.4 a) Let e0 = v1v2 be an edge in C. Let w2L(G) be the vertex corresponding to e0. Then, any neighbor x of w will correspond to an edge e, in G, incident at either v1 or v2. Let e be incident at v1 and some vertex z2N(v1), as shown in the Figure 3.4. Then, as v1 is a l.max. vertex, dG(z) dG(v1) dG(z) +dG(v2) 2 dG(v1) +dG(v2) 2 14 From Lemma 3.1, dG(v1) = dG(v2), dG(z) +dG(v1) 2 dG(v1) +dG(v2) 2 dL(G)(x) dL(G)(w); hence, w is a l.max. vertex. v2 v1 u e eprime w x G C L(G) z y Figure 3.5 b) As u2NhCi, it is adjacent to a vertex, say v1, in C. As C is not a single vertex, there exists a vertex v2 2C adjacent to v1. Let w be the vertex in L(G) corresponding to the edge v1v2 and let r be the common degree of vertices in C. Then, dL(G)(w) = 2r 2. Now, the edge uv1 corresponds to a vertex x adjacent to w in L(G), as shown in the Figure 3.5. Also, dL(G)(x) = dG(u) + r 2 and as v1 is a l.max. vertex, we get that dG(u) r. If dG(u) dG(u). Then, the edge uz corresponds to a vertex y in L(G), adjacent to x as shown in Figure 3.5. Now, dG(z) >dG(u) dG(z) +dG(u) 2 >dG(u) +dG(u) 2 dG(z) +dG(u) 2 >dG(u) +r 2 dL(G)(y) >dL(G)(x); and hence, x can not be a l.max. vertex. Corollary 3.1: It follows from Lemma 3.5 that L(C) is a component of LM(L(G)). Corollary 3.2: If C is a single vertex, then from Lemma 3.4 it generates at most one component of LM(L(G)). Otherwise, if C is not a single vertex, then every vertex of C generates a l.max. vertex from Lemma 3.5(a). As the line graph operation preserves connectivity, C will generate at most one component of LM(L(G)). Hence, in either case, C generates at most one component. Lemma 3.6. There exists an integer A such that for all k > A, every component of LM(Lk(G)) generates exactly one component of LM(Lk+1(G)). Proof: Let ck be the number of components of LM(Lk(G)). From Corollary 3.2, fckg is a non-increasing sequence. But as ck is a non-negative number for all k, there exists an integer A, such that ck is constant for all k>A. We now de ne new notation which would be followed in the rest of this chapter. Let CA+1 be a component of LM(LA+1(G)) where A is the integer from Lemma 3.6. Inductively, for each k>A, let Ck+1 be the component of Lk+1(G) generated by Ck. Let rk be the common 16 degree of vertices in Ck. We can further choose A to be su ciently large so that k > 2 for all k>A from Lemma 2.1. Lemma 3.7. Let u2NhCDibe adjacent to a vertex vD 2CD, where D is an integer greater than A. Let y2LD+1(G) correspond to the edge uv of LD(G), so y2N[CD+1]. (a) If CD is not a single vertex, so y2NhCD+1i, and, rD+1 dLD+1(G)(y) = rD dLD(G)(u): (b) In case CD is a single vertex, then, rD+1 dLD+1(G)(y) A, v generates every vertex in Ck+1. So, there exists a vertex w2Ck+1 generated by v. Now, the edges in Lk(G) corresponding to y and w, are incident at the vertex v. Hence, y is adjacent to the vertex w in Lk+1(G), implying that, if y is a l.max. vertex then y2Ck+1 or else y2NhCk+1i. Let NhCBi = fu1;u2;:::;ung. Then from Lemma 3.8, for every 1 j n, uj gener- ates a vertex, say y1j, in N[CB+1]. Now, if yij is a vertex in NhCB+ii, then from Lemma 3.8, it generates a vertex, say yi+1j , in N[CB+i+1]. Otherwise, if yij is a vertex in CB+i, then from Lemma 3.5(a), it generates a vertex, say yi+1j , in CB+i+1. It follows inductively that uj generates a sequence of ver- tices (uj = y0j;y1j;y2j;y3j;::::) where yij 2N[CB+i] and, moreover, yij 2CB+i for all i > I if yIj 2CB+I for some integer I. Then we de ne a function f(uj;i) : NhCBi! R by f(uj;i) = rB+i dLB+i(G)(yij) where i2Z+. Clearly f(uj;i) is non-negative and from Lemma 3.7 it is a non-increasing function of i. Also, if CB+i is a single vertex and yij 2NhCB+ii, then, from Lemma 3.4(a), f(uj;i) can not equal to zero because otherwise CB+i will not generate a component. Theorem 3.1. Let G be a simple connected graph. Let CA be a component of LM(LA(G)). Then, there are a nite number of integers k>A, such that Ck, generated by CA, is a single vertex. Proof: The proof is by contradiction. Let us assume that there are an in nite number of integers k>A such that Ck is a single vertex. Then we prove the following series of lemmas. Lemma 3.9. If u1 2NhCBi generates (y01;y11;y21;y31;::::), then there exists an integer I such that yI1 2CB+I. 19 Proof: We prove this by contradiction. Let yi1 2NhCB+ii for all i. The function f(u1;i) is non-increasing and decreases when CB+i is a single vertex. As there are in nite number of integers k>A such that Ck is a single vertex, there are in nite integers i such that CB+i is a single vertex as B > A. Hence, from Lemma 3.7(b) there exists an integer D > B such that f(u1;D B) = 0. Now, if CD is a single vertex, then as yi1 2NhCB+ii for all i, it follows that f(u1;D B) can not be zero and we have a contradiction. Otherwise, if CD has an edge, then let E be the smallest integer greater than D such that CE is a single vertex. From Lemma 3.7(a), f(u1;E B) = f(u1;D B) = 0, and we again have a contradiction. Lemma 3.10. If u1 2NhCBi then there exists an integer D B such that u1 generates yD B1 2NhCDi where CD is a single vertex and dLD(G)(yD B1 ) is maximum in NhCDi. Proof: From Lemma 3.9 there exists an integer I such that u1 generates yI1 2CB+I. Let I be the smallest such integer. Hence, yI 11 2NhCB+I 1i. From Lemma 3.5, if CB+I 1 has an edge then yI 11 cannot generate a vertex in CB+I. Hence, CB+I 1 is a single vertex. Also, from Lemma 3.3, dLB+I 1(G)(yI 11 ) is maximum in NhCB+I 1i. Lemma 3.11. If u1 2NhCBi where CB is not a single vertex, then, dLB(G)(u1)6= rB. Proof: Assume that dLB(G)(u1) = rB and hence, f(u1;0) = 0. But as f(ui;j) is non- negative and non-increasing, f(u1;j) = 0 for all j. But, from Lemma 3.10, there exists an integer D B such that u1 generates yD B1 2 NhCDi where CD is a single vertex with f(u1;D B) = 0, which is a contradiction. Corollary 3.3. From Lemma 3.4(a) and Lemma 3.11, if u2NhCki then dLk(G)(u1)6= rk. Lemma 3.12. Let CB =fvBgand u1;u2;:::;un be vertices of equal degree in NhCBisuch that dLB(G)(ui) is maximum in NhCBi. Then, ui generates a vertex vi2CB+1 for all 1 i n. Moreover, u1;u2;:::;un generate l.max. vertices which induce a complete subgraph in CB+1. 20 Proof: As CB generates CB+1, from Lemma 3.3 there exists an integer I 2 [1;n] such that uI generates a vertex vB+1 2CB+1. Let there be some J6= I such that uJ does not generate any vertex in CB+1. Then, from Lemma 3.8, uJ generates a vertex, say u, in NhCB+1i. Now, rB+1 = dLB+1(G)(vB+1) = dLB(G)(uI) + rB 2 = dLB(G)(uJ) + rB 2 = dLB+1(G)(u) which is a contradiction from Corollary 3.3 and hence no such J exists. So, all u1;u2;:::;un generate l.max. vertices, say v1;v2;:::;vn, in CB+1 such that vi corre- sponds to the edge uivB in LB(G). As all the corresponding edges share the vertex vB, the vertices v1;v2;:::;vn induce a complete subgraph. Lemma 3.13. Let u1;u2 2NhCBiwith dLB(G)(u1) = dLB(G)(u2). Furthermore, let u1 gener- ate the sequence (u1 = y01;y11;y21;y31;::::) and u2 generate the sequence (u2 = y02;y12;y22;y32;::::). Then, dLB+i(G)(yi1) = dLB+i(G)(yi2) for all i2Z+ and either yi1;yi2 2CB+i or yi1;yi2 2NhCB+ii. Proof: For i = 1, dLB+1(G)(y11) = dLB(G)(u1) +rB 2 = dLB(G)(u2) +rB 2 = dLB+1(G)(y12): If CB has an edge, then y11;y12 2NhCB+1ifrom Lemma 3.5(b) as u1;u2 2NhCBi, otherwise, CB is a single vertex. If dLB(G)(u1) = dLB(G)(u2) is maximum in NhCBi, then y11;y12 2CB+1 from Lemma 3.12. On the other hand, if dLB(G)(u1) = dLB(G)(u2) is not maximum in NhCBi, then y11;y12 2NhCB+1i. Let, for i = n, dLB+n(G)(yn1 ) = dLB+n(G)(yn2 ) and either yn1;yn2 2CB+n or yn1;yn2 2NhCB+ni. Now, if yn1;yn2 2CB+n then from Lemma 3.5(a), yn+11 ;yn+12 2CB+n+1 and dLB+n+1(G)(yn+11 ) = dLB+n+1(G)(yn+12 ) = rB+n+1. Otherwise yn1;yn2 2 NhCB+ni. If CB+n has an edge, from Lemma 3.5(b) we get that 21 yn+11 ;yn+12 2NhCB+n+1i. Then, dLB+n+1(G)(yn+11 ) = dLB+n(G)(yn1 ) +rB+n 2 = dLB+n(G)(yn2 ) +rB+n 2 = dLB+n+1(G)(yn+12 ): But, if yn1;yn2 2NhCB+niand CB+n is a single vertex, then, if dLB+n(G)(yn1 ) = dLB+n(G)(yn2 ) is maximum in NhCB+ni, and then from Lemma 3.12, yn1 and yn2 generate yn+11 and yn+12 , re- spectively, in CB+n+1. Else, if dLB+n(G)(yn1 ) = dLB+n(G)(yn2 ) is not maximum in NhCB+ni, then from Lemma 3.3, yn+11 and yn+12 are in NhCB+n+1i and dLB+n+1(G)(yn+11 ) = dLB+n(G)(yn1 ) + rB+n 2 = dLB+n(G)(yn2 ) +rB+n 2 = dLB+n+1(G)(yn+12 ). Lemma 3.14. If u1;u2;:::;un 2NhCBi with dLB(G)(ui) = dLB(G)(uj), then there exists an integer E > B such that u1;u2;:::;un generate vertices yE B1 ;yE B2 ;:::;yE Bn 2CE which form a clique. Proof: From Lemma 3.10 and Lemma 3.13, there exists an integer D B such that uj generates yD Bj 2NhCDi, 1 j n, where CD is a single vertex, say vD, and dLD(G)(yD Bj ) is maximum in NhCDi. Then, from Lemma 3.12, yD Bj for 1 j n induce a complete subgraph in CD+1. Lemma 3.15. There exists an integer E >A such that CE 1 has exactly one edge. Proof: Pick an integer B > A such that CB = fvBg. Such an integer exists from our assumption that there are in nite integers k > A where Ck is a single vertex. Then, as 22 A > 2, we have, from Lemma 2.1, B > 2 B < 2 rB B + 1 B. But, as there are in nite integers such that Ck is a single vertex, there exists an integer E > D such that CE is a single vertex. Let E be the smallest such integer. Then, CE 1 will have exactly one edge and the lemma is proved. Lemma 3.16. There exists an integer E such that CE =fvEg and there are three vertices u1;u2;u3 2NhCEi with equal degree. Proof: Let 0k denote the minimum degree in NhCki. Then, 0k = 0k 1 +rk 1 2: 23 Now, pick an integer B such that CB has exactly one edge. Such an integer exists from Lemma 3.15. Then, rB+1 = 2rB 2 from Lemma 3.5(a). But, 0B > 2 0B +rB 1 > 2 +rB 1 rB 1 > 2 +rB 1 0B rB 1 > 2 + 2rB 1 rB 0B + 2 2 rB 1 > (2rB 2) (rB + 0B 2) + 1 rB 1 >rB+1 0B+1 + 1 2rB 2 > 2(rB+1 0B+1 + 1) rB+1 > 2(rB+1 0B+1 + 1) Now, rB+1 is the number of neighbors of vB+1 and as vB+1 is a l.max. vertex, we have that (rB+1 0B+1 + 1) is the number of possible unique values of degree of a neighbor of vB+1. Also, because CB has exactly one edge, CB+1 = fvB+1g, and therefore, from Pigeonhole principle, there exist at least three vertices of equal degree in NhCB+1i. Continuing rest of the proof of Theorem 3.1: Now, from Lemma 3.16 and Lemma 3.14, there exists an integer F > E such that CF contains a K3. Hence, from Lemma 3.5(a), Ck contains K3 all k>F which contradicts that there are in nite number of integers k>A such that Ck is a single vertex. Hence, there are nite values of k > A where Ck is a single vertex and there exists an integer I, such that CI+i, generated by Ck, has at least one edge, for all i. So, from Theorem 3.1, for each component CjB of LM(LB(G)) where B > A, there exists an integer Ij >B such that CjIj+i generated by CjB has at least one edge for all i. Suppose LM(LB(G)) has N components. Using this reasoning for all components CjB, 1 j N, there exists an integer D = maxfIj j 1 j Ng, such that every component of LM(LD+i(G)) has at least one edge for all i. 24 Clearly, the vertices of maximum degree of any graph G are also l.max. vertices and hence are components of LM(G). But every component of LM(LD+i) has edges for all i, hence, every vertex of maximum degree is adjacent to at least one vertex of maximum degree, and so, k = 2 k 1 2 for all k>D. 25 Chapter 4 Minimum degree growth in iterated line graphs In this chapter it will be shown that for any graph G, which is not a path, there exists an integer D such that k+1 = 2 k 2 for all k > D, where k is the minimum degree of Lk(G). Note that, most of the lemmas for this proof parallel the lemmas, proved in Chapter 3, with the inequalities reversed. However, a di erent line of reasoning is used in the second half of the proof to contradict a theorem similar to Theorem 3.1. If G is a path, then as G is a nite graph, there exists an integer I such that LI(G) is unde ned. If G is a cycle, then for all k2Z+, k+1 = 2 k 2 = 2. If G is a K1;3, then L(G) is a K3 and hence, for all k> 1, k+1 = 2 k 2 = 2. Now we have to prove the theorem for any graph G where it is not a path, a cycle or a K1;3. De nition: A vertex v is a locally minimum vertex or a l.min. vertex if no vertex in the neighborhood of v has degree smaller than that of v. De nition: The subgraph of G induced by its l.min. vertices is called the locally minimum subgraph or l.min. subgraph of G and is denoted by lm(G). Lemma 4.1. All vertices in the same component of lm(G) have the same degree in G. Proof: Let v and u be two vertices in a component of lm(G). Then v and u are l.min. vertices of the graph G. As v2N(u), d(v) d(u) from de nition. Similarly, as u2N(v), d(u) d(v). Hence, d(u) = d(v). 26 Lemma 4.2. If w is a l.min. vertex of L(G), then w corresponds to an edge e in G such that at least one end of e, say v, is l.min. in G and the other end of e, say u, has the smallest degree among the neighbors of v in G. Proof: Assume that neither v nor u is a l.min. vertex. Let dG(v) dG(u). Then, as v is not a l.min. vertex, there exists a vertex y2N(v) such that dG(y) r, then, dG(u) +r 2 >r +r 2; dL(G)(x) >dL(G)(w); and x can not be a l.min. vertex. Otherwise, dG(u) = r. But as u is not a l.min. vertex, there exists a vertex z 2 N(u)nfv1gsuch that dG(z) A, every component of lm(Lk(G)) generates exactly one component of lm(Lk+1(G)). Proof: Let ck be the number of components of lm(Lk(G)). From Corollary 4.2, fckg is a non-increasing sequence. But as ck is a non-negative number for every k, there exists an integer A, such that ck is constant for all k>A. We now de ne new notation which would be followed in the rest of this chapter. Let CA+1 be a component of lm(LA+1(G)) where A is the integer from Lemma 4.5. Inductively, for each k>A, let Ck+1 be the component of Lk+1(G) generated by Ck. Let rk be the common degree of vertices in Ck. We can further choose A to be su ciently large so that k > 2 for all k>A, from Lemma 2.1. Lemma 4.6. Let u2NhCDi be adjacent to a vertex v2CD, where D is an integer greater than A. Further, let y 2LD+1(G) correspond to the edge uv of LD(G), so y 2N[CD+1]. Then the following holds. (a) If CD is not a single vertex, then dLD+1(G)(y) rD+1 = dLD(G)(u) rD 32 (b) Otherwise, if CD is a single vertex, then, dLD+1(G)(y) rD+1 rD as CD generates CD+1. So, dLD(G)(x) +rD 2 >rD +rD 2; rD+1 > 2rD 2; rD+1 dLD+1(G)(y) > (2rD 2) dLD+1(G)(y): But, dLD+1(G)(y) = dLD(G)(u) +rD 2, therefore, rD+1 dLD+1(G)(y) > (2rD 2) (dLD(G)(u) +rD 2); rD+1 dLD+1(G)(y) >rD dLD(G)(u); dLD+1(G)(y) rD+1 A, v generates every vertex in Ck+1. Then, there exists a vertex w2Ck+1 generated by v. Now, the edges in Lk(G) corresponding to y and w, are incident at the vertex v. Hence, y is adjacent to the vertex w in Lk+1(G), implying that, if y is a 34 l.min. vertex then y2Ck+1 or else y2NhCk+1i. Let NhCBi = fu1;u2;:::;ung. Then, from Lemma 4.7, for every 1 j n, uj gener- ates a vertex, say y1j, in N[CB+1]. Now, if yij is a vertex in NhCB+ii, then from Lemma 4.7, it generates a vertex, say yi+1j in N[CB+i+1]. Otherwise, if yij is a vertex in CB+i, then from Lemma 4.4(a), it generates a vertex, say yi+1j in CB+i+1. It follows inductively that uj generates a sequence of ver- tices (uj = y0j;y1j;y2j;y3j;::::) where yij 2N[CB+i] and, moreover, yij 2CB+i for all i > I if yIj 2CB+I for some integer I. Then, we de ne a function f(uj;i) : NhCBi! R by f(uj;i) = dLB+i(G)(yij) rB+i where i2Z+. Clearly f(uj;i) is non-negative and from Lemma 4.6 it is a non-increasing function of i. Also, if CB+i is a single vertex and yij 2NhCB+ii, then, from Lemma 4.3(a), f(uj;i) can not equal to zero as otherwise CB+i will not generate a component. Theorem 4.1. Let G be a simple and connected graph. Let CA be a component of lm(LA(G)). Then, there are a nite number of integers k>A, such that Ck, generated by CA, is a single vertex. Proof: The proof is by contradiction. Let us assume that there are in nite number of integers k>A such that Ck is a single vertex. Then we prove the following series of lemmas. Lemma 4.8. If u1 2NhCBi generates (y01;y11;y21;y31;::::), then there exists an integer I such that yI1 2CB+I. Proof: We prove this by contradiction. Let yi1 2NhCB+ii for all i. The function f(u1;i) is non-increasing and decreases when CB+i is a single vertex. As there are in nite number of integers k>A such that Ck is a single vertex, there are in nite integers i such that CB+i is a single vertex as B > A. Hence, from Lemma 4.6(b) there exists an integer D > B such that f(u1;D B) = 0. Now, if CD is a single vertex, then as yi1 2 NhCB+ii for all i, f(u1;D B) can not be 35 zero and we have a contradiction. Otherwise, if CD has an edge, then let E be the smallest integer greater than D such that CE is a single vertex. From Lemma 4.6(a), f(u1;E B) = f(u1;D B) = 0, and we again have a contradiction. Lemma 4.9. If u1 2 NhCBi then there exists an integer D B such that u1 generates yD B1 2NhCDi where CD is a single vertex and dLD(G)(yD B1 ) is minimum in NhCDi. Proof: From Lemma 4.8 there exists an integer I such that u1 generates yI1 2CB+I. Let I be the smallest such integer. Then, yI 11 2NhCB+I 1i. From Lemma 4.4, if CB+I 1 has an edge then yI 11 cannot generate a vertex in CB+I. Hence, CB+I 1 is a single vertex. Also, from Lemma 4.2, dLB+I 1(G)(yI 11 ) is minimum in NhCB+I 1i. Lemma 4.10. If u1 2NhCBi where CB is not a single vertex, then, dLB(G)(u1)6= rB. Proof: Assume that dLB(G)(u1) = rB and hence, f(u1;0) = 0. But as f(ui;j) is non- negative and non-increasing, f(u1;j) = 0 for all j. But, from Lemma 4.9, there exists an integer D B such that u1 generates yD B1 2 NhCDi where CD is a single vertex with f(u1;D B) = 0, which is a contradiction. Corollary 4.3. From Lemma 4.3(a) and Lemma 4.10, if u2NhCki then dLk(G)(u)6= rk. Lemma 4.11. Let CB =fvBgand u1;u2;:::;un be vertices of equal degree in NhCBisuch that dLB(G)(ui) is minimum in NhCBi. Then, ui generates a vertex vi2CB+1 for all 1 i n. Moreover, u1;u2;:::;un generate l.min. vertices which induce a complete subgraph in CB+1. Proof: As CB generates CB+1, from Lemma 4.2 there exists an integer I 2 [1;n] such that uI generates a vertex in CB+1. Let there be some J 6= I such that uJ does not generate any vertex v2CB+1. Then, from Lemma 4.7 it follows that uJ generates a vertex, say u, in NhCB+1i. Now, rB+1 = dLB+1(G)(vB+1) = dLB(G)(uI) + rB 2 = dLB(G)(uJ) + rB 2 = dLB+1(G)(u) which is a contradiction from Corollary 4.3 and hence no such J exists. So, all u1;u2;:::;un generate l.min. vertices, say v1;v2;:::;vn, in CB+1 such that vi corresponds 36 to the edge uivB in LB(G). As all the corresponding edges share the vertex vB, the vertices v1;v2;:::;vn induce a complete subgraph. Lemma 4.12. Let u1;u2 2NhCBi with dLB(G)(u1) = dLB(G)(u2). Let u1 generate the se- quence (u1 = y01;y11;y21;y31;::::) and u2 generate the sequence (u2 = y02;y12;y22;y32;::::). Then, dLB+i(G)(yi1) = dLB+i(G)(yi2) for all i2Z+ and either yi1;yi2 2CB+i or yi1;yi2 2NhCB+ii. Proof: For i = 1, dLB+1(G)(y11) = dLB(G)(u1) +rB 2 = dLB(G)(u2) +rB 2 = dLB+1(G)(y12) If CB has an edge, then y11;y12 2NhCB+1i from Lemma 4.4(b) as u1;u2 2NhCBi. Otherwise, CB is a single vertex. If dLB(G)(u1) = dLB(G)(u2) is minimum in NhCBi, then y11;y12 2CB+1 from Lemma 4.11. Else, if dLB(G)(u1) = dLB(G)(u2) is not minimum in NhCBi, then y11;y12 2NhCB+1i. Let, for i = n, dLB+n(G)(yn1 ) = dLB+n(G)(yn2 ) and either yn1;yn2 2CB+n or yn1;yn2 2NhCB+ni. Now, if yn1;yn2 2CB+n then from Lemma 4.4(a), yn+11 ;yn+12 2CB+n+1 and dLB+n+1(G)(yn+11 ) = dLB+n+1(G)(yn+12 ) = rB+n+1. Otherwise yn1;yn2 2 NhCB+ni. If CB+n has an edge, then, from Lemma 4.4(b), we have yn+11 ;yn+12 2NhCB+n+1i. Then, dLB+n+1(G)(yn+11 ) = dLB+n(G)(yn1 ) +rB+n 2 = dLB+n(G)(yn2 ) +rB+n 2 = dLB+n+1(G)(yn+12 ): But, if yn1;yn2 2NhCB+ni and CB+n is a single vertex, then, if dLB+n(G)(yn1 ) = dLB+n(G)(yn2 ) is minimum in NhCB+ni, from Lemma 4.11, yn1 and yn2 generate yn+11 and yn+12 , respectively, 37 in CB+n+1. Else, if dLB+n(G)(yn1 ) = dLB+n(G)(yn2 ) is not minimum in NhCB+ni, then from Lemma 4.2, yn+11 and yn+12 are in NhCB+n+1i and dLB+n+1(G)(yn+11 ) = dLB+n(G)(yn1 ) + rB+n 2 = dLB+n(G)(yn2 ) +rB+n 2 = dLB+n+1(G)(yn+12 ). Lemma 4.13. If u1;u2;:::;un 2NhCBi with dLB(G)(ui) = dLB(G)(uj), then there exists an integer E > B such that u1;u2;:::;un generate vertices yE B1 ;yE B2 ;:::;yE Bn 2CE which form a clique. Proof: From Lemma 4.9 and Lemma 4.12, there exists an integer D B such that uj gen- erates yD Bj 2NhCDi, 1 j n, where CD is a single vertex, say vD, and dLD(G)(yD Bj ) is minimum in NhCDi. Then, from Lemma 4.2, yD Bj for 1 j n, induce a complete subgraph in CD+1. Continuing rest of the proof of Theorem 4.1: Now, A > 3. Hence, k > 3 for all k > A. Pick any integer B > A. Let vB 2CB and wB 2LB(G) be a vertex of maximum degree, B. As G is connected, there exists a path PB = (wB = vB1 ;vB2 ;:::;vBn = vB) from wB to wB = vB1 vB2 vB3 vB4 vBn?2 vBn?1 vB = vBn LB(G) CB Figure 4.8: Path from wB to vB 38 vB as shown in Figure 4.8. Now, B > 3 B < 3 B B < B 3 B B + 1 < B 2: Degree of any neighbor of wB can be any of B B + 1 possible values. But there are wB = vB1 vB2 vB3 vB4 vBn?2 vBn?1 vB = vBn LB(G) CB zB1 zB2 Figure 4.9: Path from wB to vB B 1 neighbors of wB apart from vB2 . From Pigeonhole principle, there exist at least two vertices, say zB1 ;zB2 2N(wB)nfvB2g such that dLB(G)(zB1 ) = dLB(G)(zB2 ), as shown in Figure 4.9. Now, L(PB) will be a path in LB+1(G). Let the edge zB1 vB1 correspond to the vertex zB+11 in LB+1(G). Let the edge zB2 vB1 correspond to the vertex zB+12 in LB+1(G). Let the edge vBi vBi+1 correspond to the vertex vB+1i in LB+1(G) for 1 i n 2. From Lemma 4.7, vBn 1 generates a vertex, say vB+1n 1 , such that either vB+1n 1 2CB+1 or vB+1n 1 2NhCB+1i. When vB+1n 1 2NhCB+1i, there exists a vertex vB+1n 2CB+1 adjacent to vB+1n 1 . 39 wB = vB1 vB2 vBn?2 vBn?1 vB = vBn LB(G) CB zB1 zB2 vB+11 vB+12 vB+1n?2 vB+1n?1 vB+1 = vB+1n LB+1(G) CB+1 zB+11 zB+12 Figure 4.10: vB+1n 1 2NhCB+1i wB = vB1 vB2 vBn?2 vBn?1 vB = vBn LB(G) CB zB1 zB2 vB+11 vB+12 vB+1n?3 vB+1n?2 vB+1 = vB+1n?1 LB+1(G) CB+1 zB+11 zB+12 Figure 4.11: vB+1n 1 2CB+1 De ne PB+1 = (vB+11 ;vB+12 ;:::;vB+1n ) if vB+1n 1 2NhCB+1i, as shown in Figure 4.10. Otherwise, de ne PB+1 = (vB+11 ;vB+12 ;:::;vB+1n 1 ) if vB+1n 1 2 CB+1, as shown in Figure 4.11. Notice that dLB+1(G)(zB+11 ) = dLB(G)(zB1 ) +dLB(G)(vB1 ) 2 = dLB(G)(zB2 ) +dLB(G)(vB1 ) 2 = dLB+1(G)(zB+12 ). Also, if vB+1n 1 2 NhCB+1i, then jPB+1j = jPBj, and if vB+1n 1 2 CB+1, then jPB+1j=jPBj 1. From Lemma 4.8 there exists an integer In 1 such that vBn 1 generates vB+In 1n 1 2CB+In 1. Let In 1 be the smallest such integer. Then PB+In 1 = (vB+In 11 ;vB+In 12 ;:::;vB+In 1n 1 ) and jPB+In 1j=jPBj 1. zB+I1 vB+I1 CB+IzB+I2 LB+I(G) Figure 4.12 40 Following inductively, there exists an integer I = In 1 +In 2 +:::+I1 such that PB+I = (vB+I1 ) and dLB+I(G)(zB+I1 ) = dLB+I(G)(zB+I2 ) as shown in Figure 4.12. From Lemma 4.9 and zD1 vD CDzD2 LD(G) Figure 4.13 Lemma 4.12, there exists an integer D B + I such that zB+I1 and zB+I2 generate zD1 and zD2 , respectively, in NhCDi, where CD =fvDg and dLD(G)(zD1 ) = dLD(G)(zD2 ) is minimum in NhCDi, as shown in Figure 4.13. zD1 vD CD zD2 LD(G) zD1 vD CD+1 zD2 vD LD+1(G) x y xvD yvD Figure 4.14 But, as k > 3 for all k > A, there are at least two more neighbors of vD, say x and y and let dLD(G)(x) dLD(G)(y). As CD is a single vertex, from Lemma 4.11 it fol- lows that zD1 and zD2 generate zD1 vD and zD2 vD, respectively, in CD+1, which are adjacent to each other, as is shown in Figure 4.14. In the next iteration, we get four vertices, 41 zD1 vD CD+1 zD2 vD LD+1(G) xvD yvD (xvD)(zD1 vD) zD1 zD2 CD+2(xvD)(z D2 vD) (yvD)(zD1 vD) (yvD)(zD2 vD) LD+2(G) Figure 4.15 (xvD)(zD1 vD);(xvD)(zD2 vD);(yvD)(zD1 vD) and (yvD)(zD2 vD), as are shown in the Figure 4.15. IfdLD(x) = dLD(y), then, from Lemma 4.12, we havedLD+2(G)((xvD)(zD1 vD)) = dLD+2(G)((xvD)(zD2 vD)) = dLD+2(G)((yvD)(zD1 vD)) = dLD+2(G)((yvD)(zD2 vD)). So, from Lemma 4.13, there exists an in- teger F >E, such that, CF contains a K4. Otherwise, let dLD(x) < dLD(y). From Lemma 4.9 and Lemma 4.12, there exists an integer E > D + 2 such that CE is a single vertex, say vE, and, xvDzD1 vD and xvDzD2 vD generate vertices, say x1 and x2, respectively, in NhCEi, such that they have the same degree which is minimum in NhCEi. Let y1 and y2 be the vertices generated by (yvD)(zD1 vD) and (yvD)(zD2 vD), respectively, in LE(G), as shown in the Figure 4.16. Notice that dLE(G)(y1) = dLE(G)(y2). Then, we have the line graph iterations as shown in Figure 4.17. Now, dLE+1(G)(y1vE) = dLE(G)(y1) +dLE(G)(vE) = dLE(G)(y2) +dLE(G)(vE) = dLE+1(G)(y2vE): 42 Also, dLE+2(G)((y1vE)(x1vE)) = dLE+1(G)(y1vE) +dLE+1(G)(x1vE) 2 = dLE+1(G)(y1vE) +rE+1 2; dLE+2(G)((y1vE)(x2vE)) = dLE+1(G)(y1vE) +dLE+1(G)(x2vE) 2 = dLE+1(G)(y1vE) +rE+1 2; dLE+2(G)((y2vE)(x1vE)) = dLE+1(G)(y2vE) +dLE+1(G)(x1vE) 2 = dLE+1(G)(y1vE) +rE+1 2; and, dLE+2(G)((y2vE)(x2vE)) = dLE+1(G)(y2vE) +dLE+1(G)(x2vE) 2 = dLE+1(G)(y1vE) +rE+1 2: (xvD)(zD1 vD) zD1 zD2 CD+2(xvD)(z D2 vD) (yvD)(zD1 vD) (yvD)(zD2 vD) LD+2(G) x1 vE CE x2 y1 y2 LE(G) Figure 4.16 So, there are four vertices of same degree in NhCE+2i. From Lemma 4.13, there exists an integer F >E + 2 such that CF will contain a K4. Returning to the proof of Theorem 4.1: Therefore, for a component CjB of lm(LB(G)) where B > A there exists an integer Ij > B such that CjIj generated by CjB has a K4 and 43 hence, from Lemma 4.4(a), CjIj+i contains K4 for all i, which is a contradiction to the as- sumption that there are ini nite integers k>A such that Ck is a single vertex. Hence, there exists an integer I such that CI+i has at least one edge for all i. Suppose lm(LB(G)) has N components. Then, from Theorem 4.1, for every component CjB, 1 j N, as there are nite number of integers k such that Ck is a single vertex, there exists an integer Ij > B such that CjIj+i, generated by CjB, has at least one edge for all i. Hence, there exists D = maxfIj j1 j Ng, such that every component of lm(LD+i(G)) has at least one edge for all i. Clearly, the vertices of minimum degree of any graph G are also l.min. vertices and, hence, are components of lm(G). But every component of lm(LD+i(G)) has at least one edge for all i. Hence, every vertex of minimum degree is adjacent to at least one vertex of minimum degree, so, k = 2 k 1 2 for all k>D. x1 vE CE x2 LE(G) x1vE CE+1 x2vE LE+1(G) y1 y2 y1vE y2vE (y1vE)(x1vE) CE+2 (y1vE)(x2vE) LE+2(G) (y2vE)(x1vE) (y2vE)(x2vE) (x1vE)(x2vE) Figure 4.17 44 Chapter 5 A puzzle Dr.Ho man assigned me an interesting puzzle. If G is a connected graph and L(G) is regular, then show that G is either regular or bipartite. Proof: For any graph G, its line graph, L(G), is regular if and only if every edge of G is incident with the same number of edges. Hence, for any two edges uv and wy, d(u) +d(v) 2 = d(w) +d(y) 2; d(u) +d(v) = d(w) +d(y) Let uv be an edge of G and w be a vertex. As G is connected, then without loss of generality, there exists a path P = (u;v;v1;v2;:::;vn;w). Now, d(v1) + d(v) = d(v) + d(u) and hence d(v1) = d(u). If d(vi) = d(u), then, d(vi+1) = d(v), otherwise, if d(vi) = d(v), then, d(vi+1) = d(u). It follows from induction that for any vertex w of G, we have that, d(w) = d(u) or d(w) = d(v). Moreover, for any edge wy, either d(w) = d(u) and d(y) = d(v) or the other way round. Also, from induction, the degree of the vertices alternates along the path, hence, if jPj is even, then, d(w) = d(u), otherwise, if jPj is odd then d(w) = d(v). Now, if G has an odd cycle, say, P = (u;v1;v2;:::;vn;u), then from above discussion d(u) = d(v1). But as for any vertex w of G, d(w) = d(u) or d(w) = d(v1), therefore G is regular. It follows that for any connected graph G with L(G) regular, either G is regular and, if it is not regular, then it has no odd cycles, i.e., it is bipartite. 45 Bibliography [1] Lowell W. Beineke, \Characterizations of Derived Graphs", J. Combin. Theory, 9 (1970), 129-135. [2] Stephen G. Hartke and Aparna W. Higgins, \Maximum Degree Growth of the Iterated Line Graph", The Electron. J. Combin., 6 (1999), # R28. [3] Stephen G. Hartke and Aparna W. Higgins, \Minimum Degree Growth of the Iterated Line Graph", Ars Combin., 69 (2003), 275-283. [4] Douglas B. West, \Introduction to Graph Theory", Second Edition, PHI Learning Pvt. Ltd., 2009. 46