Maximum Degree Growth of the Iterated Line Graph

Stephen G. Hartke^{∗} Aparna W. Higgins^{†} Department of Mathematics University of Dayton Dayton, OH 45469-2316

Submitted: February 25, 1999; Accepted: June 24, 1999.

Abstract

Let Δ_{k} denote the maximum degree of the k^{th} iterated line graph L^{k}(G). For any connected graph G that is not a path, the inequality Δ_{k+1} ≤ 2Δ_{k} − 2 holds. Niepel, Knor, and Šoltés [3] have conjectured that there exists an integer K such that, for all k ≥ K, equality holds; that is, the maximum degree Δ_{k} attains the greatest possible growth. We prove this conjecture using induced subgraphs of maximum degree vertices and locally maximum vertices.

Mathematics Subject Classification: Primary 05C75, Secondary 05C12.

1 Introduction

The line graph L(G) of a graph G is defined as the graph whose vertices are the edges of G and where two vertices in L(G) are adjacent if and only if the corresponding edges in G are incident to a common vertex. Line graphs are well studied, and we direct the reader to [1] for a general discussion of the properties of line graphs. In particular, if v is a vertex in L(G) and u and w are the endpoints of the edge in G that corresponds to v, then deg_{L(G)}(v) = deg_{G}(u)+deg_{G}(w)−2. Thus, the maximum degree Δ(L(G)) of L(G) satisfies

Δ(L(G)) ≤ 2Δ(G) − 2,

†email: higgins@saber.udayton.edu

∗Correspondence to: 3252 Greenmount Dr., Cincinnati, OH 45248-3940

and the minimum degree δ(L(G)) satisfies

δ(L(G)) ≥ 2δ(G) − 2.

The iterated line graph L^{k}(G) is defined recursively as L^{0}(G) = G, and L^{k}(G) = L(L^{k−1}(G)) for k ≥ 1. Though much is known about the line graph, few results are known for the iterated line graph. Some of these results can be found in [2]. Using the inequalities above, Niepel, Knor, and Šoltés [3] developed the following bounds for the maximum degree Δ_{k} and minimum degree δ_{k} of the iterated line graph L^{k}(G):

2^{k}(δ_{0} − 2) + 2 ≤ δ_{k} ≤ Δ_{k} ≤ 2^{k}(Δ_{0} − 2) + 2.

Thus, the maximum and minimum degree both have order Θ(2^{k}).

Niepel, et al., have conjectured that the maximum degrees of all iterated line graphs, with the exception of paths, eventually attain the maximum growth rate of Δ_{k+1} = 2Δ_{k} − 2. In this paper, we say that a graph G has the Maximum Degree Growth Property (MDGP) if Δ(L(G)) = 2Δ(G) − 2. Thus, the conjecture states that there exists an integer K such that, for all k ≥ K, L^{k}(G) possesses the MDGP. The focus of this paper is to present a proof of this conjecture.

In the following work, only finite simple connected graphs with no loops are considered. Note that the iterated line graph of a path eventually becomes the empty graph and that the iterated line graphs of cycles and K_{1,3} (whose line graph is a triangle) trivially satisfy the conjecture. Therefore, we consider only graphs that are not contained in these classes.

2 The Maximum Degree Induced Subgraph

We begin with some basic definitions.

Definition 1. Let Δ(G) be the maximum degree among the vertices of G, and δ(G) be the minimum degree. Let Δ_{k} denote Δ(L^{k}(G)) and δ_{k} denote δ(L^{k}(G)).

Definition 2. A graph G has the Maximum Degree Growth Property (MDGP) if Δ(L(G)) = 2Δ(G) − 2.

The conjecture of Niepel, Knor, and Šoltés can now be stated as follows.

Conjecture 3. [3] Let G be a connected graph that is not a path. Then there exists an integer K such that, for all k ≥ K, L^{k+1}(G) has the MDGP; that is,

Δ_{k+1} = 2Δ_{k} − 2.

We now introduce the maximum degree induced subgraph M(G) which will enable us to characterize those graphs G possessing the MDGP.

Definition 4. Let the maximum degree induced subgraph M(G) be the subgraph of G induced by the vertices of G that have maximum degree Δ(G). Let M_{k} denote M(L^{k}(G)).

Lemma 5. The MDGP holds for a graph G if and only if M(G) contains an edge.

Proof. If M(G) contains an edge then two vertices of degree Δ(G) are adjacent, and the edge joining these vertices will create a vertex of degree Δ(L(G)) = 2Δ(G) − 2 in L(G).

Inversely, if M(G) does not contain an edge, then no two vertices of degree Δ(G) are adjacent, and Δ(L(G)) < 2Δ(G) − 2.

Note that Lemma 5 implies that the MDGP holds for all L^{k}(G), k ≥ 0, if and only if M_{k} contains at least one edge for all k ≥ 0.

The following lemma is a well-known result on line graphs, and is stated without proof.

Lemma 6. If H is a subgraph of G, then L(H) is an induced subgraph of L(G).

We can now prove another characterization of graphs for which the MDGP holds.

Lemma 7. The MDGP holds for a graph G if and only if L(M(G)) ≅ M(L(G)).

Proof. Assume that the MDGP holds for G. Then M(G) has an edge, and by Lemma 6, L(M(G)) is a nonempty subgraph of L(G). Since every edge in M(G) is incident to two vertices of degree Δ(G), then for all vertices v ∈ L(M(G)), deg_{L(G)}(v) = 2Δ(G) − 2 = Δ(L(G)) and thus v ∈ M(L(G)). Suppose v is a vertex in M(L(G)). Since deg_{L(G)}(v) = Δ(L(G)) = 2Δ(G) − 2, the edge e corresponding to v in M(L(G)) must be incident to two vertices in G of degree Δ(G). Thus, e is an edge in M(G), and v ∈ L(M(G)). Therefore, the vertex sets of M(L(G)) and L(M(G)) are equal. Since both M(L(G)) and L(M(G)) are induced subgraphs of L(G), the adjacencies of M(L(G)) and L(M(G)) are exactly the same. Therefore, L(M(G)) ≅ M(L(G)).

Inversely, assume that the MDGP does not hold for G. By Lemma 5, M(G) does not contain an edge. Thus, L(M(G)) is defined on an empty vertex set. But M(L(G)) cannot be the empty graph since L(G) is a finite non-empty graph (G is not a path or a single vertex) and at least one vertex in L(G) must have maximum degree. Therefore, M(L(G)) ≅ L̸(M(G)).

Corollary 8. If L^{k}(M(G)) contains an edge for all k ≥ 0, then the MDGP will hold for all L^{k}(G), k ≥ 0.

Proof. If L^{k}(M(G)) contains an edge for all k ≥ 0, then, by Lemma 7, M_{k} contains an edge for all k ≥ 0, and the result follows by Lemma 5.

Corollary 8 proves the conjecture for many graphs, since we only need to consider whether or not L^{k}(M(G)) always has an edge for k ≥ 0. Paths and (vertex-disjoint) unions of paths are the only graphs that do not satisfy this condition, and thus the maximum degree growth of graphs whose M(G) are paths or unions of paths remains unresolved with the techniques presented thus far. The concept of the maximum degree induced subgraph is insufficient for these cases because it provides no information about M_{k+1} if M_{k} does not contain an edge. In the next section, we introduce the concept of a local maximum induced subgraph in order to resolve these difficulties.

3 The Local Maximum Induced Subgraph

Definition 9. Let the neighborhood N_{G}(v) of a vertex v in G be the set of vertices in G adjacent to v. Note that v ∉ N_{G}(v).

Let the neighborhood N_{G}(S) of a subgraph S of G be the set of vertices adjacent to vertices in S but not contained in S. Thus, N_{G}(S) = (∪{N_{G}(v) : v ∈ S}) \S.

Definition 10. A vertex v in G is a local maximum if deg_{G}(v) ≥ deg_{G}(w) for all w ∈ N_{G}(v).

If u and w are the endpoints of an edge e in G, then uw is an alternative notation for the vertex v ∈ L(G) that corresponds to e. This notation suggests the following definition.

Definition 11. A vertex v ∈ L(G) is generated by a vertex u ∈ G if the edge e in G that corresponds to v is incident to u. A subgraph J of L(G) is generated by a subgraph H of G if, for each vertex v ∈ J, v is generated by a vertex in H.

Note that for a given J, H is in general not unique.

Lemma 12. Every local maximum v in L(G) is generated by a local maximum w in G. Moreover, v is generated by w and a vertex in G that is maximum in N_{G}(w).

Proof. Suppose v is in L(G) and v is generated by x, y ∈ G, where x, y are not local maxima in G. Assume that deg_{G}(x) ≤ deg_{G}(y). Then there exists a vertex w ∈ N_{G}(y) such that deg_{G}(w) > deg_{G}(y). The vertex wy in L(G) has deg_{L(G)}(wy) = deg_{G}(w) + deg_{G}(y) − 2 > deg_{G}(x) + deg_{G}(y) − 2 = deg_{L(G)}(v). Vertex wy is in N_{L(G)}(v); therefore, v is not a local maximum.

For the second part of the lemma, assume that v is a local maximum in L(G), where v is generated by w, y ∈ G, w is a local maximum in G and y is not maximum in N_{G}(w). There exists a vertex z ∈ N_{G}(w) such that deg_{G}(z) > deg_{G}(y). The vertex wz in L(G) has deg_{L(G)}(wz) = deg_{G}(w) + deg_{G}(z) − 2 > deg_{G}(w) + deg_{G}(y) − 2 = deg_{L(G)}(v). Vertex wz is in N_{L(G)}(v); therefore, v is not a local maximum, resulting in a contradiction.

Definition 13. Let the local maximum induced subgraph 𝔏𝔐(G) be the subgraph of G induced by local maximum vertices. Let 𝔏𝔐_{k} denote 𝔏𝔐(L^{k}(G)).

We now develop some useful properties of the components of 𝔏𝔐(G).

Lemma 14. Let C be a component of 𝔏𝔐(G). Then all vertices in C have the same degree in G.

Proof. Let u, v be adjacent vertices in a component C of 𝔏𝔐(G), where deg_{G}(u) ≠ deg_{G}(v). Then deg_{G}(u) > deg_{G}(v) and v is not a local maximum, or deg_{G}(u) < deg_{G}(v) and u is not a local maximum, generating a contradiction.

Similar to the individual local maxima, the components of 𝔏𝔐(L(G)) can be determined by the components of 𝔏𝔐(G). This property is shown in the following lemmas.

Lemma 15. If a component C of 𝔏𝔐(G) contains an edge, then L(C) is a component of 𝔏𝔐(L(G)).

Proof. By Lemma 12, every vertex in 𝔏𝔐(L(G)) is generated by a vertex in 𝔏𝔐(G). Let C be a component of 𝔏𝔐(G) that contains an edge, where deg_{G}(v) = r for all v ∈ C. If v and w are adjacent vertices in C, then the degree of the vertex vw in L(G) is deg_{L(G)}(vw) = 2r − 2. By Lemma 6, and since the line graph preserves connectivity, L(C) is a connected induced subgraph of L(G), where every vertex in L(C) has degree 2r − 2.

To complete the proof of the lemma, we show that no vertex in N_{L(G)}(L(C)) is a local maximum. Every vertex vy in N_{L(G)}(L(C)) is generated by a vertex y ∈ N_{G}(C) that is adjacent to a vertex v ∈ C. If deg_{G}(y) < r, then deg_{L(G)}(vy) < 2r − 2, and vy is not a local maximum in L(G). If deg_{G}(y) = r, then since y ∉ C there exists a vertex z ∈ N_{G}(y)\C such that deg_{G}(z) > r. Then deg_{L(G)}(yz) > 2r − 2 = deg_{L(G)}(vy), and vy is not a local maximum in L(G). Therefore, no vertex in N_{L(G)}(L(C)) is a local maximum, and thus L(C) is a component of 𝔏𝔐(L(G)).

Lemma 16. Let C be a component of 𝔏𝔐(G) that does not contain an edge (C consists solely of a vertex v), and let s be the maximum degree of vertices in N_{G}(v). Then the following hold:

1. If s = deg_{G}(v), then no vertex in L(G) generated by v is a local maximum.

2. If s < deg_{G}(v), and if for all u ∈ N_{G}(v) with deg_{G}(u) = s there exists w ∈ N_{G}(u)\{v} such that deg_{G}(w) > deg_{G}(v), then no vertex in L(G) generated by v is a local maximum.

3. If s < deg_{G}(v), and if for a given u ∈ N_{G}(v) with deg_{G}(u) = s, deg_{G}(w) < deg_{G}(v) for all w ∈ N_{G}(u)\{v}, then v will generate a local maximum in L(G) for each such u. All local maxima thus generated will be adjacent.

4. If s < deg_{G}(v), and if for a given u ∈ N_{G}(v) with deg_{G}(u) = s there exists w ∈ N_{G}(u)\{v} such that deg_{G}(w) = deg_{G}(v), then v will generate locally maximum vertices in L(G) that are adjacent, and the locally maximum vertices generated by v will be adjacent to other locally maximum vertices in L(G) that are generated by a different component in 𝔏𝔐(G).

Proof. Let deg_{G}(v) = r, and let u ∈ N_{G}(v) have maximum degree in N_{G}(v). Note that all local maxima in L(G) generated by v, if any, will be adjacent to each other.

Let y ∈ N_{G}(v), where deg_{G}(y) < s. So y is not maximum in N_{G}(v). Then deg_{L(G)}(vy) < r +s−2 = deg_{L(G)}(vu), and vy is not a local maximum in L(G). Thus, only vertices generated by v and vertices maximum in N_{G}(v) can be locally maximum in L(G).

Assume that deg_{G}(u) = r = deg_{G}(v). Since u ∉ C there exists a vertex w ∈ N_{G}(u)\{v} such that deg_{G}(w) > r. Then deg_{L(G)}(uw) > 2r − 2 = deg_{L(G)}(vu), and vu is not a local maximum in L(G), proving part 1.

Assume that r = deg_{G}(v) > deg_{G}(u) = s. If there exists a vertex w ∈ N_{G}(u)\{v} such that deg_{G}(w) > r, then deg_{L(G)}(uw) > r + s − 2 = deg_{L(G)}(vu), and vu is not a local maximum in L(G). If such a vertex w exists for all maximum degree vertices in N_{G}(v), then no vertex in L(G) generated by v is a local maximum, proving part 2. If deg_{G}(w) ≤ r for all w ∈ N_{G}(u)\{v}, then deg_{L(G)}(vu) = r + s − 2 ≥ deg_{L(G)}(uw), and vu is a local maximum in L(G). This proves part 3. If there exists a vertex w ∈ N_{G}(u)\{v} such that deg_{G}(w) = r, then deg_{L(G)}(uw) = r + s − 2 = deg_{L(G)}(vu), and vu and uw are adjacent local maxima in L(G), proving part 4. Note that vertices vu and uw are in the same component of 𝔏𝔐(L(G)), but the component is generated by more than one component in 𝔏𝔐(G).

Thus, we now know the possible effects of the line graph on components of 𝔏𝔐_{k}. However, we can determine the exact effect on a component of 𝔏𝔐_{k} if k is large enough.

Corollary 17. Each component of 𝔏𝔐(L(G)) is generated by components of 𝔏𝔐(G), and each component of 𝔏𝔐(G) generates at most one component of 𝔏𝔐(L(G)).

Proof. The first part of the corollary follows from Lemma 12, and the second part follows from Lemmas 15 and 16.

Corollary 18. There exists an integer J_{1} such that every component of 𝔏𝔐_{k} generates a component of 𝔏𝔐_{k+1} for k ≥ J_{1}, and every component of 𝔏𝔐_{k+1} is generated by exactly one component of 𝔏𝔐_{k}.

Proof. Let c_{k} denote the number of components of 𝔏𝔐_{k}. By Corollary 17, the sequence {c_{k}} is non-increasing. Since G is a finite graph, there exist vertices of maximum degree, and thus 𝔏𝔐_{k} is nonempty and c_{k} ≥ 1 for all k. Therefore, there exists an integer J_{1} such that c_{k} is constant for k ≥ J_{1}. Using Corollary 17, the statement of this corollary follows.

The following notation will allow us to consider a particular component C_{J_{1}} of 𝔏𝔐_{J_{1}} and the components in 𝔏𝔐_{k} that C_{J_{1}} generates for k > J_{1}.

Definition 19. Let J_{1} be the integer given in Corollary 18, and let {C_{k}}_{k≥J_{1}} be a sequence such that C_{k} is a component of 𝔏𝔐_{k} and C_{k+1} is generated by C_{k}. Let r_{k} = deg_{L^{k}(G)}(v) for all v ∈ C_{k}.

Lemma 20. For k ≥ J_{1} given in Corollary 18, let u ∈ N_{L^{k}(G)}(C_{k}) where deg_{L^{k}(G)}(u) = a. Then there exists a vertex v ∈ L^{k+1}(G) generated by u where deg_{L^{k+1}(G)}(v) = r_{k} + a − 2, and either v ∈ N_{L^{k+1}(G)}(C_{k+1}) or v ∈ C_{k+1}.

Proof. Let w be a vertex in C_{k} that is adjacent to u ∈ N_{L^{k}(G)}(C_{k}). Then the degree of v = uw in L^{k+1}(G) is r_{k} + a − 2. Since C_{k} generates C_{k+1}, there exists a vertex z ∈ N_{L^{k}(G)}(w) such that wz ∈ C_{k+1}. If deg_{L^{k}(G)}(u) = deg_{L^{k}(G)}(z), then v ∈ C_{k+1}; otherwise, v ∈ N_{L^{k+1}(G)}(C_{k+1}).

Note that if C_{k} has an edge, then

\begin{aligned}r_{k+1} − deg_{L^{k+1}(G)}(v) & = (2r_{k} − 2) − (r_{k} + a − 2) \\ & = r_{k} − a. \end{aligned}

If C_{k} does not have an edge, then

\begin{aligned}r_{k+1} − deg_{L^{k+1}(G)}(v) & < (2r_{k} − 2) − (r_{k} + a − 2) \\ & = r_{k} − a. \end{aligned}

Note also that if two vertices u_{1} and u_{2} in L^{k}(G) are adjacent to a common vertex w in C_{k}, then vertices v_{1} = u_{1}w and v_{2} = u_{2}w are adjacent in L^{k+1}(G).

The following lemma is another well-known result on iterated line graphs, and is presented without proof.

Lemma 21. Let G be a connected graph that is not a path, cycle, or K_{1,3}. Then for all integers q there exists an integer Q such that δ_{Q} > q.

We now proceed with our characterization of the components of 𝔏𝔐_{k}.

Lemma 22. There exists an integer J_{2} such that C_{J_{2}} contains an edge.

Proof. Assume that there does not exist an integer J_{2} such that C_{J_{2}} contains an edge. Assume that J_{1} given in Corollary 18 is large enough such that, by Lemma 21, δ_{J_{1}} > 1. Then r_{J_{1}} > r_{J_{1}} − δ_{J_{1}} + 1. Since r_{J_{1}} − δ_{J_{1}} + 1 represents the number of possible degrees a vertex in N_{L^{J_{1}}(G)}(C_{J_{1}}) can have, by the Pigeonhole Principle there exist two vertices of the same degree adjacent to every vertex in C_{J_{1}}. Let w ∈ C_{J_{1}}. Then there are two vertices x_{J_{1}} and y_{J_{1}} of degree a_{J_{1}} adjacent to w. Construct a sequence of pairs of vertices {(x_{k}, y_{k})}, where x_{k+1} is generated by x_{k} as described in Lemma 20 and similarly for y_{k+1}. Thus, the degree a_{k+1} of x_{k+1} and y_{k+1} is given by a_{k+1} = a_{k} + r_{k} − 2. Both vertices in each pair (x_{k}, y_{k}) are adjacent to one another for k > J_{1}, since x_{k−1} and y_{k−1} are adjacent to a common vertex in C_{k−1}. Since, for k ≥ J_{1}, C_{k} does not contain an edge, r_{k+1} − a_{k+1} < r_{k} − a_{k}. Thus, there must exist an integer P where r_{P} − a_{P} = 0. This implies that C_{P} contains two vertices and thus must contain an edge, which is a contradiction.

Lemma 23. If there does not exist an integer P such that C_{k} contains an edge for all k ≥ P, then there exists an integer J_{3} such that there are three vertices in N_{L^{J_{3}}(G)}(C_{J_{3}}) where all three vertices have the same degree and are adjacent to the same vertex in C_{J_{3}}.

Proof. Assume that there does not exist an integer P such that C_{k} contains an edge for all k ≥ P. By Lemma 22, there exists an integer J_{2} such that C_{J_{2}} contains an edge. Let J_{3} be the smallest integer greater than J_{2} such that C_{J_{3}} does not contain an edge. Then C_{J_{3}−1} contains exactly one edge and two vertices. Let b_{k} denote the minimum degree of vertices in N_{L^{k}(G)}(C_{k}). The component C_{J_{3}−1} generates C_{J_{3}}, where C_{J_{3}} consists of the single vertex w of degree r_{J_{3}} = 2r_{J_{3}−1} − 2. The minimum degree of vertices in N_{L^{J_{3}}(G)}(w) is b_{J_{3}} = r_{J_{3}−1} + b_{J_{3}−1} − 2. By Lemma 21, the minimum degree δ_{k} can be made arbitrarily large by iterating long enough, and thus b_{J_{3}−1} ≥ δ_{J_{3}−1} > 2 can be assumed. Then

b_{J_{3}−1} > 2
⇒ r_{J_{3}−1} − 1 > r_{J_{3}−1} − b_{J_{3}−1} + 1
⇒ 2r_{J_{3}−1} − 2 > 2 ((2r_{J_{3}−1} − 2) − (r_{J_{3}−1} + b_{J_{3}−1} − 2) + 1)
⇒  r_{J_{3}} > 2(r_{J_{3}} − b_{J_{3}} + 1).  (∗)

Since r_{J_{3}} −b_{J_{3}} +1 represents the maximum number of degrees a vertex in N_{L^{J_{3}}(G)}(C_{J_{3}}) can have, by the Pigeonhole Principle and inequality (∗), w has at least three adjacent vertices that have the same degree.

Lemma 24. There exists an integer J_{4} such that C_{k} contains an edge for all k ≥ J_{4}.

Proof. Assume that there does not exist an integer P such that C_{k} contains an edge for all k ≥ P. Then by Lemma 23 there exists an integer J_{3} such that there are three vertices x_{J_{3}}, y_{J_{3}}, and z_{J_{3}} in N_{L^{J_{3}}(G)}(C_{J_{3}}) where all three vertices have the same degree a_{J_{3}} and are adjacent to the same vertex w in C_{J_{3}}. Construct a sequence of triples of vertices {(x_{k}, y_{k}, z_{k})}, where x_{k+1} is generated by x_{k} as described in Lemma 20 and similarly for y_{k+1} and z_{k+1}. Thus, the degree a_{k+1} of x_{k+1}, y_{k+1}, and z_{k+1} is given by a_{k+1} = a_{k} + r_{k} − 2. The vertices in each triple (x_{k}, y_{k}, z_{k}) are adjacent to one another for k > J_{3}, since x_{k−1}, y_{k−1}, and z_{k−1} are adjacent to a common vertex in C_{k−1}. Since C_{k} does not contain an edge for all k ≥ J_{3}, there exists an infinite number of integers k ≥ J_{3} where C_{k} does not contain an edge and where r_{k+1} − a_{k+1} < r_{k} − a_{k}. Thus, there must exist an integer Q where r_{Q} −a_{Q} = 0. This implies that (x_{Q}, y_{Q}, z_{Q}) forms a triangle in C_{Q}, and thus C_{k} will contain an edge for all k ≥ Q.

We now have all the necessary lemmas to prove the conjecture.

Theorem 25. For all connected graphs G that are not paths, there exists an integer K such that the MDGP will hold for L^{k}(G) for all k ≥ K.

Proof. By Lemma 24 and since 𝔏𝔐_{k} has a finite number of components, there exists a K such that every component of 𝔏𝔐_{k} contains an edge for all k ≥ K. By Lemma 14, M_{k} is a subset of the components in 𝔏𝔐_{k}. Thus, M_{k} contains an edge for all k ≥ K, and, by Lemma 5, the MDGP will hold for all k ≥ K.

4 Conclusion

Theorem 25 proves the existence of an integer K such that the MDGP will hold for all k ≥ K. From this result, we can conclude that the formula Δ_{k} = 2^{k−K}(Δ_{K} −2)+2 holds for all k ≥ K. However, this formula is not particularly useful unless the least integer K such that the MDGP will hold for all k ≥ K can be determined. The calculation of this tight bound for a given graph remains an open question.

Niepel, Knor, and Šoltés in [3] also posed a corresponding conjecture for the minimum degree δ_{k}: There exists an integer P such that δ_{k+1} = 2δ_{k} − 2 for k ≥ P. Even though analogous minimum degree induced subgraphs and local minimum induced subgraphs can be defined, the authors have been unable to prove lemmas corresponding to Lemmas 22 and 23 for the minimum degree case. This conjecture also remains an open question.

Acknowledgments

The first author wishes to thank the University of Dayton Honors Program for support of his Honors Thesis, of which this work is a part. We also thank the referees for their suggestions.

References

[1] R. L. Hemminger and L. W. Beineke, “Line Graphs and Line Digraphs,” in L. W. Beineke and R. J. Wilson, ed., Selected Topics in Graph Theory, Academic Press, New York, 1978, pp. 271-305.

[2] C. Hoover, “The Behavior of Properties of Graphs under the Line Graph Operation,” University of Dayton Honors Thesis, 1991.

[3] L’. Niepel, M. Knor, and L’. Šoltés, “Distances in Iterated Line Graphs,” Ars Combinatoria 43 (1996), pp. 193-202.