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