GRAPHS AND THEIR‘ ASSOCIATED LINE-GRAPHS Thesis for the Degree of Ph. D. MICHIGNN STATE UNIVERSITY Gary Theodore Chartrand 19.64 0-169 00671 9 u WWWmm «L This is to certify that the thesis entitled Graphs and Their Associated Line-Graphs presented by Gary Theodore Chartrand has been accepted towards fulfillment ‘ of the requirements for I Ph.D. degree in Mathematics I i 36552’7 ' ajor professor I Dme May 20, 196% LIBRARY Winn» PVISSI.J RETURNING MATERIALS: PIace in book drop to LJBRARJES remove this checkout from .—__. your record. FINES will be charged if book is returned after the date stamped below. ABSTRACT GRAPHS AND THEIR ASSOCIATED LINE—GRAPES by Gary Theodore Chartrand With every ordinary graph G there is associated a graph L(G), called the line—graph of G) whose vertices are in one-to~one correspondence with the edges of G and having the property that adjacency is preserved. The con- cept of the line-graph was originated in 1932 by H. Whitney, In the 32 years which have elapsed since then, the litera- ture on this subject has been quite sparse. The purpose of this thesis is to add to the knowledge of line-graphs. Sectionl_consists of the introduction in which the origin of the thesis problem is presented and in which are outlined the tOpics treated in the sections which followt Section 2 contains definitions of the technical terms which are basic to graph theory and which are used throughout the thesis. In this same section we also establish some of the notation to be used“ A brief history of the literature on -line-graphs of ordinary graphs is presented in Section 3. Numerous preliminary and elementary results are given in Section 4. Among these are: (l) the only graphs which are isomorphic to their line-graphs are the regular graphs of degree two; (2) a necessary and sufficient condition Gary Theodore Chartrand that the sequence {Ln(3)} of repeated line-graphs of a graph G be infinite is that at least one component of G be other than an arc; (3) for every connected graph G which is not an arc, there exists a nonnegative interger N such that for all ij N, Lp(G) is nonseparable. (The exact value of N is given for every such graph.) Connectedness relations between graphs and their line- graphs are investigated in Section 5. In particular, it is shown that: (I) if a graph G is m-edge connected, then L(G) is (2m-2)-edge connected; and (2) if G is m-connected, then L(G) is m-connected. Examples are given to show that in general these results cannot be improved. Section 6 is devoted to Euler graphs. It is shown that the line-graph of an Euler graph is an Euler graph; however, the main theorem is: A necessary and sufficient condition that some repeated line-graph of a connected graph G be Euler is that every edge of G have the same parity. In par— ticular, if a graph G has this property, then L2(G) is an Euler graph. In Section 7 the notion of sequential graphs is intro- duced, and the relationship between such graphs and Hamilton line-graphs is given. It is in this section that the major theorem of the thesis is presented, namely: Let G be any connected graph of order n which is not an arc. Then there exists a unique nonnegative integer h(G), called the Hamilton index of G, such that for all p 2;h(G), Lp(G) is a Hamilton Gary Theodore Chartrand graph; furthermore, h(G).£:n-3, and the upper bound n—3 cannot, in general, be improved. Triangle relations in repeated line-graphs of regular graphs G of degree r:>2 are given in Section 8. It is shown there that the probability approaches one as n approaches infinity that if three vertices are selected at random from Ln(G), then these will be the vertices of an "empty” triangle in Ln(G). The thesis is concluded with Section 9 in which are presented some miscellaneous results dealing with line-graphs. The chief theorems of the section are: (l) a necessary and sufficient condition that a graph be the line-graph of a tree is that it be a completed Husimi tree, all of whose vertices have connective index at most two; (2) the only bipartite line-graphs are arcs and circuits of even length; (3) the line—graph of a nonplanar graph is nonplanar. GRAPHS AND THEIR ASSOCIATED LINE-GRAPHS By Gary Theodore Chartrand A THESIS Submitted to Michigan State University in partial fulfillment of the requirement for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1964 ACKNOWLEDGMENTS The interest shown by many individuals in this thesis and in graph theory, in general, has made the development of this thesis a most enjoyable and rewarding experience. To all these peOple, I give my most sincere thanks. First and foremost must the name of Professor E. A. Nordhaus be mentioned. To say that I appreciate all the time he has taken for me, all the things he has taught me, and all the kindly advice he has given me, is certainly an understatement. For everything he has done for me, I am indeed most grateful. I wish next to express my gratitude to Professor L. M. Kelly for the interest he has displayed, for the dis- cussions I have had with him, and for the advice and sugges- tions he has given me. To Professors B. M. Stewart and Frank Harary go my sincere thanks for their interest. I would also like to thank Professors J. G. Hocking and R. H. Wasserman for serving on my guidance committee. ii DEDICATION to my Mother, my Father, and Mark. iii Section H .t I» m U1 9. TABLE OF CONTENTS INTRODUCTION NOTATION AND BASIC DEFINITIONS A SURVEY OF KNOWN RESULTS. FUNDAMENTAL PROPERTIES OF AND PRELIMINARY RESULTS CONCERNING LINE-GRAPHS . THE CONNECTIVITY OF LINE-GRAPHS. LINE-GRAPHS AND EULER PATHS SEQUENTIAL GRAPHS; LINE-GRAPHS AND HAMILTON CIRCUITS . . . TRIANGLE RELATIONS IN REPEATED LINE-GRAPHS OF REGULAR GRAPHS . . . . . MISCELLANEOUS RESULTS ON LINE-GRAPHS INDEX OF DEFINITIONS BIBLIOGRAPHY . iv Page 16 32 56 74 82 90 92 LIST OF FIGURES Figure Page 3.1 11 3.2 13 5.1 . . . . . . . . . . . 45 5.2 1+8 7.1 57 7.2 57 7-3 57 7.4 57 7.5 66 7.6 67 7.7 73 9.1 87 9.2 89 SECTION I INTRODUCTION In 1932 the paper ”Congruent Graphs and the Connec- tivity of Graphs” by H. Whitney appeared in the American Journal of Mathematics [15]. This paper contained a theorem which led to the definition of ”line-graph” we are about to give, and it is the development of this con— cept with which we are concerned. The problem of investi— gating the properties of repeated line-graphs was suggested by Ore (see [11], page 21, problem 7). Definition 1.1 The line—graph L(G) of an ordinary graph G is that graph whose vertex set can be put in one—to-one correspondence with the edges of G in such a way that two vertices of L(G) are joined by an edge if and only if the corresponding edges of G have a vertex in common. By L2(G) we shall mean L(L(G)), and, in general, n(G) = L(Ln-1(G)) for h 332. For L(G) we shall sometimes 1 ( L write L G), and LO(G) will mean G itself. The graphs Ln(G), n522, will be referred to as the repeated line-graphs of G. The term ”line-graph” employed by Harary [6], is alternatively referred to as ”interchange graph" by Ore [ll] II and derivativeH by Sabidussi [12]; however, we shall use "line-graph” throughout the paper. Definitions of technical terms which are basic to graph theory and which are used in this thesis are presented in Section 2, as well as a few remarks regarding notation. In Section 3, we give a survey of the known literature on line-graphs. Several preliminary and furdamental results concerning line-graphs are given in Section A. Many of these results are used throughout the thesis. In Section 5 we discuss the relationship between the connectivity of a graph and that of its line-graph. The corresponding relationship with edge connectivity is also investigated. Sections 6 and 7 deal with the problems of line~graphs containing Euler paths and Hamilton circuits, respectively. In particular, conditions are given under which repeated line-graphs of a given graph contain Euler paths or Hamilton circuits. In Section 8 we investigate some numerical results involving the number of vertices, edges, and the various types of triangles which occur in repeated line-graphs of regular graphs of degree r;.2. The concluding Section 9 contains a number of miscel~ laneous results on linowgraphs dealing with trees, bigraphs, and planar and nonplanar graphs. SECTION 2 NOTATION AND BASIC DEFINITIONS The subject of graph theory is presently in the posi— tion of having many different terms used for the same con- cept. It therefore seems advisable to define those terms which are fundamental to graph theory and which are used in this thesis. These definitions are presented in this sec- tion, as is some of the notation which is used later. In order to give a definition of a graph, we begin with a finite nonempty set V, whose elements we call points or vertices. We refer to V as the vertex set. A graph G with vertex set V is a set (possibly empty) of pairs of elements of V. The elements of G are called lipgp or gdgpp. To emphasize the fact that G has vertex set V, we often write G(V) for G. If E = (a,b) is an edge of G(V), then we say E joins a and b. An edge of the type (a,a) is called a lppp. We shall omit loops entirely from our consideration. If a graph G = G(V) consists of ordered pairs of vertices, then G is called a directed graph (or simply a digraph) and the edges of G are referred to as directed edges. If G con- sists of unordered pairs of vertices, then G is an undirected graph. An undirected graph without 100ps is called an ordinary graph, and with the one exception noted in Section 3 7, the word "graph” in this thesis is understood to mean "ordinary graph.” With regard to language, when we speak of the vertices of the graph G = G(V), we shall be referring to the vertices in V. If two vertices a and b are joined by an edge E, then a and b are said to be adjacent. Similarly, if two distinct edges El and E2 have a vertex in common, they are adjacent. If E = (a,b) is an edge of some graph, then E and a are said to be incident to each other, as are E and b. A vertex adjacent to no other vertex in a graph is called an isolated vertex. If a graph G consists only of isolated vertices, then G is called an empty graph. A trivial graph consists of one (isolated) vertex; thus, a nontrivial graph must nec- essarily contain at least two vertices. In contradistinction to an empty graph is a complete graph, in which all pairs of distinct vertices are adjacent. A complete graph with n vertices has n(n-l)/2 edges and is denoted by Kn: The graph K3 is called a triangle. The number of elements in the vertex set of a graph is referred to as the pgdgp of that graph. The number of vertices to which a vertex a is adjacent is called the degree pf_g and is denoted by )9(a). If a is an isolated vertex, then /0(a) = 0; while if G = G(V) is a complete graph of order n, then ,p(v) = n-l for every v 5 V3 An edge E = (a,b) is called a terminal edge if either f3(a)=l or /9(b)=l. If /9(a)=l, then a is a terminal vertex. A fundamental theorem states: If G = G(V) has m edges, then £23,F(v) = 2m. From this result it follows that every grdzx contains an even number of vertices having odd degrees. A graph H is called a subgraph of the graph G = G(V) if the vertex set of H is a nonempty subset of V, and if every edge of H is an edge of G. If a subgraph H of a graph G = G(V) is defined as a certain nonempty subset of the edges of G and the vertex set of H is not otherwise specified, then the vertex set of H shall be those vertices which are incident with at least one edge of H. If A is a nonempty subset of the vertex set V, then the subgraph G(A), whose vertex set is A and whose edges are all those edges in G which join two vertices of A, is called the section graph of G determined_py A or the subgraph of G generated py A. If A = V, then the section graph G(V) is G itself, which agrees with our earlier notation. If G is a graph having at least one edge and H is a proper subgraph of G (that is, G contains at least one more edge than H), then we can speak of the complement pf‘H 3p g, denoted by G-H, which is that subgraph of G consisting of those edges of G which are not in H. Under this definition, it is never possible for G-H to contain isolated vertices. 0| Similar to this is the concept of the complementary graph Of a graph G = G(V). G'is that graph whose vertex set is V and which contains all edges in the complete graph having vertex set V which are not in the graph G. ‘5 may very well contain isolated vertices; indeed, the complementary graph of a complete graph is an empty graph, and vice versa. Two graphs G and G' with vertex sets V and V', respectively, are isomorphic if there exists a one-to-one correspondence between V and V' such that two vertices are joined by an edge in one graph if and only if the corre- sponding vertices are joined by an edge in the other graph. A pgph in a graph G = G(V) is a sequence P of dis- tinct edges from G : E1 = (a,al), E2 = (a1, a2), . . . , En = (an_l,b), where the vertices need not be distinct. We say P is a path from a to b (or from b to a). If in the sequence P above, a = b (and so n 533), then P is called a cyplic path. If all vertices in a path are distinct, then the path is called an app. If a = b, but all other vertices are distinct, then the cyclic path is called a circuit or a pyplg. For the path P above, we often write P : (a,al,a2, . °:an~l:b)' If P is a cyclic path, we write P : (a,al,a2, . . .,an_l,b=a). By the section graph [0] f‘g circuit c (ao,al,...,an_l,an=ao) in G, we mean the section graph G(A), where A = {ao,al,...,an_¥3 . A diagonal of a circuit c is an edge in [C] which is not in C. It is well known and not difficult to prove that if there is a path from a to b, a £ b, in a graph G, then there is also an arc in G from a to b. Two vertices a and b are gppnected if a = b or if a £ b and there is an arc from a to b. A connected graph is a graph in which every pair of its vertices is connected. The relation ”is connected to” is an equivalence relation on V; therefore, there exists a decom- position of the vertex set V = LJVi into disjoint sets such that in each Vi, each pair of vertices is connected, while if a 5 Vi and b 6 VJ, i e j, then a is not connected to b. G can then be decomposed into disjoint connected section graphs G(Vi), called the connected components or simply the components of G. We write G = Z G(Vi), and say G is expressed as the direct sum of its components indicating that every vertex and every edge of G is in precisely one of the G(Vi). We say that G is expressed as the edge direct sum of the subgraphs, G1, G2,...,Gk, and write again G = 23 Gi’ if every vertex and every edge of G is in some Gi but no edge is in more than one Gi' Two subgraphs which have no vertex in common are called disjoint, and two subgraphs which have no edge in common are called edge disjoint. It therefore follows that the summands of a direct sum are pairwise dis- joint and the summands of an edge direct sum are pairwise edge disjoint. Clearly, disjoint subgraphs are edge disjoint, and a direct sum is also an edge direct sum, but the converse of neither is true; indeed, a graph G and its complementary graph G are always edge disjoint but never disjoint. The definitions of a few special types of graphs will be useful. A connected graph which contains no circuits is a tree. A graph G = G(V) is called regular pf degree §_if f7(v) = r for all ve V. A circuit is regular of degree two, and KD is regular of degree n-l. If we write V = Vl LS} V2 as a disjoint union of non— empty subsets of V, and G = G(V) is such that no two vertices of V1, 1 = l, 2, are adjacent, then G is called a bipartite graph or a bigraph. If V1 contains m vertices and V2 con- tains n vertices, then the bigraph in which all mn edges are present is called a complete bigraph and is denoted by Km,n or Kn,m' A complete bigraph of the type Kl,n is referred to as a star graph. SECTION 3 A SURVEY OF KNOWN RESULTS This section will be devoted to a brief history of the literature on line-graphs, which is quite sparse. We shall also mention here some easily verified elementary results. From the definition of”1ine-graph,” it follows at once that the line—graph L(G) of a graph G depends only on the edges of G and the way they are related to one another. This leads to the following. Theorem 3.1 Let G and G' be two nonempty graphs, and let H and H‘ be those subgraphs of G and G', respectively, ob- tained by deleting all isolated vertices of G and G'. If H and H' are isomorphic, then L(G) and L(G‘) are isomorphic. According to the preceding theorem, if we are given a linevgraph J, we can always find a graph G having no isolated vertices such that L(G) = J. We shall make use of this fact. Whether two nonisomorphic graphs, neither having isolated vertices, can have isomorphic line-graphs is the essence of the first theorem on line-graphs given by Whitney [15] in 1932. IO Theorem of Whitney If the line-graphs L(G) and L(G') of the connected graphs G and G' are isomorphic but different from K3, then G and G' are isomorphic. It is an easy exercise to show that L(K3) and L(Kl,3) are both K3 and that no other graph has the line-graph K3; thus, Whitney's theorem implies the existence of a one-to-one correspondence between connected graphs and line-graphs of connected graphs if the line—graph K3 is not considered. Since 1932, other proofs of Whitney's theorem have been given. One of these made use of the following interesting characterization of line-graphs given by Krausz (see [6]). Theorem of Krausz A graph is a line-graph if and only if it can be expressed as an edge direct sum of complete sub- graphs in such a way that no vertex is contained in more than two of these subgraphs. It is not difficult to show that a line-graph L(G) can be expressed as an edge direct sum of complete subgraphs in such a way that every vertex belongs to exactly two of these subgraphs unless G has terminal edges, so, in particular, this result holds if G is a regular graph of degree r E?2. With the aid of Krausz‘ theorem, the following result is easily established. Theorem 3.2 There exist graphs which are not line—graphs. Proof. Consider the star graph Kl,3° The only complete subgraphs in K1,3 are edges, so if K1 3 is expressed as an ) II edge direct sum of complete subgraphs, then necessarily one vertex will be contained in three such subgraphs. Hence, Kl,3 is not a line-graph. As Ore [11] pointed out, with every graph G = G(V) one can associate various matrices called incidence matrices. One such matrix is the so-called vertex incidence matrix which we shall denote by MV(G). The usual way of constructing this square matrix is as follows. Every edge of G can be con- sidered as an element of the product space V x V. The elements of V x V can be represented in a square array with the elements of V serving as coordinates along the two axes (Fig— ure 3.1). V1 ooooo Vj oooooo Vn V1 ; Figure 3.1 vi ........ ;(Vi’ v3) Vn It is customary to take the elements of V in the same order along each axis. At the position wimacoordinates(vi, VJ) we place 1 or 0 depending on whether there is or is not a corresponding edge in G. We thus obtain the matrix MV(G). The matrix MV(G) is a symmetric matrix having all diagonal entries equal to O. Another matrix is the edge incidence matrix N%(G) of G where both rows and columns correspond to 12 the edges of G, the edges taken in the same order along both row and column. At a position (El’ E2) we place 1 or G de- pending on whether E1 and E2 are or are not adjacent. As with MV(G), MG(G) is a square symmetric matrix all of whose diagonal entries are O. It is possible to consider Me(G) as the vertex incidence matrix of a new graph G1 whose vertices are in one-to—one correspondence with the edges of G. It is then easily seen that the graph G1 is the line-graph L(G). Figure 3.2 gives an example. In recent years investigations have been made to deter— mine how closely various properties of line-graphs of special graphs seem to characterize these graphs. The first theorem along this line is given next (see [3], [8], and [13]). It was proved in parts and completed in 1960. Theorem of Conner, offman, and Shrikhande If G is a graph of order n(n-1)/2, n 2'4, having the following three properties: (i) every vertex of G has degree 2(n-2), (ii) every two adjacent vertices are mutually adjacent to n—2 other vertices, (iii) every two nonadjacent vertices are mutually adjacent to four vertices, then G is isomorphic to L(Kn) except when n = 8, in which case there are precisely three counter examples. The corresponding theorem for complete bigraphs appeared in 1963 [9]~ l3 1 A c A c G L(G) E 2 A B B D 3 1 2 3 A 1 o 1 o 1 2 1 o 1 1 Mv(G): o 1 o 1 LL 1 1 1 o A B C D E A o 1 1 o 1 B 1 o o 1 1 Me(G) .—. MV(L(G)) c 1 o o 1 1 D o 1 1 o 1 E 1 1 1 1 0 Figure 3.2 14 Theorem of J. W. Moon If G is a graph of order mn, m 2:n2: 1, having the following three properties: (i) every vertex of G has degree m + n - 2, (ii) there are nm (m-l)/2 pairs of adjacent vertices mutually adjacent to m—2 other vertices, and the remaining mn(n-l)/2 pairs of adjacent vertices are mutually adjacent to n-2 other vertices, (iii) every two nonadjacent vertices are mutually adjacent to two vertices, then G is isomorphic to L(Km,n) except possibly when (m,n) = (4,4), (4,3), or (5,4). Shrikhande [14] has shown there is precisely one counter example for (m,n) = (4,4), and from a discussion with Profes- sor Harary, I have learned that A. J. Hoffman has now verified Moon's theorem for (m, n) = (4,3) and (5,4); hence, the result is now complete. There is one other result in the literature which deals with line-graphs of ordinary graphs. This theorem falls within the realm of algebraic graph theory, a topic not con- sidered in this thesis. For the sake of completeness, however, we shall also state this result. A few introductory remarks are in order. With every graph G = G(V) there corresponds a group of automorphisms {“ = F"(G) consisting of all isomorphisms of G onto G, i.e., r" consists of all one-to-one correspondences f of V onto V such that when E = (a,b) is an edge in G, 15 E‘ = (f(a), f(b)) is also an edge in G, and conversely. (1 may thus be considered as a permutation group on V. The auto- morphism group of Kn is Sn’ the symmetric group of order n1, while the automorphism group of a circuit of length n is the dihedral group of order 2n. Perhaps the best known theorem in this area is due to Frucht (see [11]): For any finite group I"1 there exists a graph G such that F = F(G). The result on line—graphs [12] can now be given. Theorem of Sabidussi If G is a connected nontrivial graph not isomorphic to K2, K4, Q (the graph of order four having four edges and a vertex of degree three), or to L(Q), then I" (G) is isomorphic to F(L(G)). SECTION 4 FUNDAMENTAL PROPERTIES OF AND PRELIMINARY RESULTS CONCERNING LINE-GRAPES In this section we present several basic results which are fundamental in understanding the relationship between a graph and its line-graph. Many of these results will be used numerous times in the sections which follow. Theorem 4.1 Let G = G(V) be a graph with m edges and T triangles. Then the line-graph L(G) of G contains m vertices, v 2 ('0(\2]))edges, and T + Z (10(1)) triangles. Also, if e V 6 V v e V ” is the vertex in L(G) which corresponds to the edge E = (a,b) of G, then [0(e) has the value ,0(a) + [9(b) — 2. grggf. Since there is a one-to-one correspondence between the edges of G and the vertices of L(G) and G has m edges, L(G) has m vertices. Two vertices are joined by an edge in L(G) if and only if the corresponding edges in G are adjacent. The number of edges in L(G) is therefore the number of pairs of adjacent edges in G, which is 22:: (P(g)) v e V As we have seen, a triangle in a line-graph L(G) can be Generated in one of two ways, namely, by a triangle in G or by three edges in G having a common vertex; the number of these types of subgraphs in G is given by T and Z. ((091)), v 61] 16 17 respectively, thereby producing the desired result. If the vertex e in L(G) corresponds to the edge E = (a,b) of G, then B is adjacent to [ f’(a) - l] + [ /’(b) — l] = ,0(a) + flb) - 2 edges of G implying that e is adjacent to F(a) + ,0 (b) - 2 vertices in L(G) or that/(e)=/(a)+fl(b)—2. Q.E.D. With the aid of the preceding theorem, it is now an easy matter to give a characterization of regular line-graphs. We precede this, however, with two definitions and a lemma. Definition 4.1 The degree gf_an edge E = (a,b) in a graph G is defined to be the number )0(E) = ,0(a) + )0(b) —2, and is the number of edges in G adjacent to E. Definition 4.2 A graph G is said to be edge regular of degree r if every edge has the same degree r. Lemma 4.2 A vertex e in the line-graph L(G) of the graph G has the same degree as the degree of its corresponding edge in G. Proof. The proof is a direct consequence of Definition 4.1 and Theorem 4.1. Q.E.D. Theorem 4.3 A line-graph L(G) is regular of degree r if and only if G is edge regular of degree r. Proof. The proof follows immediately from Lemma 4.2. Q.E.D. An edge regular graph need not be regular as can be seen by considering star graphs having order three or more, but 18 every regular graph is edge regular implying that the line- graph of a regular graph is regular. We state this in the following theorem. Theorem 4.4 If G is a nonempty regular graph of degree r, then L(G) is a regular graph of degree 2r - 2, and if r.2:2, then for n = l, 2, 3, . . . , Ln(G) is a regular graph of degree 2n(r-2) + 2. m. If G is regular of degree r21, then G is seen to be edge regular of degree 2r - 2, and L(G) is regular of degree 2r - 2 by Theorem 4.3. The remaining part of the theorem follows by a routine application of mathematical (induction. Q.E.D. Before continuing with regular graphs, we present some facts which will be useful in the sequel. Theorem 4.5 If G is a nontrivial connected graph, then L(G) is connected. Conversely, if L(G) is connected (and G has no isolated vertices) then G is connected. .grggf. Let G be a nontrivial connected graph. If G consists of a single edge, then L(G) is a single vertex and so is connected; otherwise, let a and b be any two vertices in L(G), and let A = (a1, a2) and B = (b1, be) be the edges in G which correspond to a and b, respectively. If A and B are adjacent in G, then a and b are adjacent in L(G) and are connected; otherwise, since G is connected, a1 and b1 are l9 joined by an arc Q: E1, E2, . . ., Ek' Let e1, e2, . . ., 8k be the corresponding vertices in L( ). If A = El and B = Ek’ then P = (a, e2, . . . , ek-l’ b) is an arc in L(G) joining a and b. If A £ El but B = Ek’ e2, . . ., ek-l’ b) is an arc in L(G) joining a and b. The then P1 = (a, el, cases A = E], B e ER and A 2 E1, B a Ek are handled similarly, and we see that a and b are connected so that L(G) is con- nected. Conversely, let L(G) be connected, and let u and v be any two vertices of G. Since there are no isolated vertices in G either there is an edge (u, v) in G, in which case u and v are connected, or else there are two edges E = (u, ul) and F = (v, v1) in G. In the latter case let e and f be the two vertices in L(G) which correspond to E and F, respectively. Since L(G) is connected, e and f are connected by an arc S: {D (e, e1),(el, e2), . . . , (es-1’ f) which corresponds to path T : E, E1, E2, . . . , Es-l: F in G from u to v so that u and v are connected. Q.E.D. Theorem 4.5 immediately implies the following: Corollary 4.5.1 If 23 G1 is the direct sum decomposition of a graph G into its components, none of which are isolated vertices, then the line—graph L(G) can be expressed as the direct sum :3 L(Gi) of its components. One may ask if a statement analogous to Corollary 4.5.1 can be made when a graph is expressed as an edge direct sum. An answer is given in the negative by the following. 20 Theorem 4.6 If G is expressed as the edge direct sum H + K, neither H nor K having isolated vertices, then L(H) and L(K) are disjoint, hence edge disjoint, and L(G) can be expressed as the edge direct sum L(H) + L(K) + J, where J is a subgraph of L(G), each edge of which joins a vertex of L(H) to a vertex of L(K). J is an empty graph if and only if the edge direct sum H + K is direct. Pooof. The fact that L(H) and L(K) are disjoint follows by noticing that if some vertex were simultaneously in L(H) and in L(K), then there would exist an edge in G common to H and K contradicting the hypothesis that H and K are edge dis- joint. Sinceeverwredge of G lies either in H or in K, every vertex of L(G) is contained in either L(H) or L(K). An edge of L(G) is determined by two adjacent edges in G, and two such edges may lie both in H, both in K, or else one of the two adjacent edges must lie in H and the other in K resulting in an edge of L(H), an edge of L(K), or an edge neither in L(H) nor in L(K) but rather an edge joining a vertex of L(H) to a vertex of L(K), respectively. Let J denote the collec- tion of all edges in L(G) joining a vertex of L(H) to a vertex of L(K). We shall refer to an edge contained in a subgraph such as J as a ”cross edge.” It is now seen that L(G) can be expressed as the edge direct sum L(H) + L(K) + J. If H + K is a direct sum, then the fact that J is an empty graph is a simple consequence of Corollary 4.5.1. On 21 the other hand, if H + K is an edge direct sum but not a direct sum, then since H and K have no isolated vertices and are both nontrivial, it is easily seen that an edge of H must be adjacent to an edge of K producing an edge in J. Q.E.D. Immediate consequences of this theorem will be given next. Corollary 4.6.1 If H is a nonempty subgraph of G, then L(H) is a subgraph of L(G). Corollary 4.6.2 If H is a nonempty section graph of G, then L(H) is a section graph of L(G). Corollary 4.6.3 If H is a nonempty subgraph of G and G - H is the complement of H in G, then L(G-H) is the com- plement of L(H) in L(G) if and only if H and G-H are disjoint, i.e., if and only if H is the sum of components of G. Corollary 4.6.4 If G is expressed as the edge direct sum :2: Hi, where the Hi are without isolated vertices, then the L(Hi) are pairwise disjoint, and L(G) can be expressed as the edge direct sum 2: L(Hi) + J, where J is a subgraph of L(G), each edge of which joins a vertex of some L(Hi) to a vertex of some L(HJ), i £ j. J is an empty graph if and only if the edge direct sum 2 H1 is direct. We now return to regular graphs in order to present a theorem which solves the problem proposed by Ore of deter— mining all graphs isomorphic to their line-graphs (see [11], page 21, problem 5). The proof we give is chosen as an application of Theorem 4.1. 22 Theorem 4.7 The only graphs which are isomorphic to their line—graphs are the regular graphs of degree two. Proof. Let G be regular of degree two. By Corollary 4.5.1, we may assume G to be connected. Let the vertices of G be al, a2, . . ., an, ordered in such a way that the resulting n edges are (al, a2), (a2, a3), . . . , (an_l, an), (an, a1), whose corresponding vertices in L(G) are b1, b2, ., bn-l: bn, respectively. The one-to-one correspondence ai<———e>bi (i = l, 2, . . ., n) is then easily seen to be an isomorphism between G and L(G). Conversely, let G be a graph which is isomorphic to its line-graph L(G). Let G have n vertices, say v1, v2, ,vn, and m edges. Hence, L(G) has m vertices, and since G and L(G) are isomorphic, m = n. If G has T triangles, then L(G) I"! .(V') too must have T triangles implying that T = T + :(F f) 1:4. 3 F(Vi) (from Theorem 4.1) or that ;%% = 0, so that 1.: 3 flvi) g 2 for all i = 1, 2,... ., n. Since m .—. n, (v-) (V > n: i: ID 1 ,but P(vi) < 2so ,0 i =lorO i=1 2 _ 2 depending on whether [G(Vi) = 2 or /0(Vi) < 2. However, n pm) the sum has the value n and has n terms, so i=1 2 for each i = l, 2, . . . , n, we must have f9(vi) = 2; there- fore, G is regular of degree two. Q.E.D. Since a connected regular graph of degree two is simply a circuit, the graphs which are isomorphic to their line-graphs are those graphs whose components are simple circuits. In a I 0 LA) like manner one can show that if G contains a circuit, then L(G) contains an isomorphic circuit. We consider the repeated line-graphs of another special type of graph next. Theorem 4.8 If G is an arc of length n (n 2:1), then L(G) is an arc of length n-l. Proof. Let E1 = (a0, a1), E2 2 (a1, a2) . . . , En = (an-l: an) be the edges of G and let e1, e2, . . .,en be the corresponding vertices in L(G). Then the edges in L(G) are Fl = (e1, e2), F2 2 (e2, e3), . . . , Fn-l = (en_l, en), and so L(G) is an arc of length n-l. Q.E.D. Corollary 4.8.1 If G is an arc of length n (n 271), then Ln (G) consists of an isolated vertex (an arc of length zero), while for k >'n, there exists no graph Lk(G). It should be clear that the arcs and the circuits are the only connected graphs all of whose vertices have degree not exceeding two, so any other connected graph has one or more vertices of degree three or more. Theorem 4.9 A necessary and sufficient condition that the sequence ‘(IF(G)} be infinite is that at least one component of G be other than an arc. Proof. Let G be a graph such that the sequence {;Ln(G)} is infinite. If the components of G were all arcs and the maximum length of these arcs were N, then by Corollary 4.6.1, Lk(G) for k > N would not exist. On the other hand, if a com- ponent G1 of G were not an arc, then either G1 would be a 24 circuit or would contain a vertex v having degree three or more. If Gl were a circuit, L(Gl) and so Lk(Gl) for all k would be a circuit. If G1 contained a vertex v incident with three edges, then L(G and so Lk(Gl) for all k would 1) contain a triangle. Hence, Lk(G) exists for all k. Q.E.D. Definition 4.3 Let G be a graph for which the sequence { Ln(G)} is infinite. The sequence { Ln(G)} is said to have a limit graph if there ex1sts a positive integer N such that if m 27 N and p 27 N, then Lm(G) is isomorphic to Lp(G). LN(G) is then called the limit graph of { Ln(G) } Theorem 4.10 A necessary and sufficient condition that the sequence { Ln(G)} have a limit fraph is that G contain one or more components which are either simple circuits or star graphs of the type K1,3 while any other components of G be arcs. Proof. From Theorem 4.7 the only possible limit graphs are graphs whose components are simple circuits. It follows by the theorem of Whitney that with the exception of triangles, the only graph whose line-graph is a circuit is an isomorphic circuit. In the case of a triangle, it is the line-graph of both a triangle and the star graph K1,3° In addition to Kl,3 and circuits, G may contain arcs as com- ponents, for by Corollary 4.8.1, after taking a finite number of line-graphs, we arrive at a graph containing no arcs. Q.E.D. 25 Corollary 4.10.1 Let G be a graph which contains at least one component different from a circuit, the star graph K1,3, or an arc. Then if m and p are any two nonnegative integers (m £ p), Lm(G) and Lp(G) are nonisomorphic. Just as we found it useful to decompose a graph into its connected components, we find it useful to decompose con- nected graphs into special types of pairwise edge disjoint connected subgraphs and to investigate the relationships of such subgraphs with these types of subgraphs in the line—graph. We now introduce the following definitions, many of which may be found in Ore [11]. Definition 4.4 An edge E of agxemfliG is called a circuit edge of G if E belongs to some circuit of G. Definition 4.5 An edge E = (a, b) of a graph G is a separating edge or oof_oogo of G if the removal of E from G results in a graph G1 in which a and b are not connected, i.e., if a and b are not connected in the graph G1 whose vertex set is that of G and which has all edges of G with the exception of E. It is then a routine matter to verify the assertation: Theorem. An edge E is a circuit edge of a graph G if and only if it is not a separating edge of G. Definition 4.6 A vertex v of a graph G = G(V) is called a separating vertex or cut point of G if the removal of v (and necessarily then all edges in G incident with v) results 26 in a graph having a greater number of components than that of G, i.e., if G(U), where U = V - {Iv} , has more compon- ents than G. If G is connected, the removal of a separating vertex results in a disconnected graph. For example, cir- cuits and complete graphs contain no separating vertices, while, on the other hand, every vertex of degree two in an arc is a separating vertex. Definition 4.7 For any edge E of a graph G, the set of edges consisting of E and all edges F of G such that E and F both belong to some circuit in G forms a connected subgraph of G called the block (also lobe graph, member, or minimal piooo) of G determined by E. We state without proof the following well known results. Theorem. Every edge of a graph G lies in one and only one block of G. Theorem. Every block of a graph G is a section graph of G, but not conversely. Theorem. Every block of a graph G is a maximal connected subgraph of G containing no separating vertices. Theorem. Every graph is the edge direct sum of its blocks. Definition 4.8 The number of blocks to which a vertex v belongs is called the connective index of v and is denoted by i(v). It follows from the definition that a vertex v of a graph G is a separating vertex of G if and only if i(v):>l. 2.7 Definition 4.9 A nontrivial graph containing a single block is called a nonseparable graph. We now resume our investigations of line-graphs. Theorem 4.11 If a is any vertex in the line—graph L(G) of the graph G, then either i(a) = l or i(a) = 2. Proof. By Krausz' theorem, any line-graph is charac- terized by the fact that it can be expressed as an edge direct sum of complete subgraphs in such a way that every vertex belongs to at most two of these complete subgraphs. Clearly, any complete subgraph must lie wholly in some block, so any vertex a in a line-graph is contained in at most two blocks; hence i(a) = l or i(a) = 2. Q.E.D. Theorem 4.12 A necessary and sufficient condition that a vertex e in the line-graph L(G) of a graph G be a separating vertex is that the corresponding edge E in G be a nonterminal separating edge of G. IEEEE} Without loss of generality we may assume G and therefore L(G) to be connected graphs. Let E be a nonterminal separating edge of G, and let e be the corresponding vertex in L(G). If G1 is the graph obtained from G by deleting E, then we see that L(Gl) is the graph obtained from L(G) by deleting e. Since E is nonterminal, neither of the two com- ponents of G1 can be isolated vertices; hence L(Gl) is a dis- connected graph implying that e is a separating vertex of L(G). If E were a terminal separating edge, Gl would consist Of two components, one of which would be an isolated vertex, 28 so L(Gl) would be connected. If E were a circuit edge, then G1 would be connected as would L(Gl). Q.E.D. Theorem 4.13 A necessary and sufficient condition that an edge E = (a, b) be a separating edge of the line-graph L(G) of the graph G is that the edges A and B in G, which corre- spond to the vertices a and b, respectively, be separating edges of G which meet in a vertex of degree two. Proof. Again, we may take G to be connected. Suppose A and B are two separating edges of G meeting in a vertex v of degree two. If the edge B is deleted from G, we obtain a disconnected graph consisting of two components; let G1 denote that component containing v. Similarly, if the edge A is removed from G, we obtain a disconnected graph, one component of which contains v; call this component 62‘ Since G1 and G2 are connected, nontrivial, and edge disjoint, L(Gl) and L(Go) are connected and disjoint subgraphs of L(G). It is now easy to see that L(Gl) + L(G2) is precisely the subgraph of L(G) obtained by deleting the edge E = (a,b) from L(G), where a and b are the vertices of L(G) which correspond to A and B, respectively; hence, E is a separating edge of L(G). Conversely, let E = (a, b) be a separating edge in L(G), and let A and B be edges in G which correspond to the vertices a and b, respectively. Since it is obvious that A and B are adjacent, let v be the vertex in G common to A and B. /9(v) = 2, for if another edge C were incident with v and 29 c were the corresponding vertex in L(G), the vertices a, b, and c would form the vertices of a triangle in L(G) contra- dicting the fact that E is a separating edge. If A or B were a circuit edge, then necessarily there would exist a circuit in G containing both A and B as adjacent edges in the circuit, but a circuit in a graph produces an isomorphic circuit in its line-graph; however, this resulting circuit in L(G) would contain E as a circuit edge, again leading to a contradiction. Q.E.D. We see then that the only way of producing a separating edge in a line-graph L(G) is to have two separating edges in G which meet in a vertex of degree two. By carrying the argu- ment one step further, we see that in order to have two separating edges in a line-graph L(G) meeting in a vertex of degree two, the graph G must contain an arc of three separat— ing edges, each adjacent pair meeting in a vertex of degree two. It is also seen that G must have this property in order that L2(G) contain a separating edge. Let us state some con— sequences of Theorem 4.13 in a more formal way. Corollary 4.13.1 The line-graph L(G) of the graph G has m pairwise disjoint arcs of lengths n1, n2, . . . , nm (ni 27 1) consisting only of separating edges if and only if G has m pairwise edge disjoint arcs of lengths nl + 1, n2 + l, ., nm + 1 consisting only of separating edges, where any two adjacent separating edges in an arc meet in a vertex of degree two. 30 Proof. By arguments analogous to those used in the proof of Theorem 4.13, one sees directly that if G has an arc of length ni + 1 consisting only of separating edges, each adjacent pair of which has a vertex of degree two in common, then this results in an arc of ni separating edges, and two such arcs in G which are edge disjoint produce two disjoint arcs in L(G). The converse follows, again, by repeated ap— plication of the methods set forth in the proof of Theorem 4.13. Q.E.D. Corollary 4.13.2 If G is a graph containing k separating edges, k 27 1, then L(G) has fewer than k separating edges. .Proof. An arc of m separating edges, m 2: 2, in G, each adjacent pair having a vertex of degree two in common, produces an arc of m - l separating edges in L(G), and such an arc in L(G) can be obtained in no other way; hence, the number of separating edges decreases as we pass from G to L(G). Q.E.D. Corollary 4.13.3 A necessary and sufficient condition that the graph Lm(G) contain a separating edge is that G contain an arc of m + l separating edges, each adjacent pair of which has a vertex of degree two in common. Corollary 4.13.4 Let the separating edges of Lm(G) be denoted by El’ E2, . . . , Ek’ and assume that no two of these edges are adjacent. Then in G, there are k edge dis- joint arcs of length m + 1, each arc consisting only of 31 separating edges, and each pair of adjacent separating edges in any such arc has a vertex of degree two in common. We conclude this section witheatheorem which will be greatly strengthened in Section 7. Theorem 4.14 For any connected graph G which is not an arc, there exists a nonnegative integer N such that for all p 2: N, Lp(G) is a nonseparable graph, where the smallest value of N is (i) N = O if G is nonseparable, (ii) N = 1 if G contains separating vertices but no separating edges, and (iii) N = m + 1 if G contains separating edges, and m is the length of the longest arc in G consisting entirely of separat- ing edges, each adjacent pair of edges in the arc having a vertex of degree two in common. Proof. (i) follows as a direct result of Theorem 4.12, (ii) from Theorem 4.13, and (iii) follows from Theorem 4.13 and Corollary 4.13.3. Q.E.D. SECTION 5 THE CONNECTIVITY OF LINE-GRAPHS In Section 4 it was shown that if G is a graph with- out isolated vertices, then the line—graph L(G) is connected if and only if G is connected. This and other results in the preceding section imply that if G is a connected graph which is not an arc, then ‘(IP(G)} is an infinite sequence of connected graphs. In this section the twin tOpics of edge connectivity and (vertex) connectivity are considered. We begin by giving a definition due to Ore [11]. Definition 5.1 A nontrivial graph G = G (V) is m-edge connected if there exists no nonempty proper subset A of V such that the total number of edges joining a vertex of A to a vertex of A'= V - A is less than m. According to this definition, every nontrivial graph is O-edge connected. Definition 5.2 The largest value of m for which a graph G is m-edge connected is called the edge connectivity of G and is denoted by k0 = kO (G). Theorems stated by Ore dealing with edge connectivity include: 32 33 Theorem. A nontrivial graph is connected if and only if it has edge connectivity kO E: 1. Theorem. For any graph G = G(V) with edge connectivity k0, kO f3 min/9(v). velJ Theorem. A connected graph G has edge connectivity k0 = 1 if and only if G has a separating edge. The next two theorems will show that the concept of edge connectivity can be approached from a different direc- tion if we limit our discussion to connected graphs. Theorem_5.l A nontrivial graph G = G(V) is m-edge connected, m 24, if and only if the removal of any k edges, OS.k<1n, from G results in a connected graph. Proof. Let G be a graph which is m-edge connected, where H1211” Gris therefore connected. Assume, to the contrary, that there is some set of k edges, O-< ki< m, which, when deleted from G, disconnects it. If G1 is the graph ob- tained from G by removing these k edges, then it follows that G1 can be expressed as a direct sum: H1 + H2. If the vertex set of H1 is A and that of H2 is A = v - A, then the number of edges in G joining a vertex of A to a vertex of A is at most k, but k‘% (mr - r) = '% r(m-l):> % m (m - l) = (3), but this is impossible since the maximum number of edges in the section graph G(A) is (g). Likewise, a contradiction is reached if A contained only vertices adjacent to vertices of A. Suppose, then, that both A and A contain some vertices adjacent only to vertices in their respective subsets. Then A and A must both contain at least r + 1 vertices; G would have 2r + 2 vertices; however, 2r + 2 >-2r + l Ztn, which is a contra- diction. Q.E.D. We next investigate the relationship between the edge connectivity of a graph and that of its line-graph. Theorem 5.5 If a graph G = G(V) is m—edge connected, then its line-graph L(G) is (2m - 2) - edge connected. Proof. The result is trivial if m = 0. If G is l-edge connected, then G is connected, as is L(G), so L(G) is in fact l-edge connected. Suppose, then, that G is m-edge connected, where m 2:2. We shall show that L(G) is (2m -2) - edge connected. Let the vertex set of L(G) be denoted by W. It sufficies to show that if W1 is any nonempty proper subset of W, then these are at least 2m - 2 edges of L(G) joining vertices of W1 to vertices of W2 = W - W1. 37 Since G is certainly connected, L(G) is also connected. Thus, there must be at least one edge of L(G) joining a vertex of W1 to a vertex of W2; let this edge be E = (a,b), where a 6 W1 and b 6 W2. Also, let A and B denote those edges in G which correspond to a and b, respectively. Since a and b are adjacent in L(G), A and B are adjacent in G; so let A = (ul, u) and B = (v1, u). From a previously mentioned theorem, ,0 (u) _>_ m because kO 2 m, where kO denotes the edge connectivity of G. Hence, there are at least m edges in G incident with u. Consider the star subgraph S of G made up of A, B, and any other m-2 edges which are incident with u. L(S) is a complete subgraph C of L(G), where the vertex set U of C consists of m vertices of W. Now, a e U and b e U; so the vertex decomposition W = W1 L) We induces the vertex decomposition U = U1 L) U2, where U1 CI W1 and U2 (1 W2, and where both U1 and U are nonempty proper sub- 2 sets of U. Let the vertices of U1 be denoted by a = a1, a2, . . . , ak and the vertices of U2 be denoted by b = bl, b2, . . . , bm—k' Also, let the corresponding edges in G (the edges of S) be denoted by Al, A2, . . . , Ak and B1, B2, . . . , Bm-k' There is no loss of generality in assuming k:S;m-k. Since C is complete, all edges (ai, b3), i = 1, 2, . . ., k ; j = 1, 2, . . . , m-k are present; hence, there are at least k(m-k) edges joining wl with w2. Now there are at least m pairwise edge disjoint arcs in G joining ul to v1, say: 38 Pl : E11, E12, . . . , Blnl Pm : Em], Emg, . . . , anm. If the edge A appears in such an arc, it can only appear in one, and if it does, then it must be some E11. Similarly, B can only appear once and only then as some Ejnj‘ Hence, except for the one possible Ei which may be I A itself, all edges Ei are adjacent to A. Similarly, all 1 edges Eon are adjacent to B, with one possible exception. J J Clearly, none of the edges E11 can be any of the edges Bl’ B2, . . . , Bm_k. All this shows that in L(G) there are at least m arcs joining a to b which are disjoint except at the vertices a and b. If we eliminate these arcs among Pl’ P2, . . . , Pm which contain any of the edges Al, A2, , Ak’ there still remain at least m-k arcs. We have already seen that the line-graph of an arc is an arc (of length one less than the original). Hence, corresponding to the m-k (or more) arcs just mentioned are m-k (or more) arcs in L(G), none of which contain any of the vertices a1, a2, . . . , ak. Also, a1 is adjacent to the initial vertex of each of these arcs; however, no initial vertex is one of the vertices b1, b2, . . . , bm-k' Moreover, the terminal vertex of each of the m-k (or more) arcs in L(G) is either bl or is adjacent to b1. Clearly, each such arc must contain at least one edge joining a vertex of W1 to a vertex 39 of W2, and none of these edges can coincide. Also such edges cannot possibly be of the fomr (a1, b3), for this situation has been eliminated. Thus, there must be at least m-k edges joining a vertex of Wl to a vertex of W2 in addition to theLd_m—k) edges (ai’lbj) giving k(m-k) + (m-k) = (k + l) (m-k) edges in all joining a vertex of W1 to a vertex of W2. However, for k = l, 2, . . .,[%], (k + l) (m-k) assumes its minimum value when k = 1. There- fore, at least 2(m-l) = 2m-2 edges join a vertex of Wl to a vertex of W2, and so L(G) is (2m-2) - edge connected. Q.E.D. Corollary 5.5.1 Let G be a graph having edge connectivity k0, andlet kl denote the edge connectivity of its line-graph L(G). Then k1 E: 2kO - 2. Proof. If G has edge connectivity k0, then G is k0 - edge connected, and byTheorem 5.5, L(G) is (2kO -2) - edge connected. Hence, k1 Z 2kO - 2. Q.E.D. Corollary 5.5.2 If G is regular of degree r, r 222, and k0 = r, and kn denotes the edge connectivity of Ln(G), then kn = 2n(r-2) + 2. In particular, if G is a regular graph of degree r and order n, where r E: nél, then kn = 2n(r-2) + 2. Proof. If the graph G, regular of degree r, has edge connectivity k0 = r, then Theorem 5.5 implies that L(G) has edge connectivity kl 2:2r - 2; however, L(G) is regular of degree 2r - 2 and so klfi 2r - 2. Therefore, kl = 2r - 2. 40 If G is a regular graph of degree r and order n, where Farl'l , then Theorem 5.4 shows that k0 = r and kl = 2r -2 as before. The last statement follows by induction. Q.E.D. Analogous to the concept of edge connectivity is that of vertex connectivity. The definition we give is a slight variation of that given by Ore. Definition 5.3 Let G = G(V) be a nontrivial graph and let A be a nonempty proper subset of V. A vertex a of A is called an interior vertex of G(A) if a is adjacent only to vertices of A. A vertex of A adjacent to vertices both in A and A = V - A is called a vertex of attachment of G(A). Definition 5.4 A nontrivial graph G = G(V) is m-vertex connected, or simply m—connected, if either (1) G is a complete graph of order n >tm, or (2) there exists no non- empty proper subset A of V with G(A) having at least one interior vertex such that the total number of vertices of attachment is less than m. It is not difficult to show that a necessary and suf- ficient condition that a nontrivial graph G = G(V) contain a nonempty prOper subset A of V such that the section graph G(A) have at least one interior vertex is that G be not com- plete. For this reason an alternative definition of "m- connected” was given for complete graphs. A graph which is 2-connected is often called doubly gonnected or oiconnected. A 3-connected graph is also 4l referred to as a triply connected graph. Definition 5.5 The largest value of m for which a graph G is m-connected is called the vertex connectivity or simply the connectivity of G and is denoted by (B = 1g(G). We next state without proof the following simple con- sequences of the definition of connectivity of a graph (see Ore [11]). Theorem. A nontrivial graph is connected if and only if it has connectivity .10 221. Theorem. A connected graph G has connectivityflO = 1 if and only if G consists of a single edge or G has a separating vertex. Corollary. A necessary and sufficient condition that a con- nected graph G consisting of more than an edge be nonseparable is that G be biconnected. Theorem. If .20 is the connectivity of a graph G = G(V), then [03min [0(v). veaV Another consequence of the definition of connectivity is presented next. Theoremy5.6 Let G be a graph of order n having connectivity “[0. If G is complete, then ‘[o = n-l, while if G is not complete, then Io gn-2. 'Proof. If G is complete, then the largest value of m for which n > m is clearly n—1, and so £0 = n-l. If G is not complete, then ‘IO‘S n-2 by the preceding theorem. Q.E.D. 42 We present an alternative approach to m-connectedness and connectivity, analogous to that given for m-edge con- nectedness and edge connectivity. Theorem 5.7 A graph G = G(V) is m-connected, m 2:1, if and only if the removal of any k vertices, O S k-1, having precisely +1 one vertex in common. With the aid of Theorem 5.4, it is easily seen that H has edge connectivity m and connectivity one (H is therefore m-edge connected but not m-connected). For the case where m = 5, see Figure 5.1. Figure 5.1 46 We do have the following result, however, in the case of line-graphs. Theorem 5.9 If G is an m-edge connected graph, then the line-graph L(G) is m—connected. .EEQQQ- Let a and b be two arbitrary d stinct vertices of the line-graph L(G) of the m-edge connected graph G. Let A = (u, ul) and B = (v, V1) be the edges of G which corre- spond to the vertices a and b, respectively. Consider the vertices u and v (or u and v1, should u = v). Since G is m-edge connected, there exist m arcs Pi’ i = l, 2, . . . , m, every two of which are edge disjoint, which join u to v. At most one Pi contains A; however, those arcs which fail to contain A have their first edge adjacent to A. Similarly, at most one such arc contains B, but any arc not containing B has its last edge adjacent to B. Corresponding to the arcs Pi in G are then m arcs Qi’ i = l, 2, . . . , m, in L(G), which are pairwise disjoint. a. lies in at most one Q1, as does b, but any arc not containing a has its first vertex adjacent to a. Similarly, any arc Qi not containing b has its last vertex adjacent to b. This implies, then, that there exist m arcs in L(G) joining a and b, which are dis- joint except for a and b. Hence, L(G) is m-connected. Q.E.D. Corollary 5.9.1 If G has edge connectivity kO and L(G) has connectivity .21, then kO _‘_<_ [1. 47 Corollary 5.9.2 If G is m-connected, then L(G) is m- connected. Proof. If G is m-connected, then G is also m-edge connected; thus, by Theorem 5.9, L(G) is m-connected. Q.E.D. One might expect a result for m-connectedness analogous to that obtained for m-edge connectedness (see Theorem 5.5); however, the following example shows that Corollary 5.9.2 cannot be improved. Let the graph J con— sist of two disjoint graphs of the type K m.2:l, the m+l’ vertices of which are denoted by ui and Vi’ respectively, i = O, l, . . . , m, where, in addition, the m edges E1 = (ui, vi), i = l, 2, . . ., m are inserted. J has con- nectivity m (and so is m - connected); however, L(J) also has connectivity m (and so is not (m+l)—connected) since the deletion of the vertices ei (where ei corresponds to E1) from L(J) disconnects it. Figure 5.2 shows the case where m = 3. It thus follows that the results obtained in Corol- laries 5.5.1 and 5.9.1 are the best possible, and this constitutes a solution to the problem proposed by Ore of determining the relations between the connectivities and the edge connectivities for a graph and its line-graph (see [11], page 81, problem 2). We have the following extension. Theorem 5.10 If G is m-connected, then L2(G) is (2m-2) - connected. 48 1» A fl.» m.m enemas TVQTV m> 49 Proof. Since G is m-connected, it is m-edge connected. By Theorem 5.5, L(G) is (2m -2) - edge connected. From Theorem 5.9, it then follows that L2(G) is (2m - 2) - connected. Q.E.D. Corollary 5.10.1 If G is m-connected, then Lk(G) is k-l k [2 (m-2) + 2] - connected and is [2 (m-2) + 2] - edge connected for k 2 1. Proof. This follows by induction on k. Q.E.D. We conclude this section with two corollaries to Corollary 5.10.1. Corollary 5o10.2 If G is a graph whose edge and vertex connectedness exceed two, then the edge connectedness and vertex connectedness of Lk(G) are unbounded as k becomes infinite. Corollary 5.10.: Let G be a graph with k0 2: £0 5: 2. Then lim k0 [Ln(G)] = lim ,[O [Ln(G)] = oo . n—+oo f1——ewo SECTION 6 LINE-GRAPHS AND EULER PATHS In this section we prove that the line-graph of a graph which contains an Euler path also contains an Euler path. Necessary and sufficient conditions are derived in order that some repeated line-graph contain an Euler path. Definition 6.1 A graph G without isolated vertices is said to contain an Euler path if there exists a cyclic path in G containing every edge of G, and every such cyclic path is called an Euler path. A graph containing an Euler path is called an Euler graph. Definitions of a few other terms will be useful here. Definition 6.2 A vertex is called even or odd according to whether its degree is an even or odd integer. An edge is called oyoo_or ooo depending on whether its degree is even or odd. Euler graphs have been of interest to graph theorists, both professionals and amateurs alike; however, the question of whether a given graph is an Euler graph was answered by Euler in the following way. Theorem (Euler). A necessary and sufficient condition that a nontrivial graph G be an Euler graph is that G be 50 51 connected and every vertex of G be even. Lemma 6.1 Every edge of an Euler graph is even. Proof. If E = (a, b) is an edge of an Euler graph, then )0(E) = F(a) + F(b) - 2 is even since [0(a) and b are bOth even by EUISP'S theorem. 3,.EOD. Theorem 6.2. The line-graph of an Euler graph is an Euler graph. _Proof. Let G be an Euler graph and L(G) its line- graph. The degree of a vertex in L(G) has the same value as the degree of its corresponding edge in G by Lemma 4.2, which is even by Lemma 6.1. Since G is connected, L(G) is connected; hence, L(G) is an Euler graph by Euler's theorem. Q.E.D. Corollary 6.2.1 If G is an Euler graph, then {L“(G)} is an infinite sequence of Euler graphs. Corollary_6.2.2 If G is an Euler graph which is not a circuit, then Lm(G) and Ln(G), m £ n, are nonisomorphic Euler graphs. Proof. This is simply a combination of Corollaries 4.10.1 and 6.2.1. Q.E.D. We now determine conditions for a graph G in order that there exists a nonnegative integer k such that Lk(G) contains an Euler path. The only possibilities are given in the following theorem. 52 Theorem 6.3 Let G be a connected graph which is not an arc. Then exactly one of the following four situations must occur: ( ) G is an Euler graph, (ii) L(G) is an Euler graph but G is not, ) L2(G) is an Euler graph but L(G) is not, ) there exists no n 2:0 such that Ln(G) is an Euler graph, where (i) occurs if and only if every vertex of G is even, (ii) occurs if and only if every vertex of G is odd, (iii) occurs if and only if every edge of G is odd, and (iv) occurs otherwise. Proof. Since G is connected and not an arc, the fact that G is an Euler graph if and only if every vertex of G is even is just a restatement of Euler's theorem. If every vertex of G is odd, then G cannot be an Euler graph (again, by Euler's theorem), but every edge of G must be even, so every vertex of L(G) is even; therefore, L(G) is an Euler graph. Conversely, suppose L(G) is an Euler graph but G is not. It follows, then, that every vertex of L(G), and hence every edge of G, is even; thus, if E = (a, b) is an edge in G, the number /0(a) + /9(b) - 2 is even. This implies, of course, that /0(a) + f(b) is even, or that the two vertices incident with any edge of G are either both even or both odd. Because G is not an Euler graph, though, there. must be at least one edge in G incident with two odd vertices; 53 call the edge F = (u, v). We must have all vertices of G odd then, for if w is any vertex of G either w = v and w is odd, or w £ v and there is an arc P : (v, v1, v2, . . . , Vk-l’ w) between v and w (since G is connected). However, since v is odd, vl must also be odd (recalling that two vertices incident with an edge must be of the same parity), but (v1, v2) is an edge implying that v2 is odd, etc. Finally, we arrive at w, which must be odd. If every edge of G is odd, then every vertex of L(G) is odd, and L(G) is not an Euler graph. If, however, every vertex of L(G) is odd, then every edge of L(G) is even, so every vertex of L2(G) is even, and L2(G) is an Euler graph. Conversely, let G be a graph such that L2(G) is an Euler graph but L(G) is not an Euler graph. Whereas L2(G) is an Euler graph, the vertices of L2(G) are even, and the edges of L(G) are even. Seeing that L(G) is not an Euler graph, we can argue as in the preceding paragraph to conclude that every vertex of L(G) is necessarily odd. From this it follows that every edge of G is odd. It remains to show that if (i), (ii), or (iii) is not satisfied by a graph G, then there is no n 2:0 such that Ln(G) is an Euler graph. Let us assume, then, that G, L(G), and L2(G) are not Euler graphs, but that there does exist an n E: 3 such that Ln(G) is an Euler graph. Let m be the smallest value of n for which Ln(G) is an Euler graph. Then ifCD£ELc_ 2, Ln(G) is an Euler graph. 55 Corollary 6.3.3 Let G be a graph, connected or not. A nec- essary and sufficient condition that there exists an n such that Ln(G) is an Euler graph is that G contain one component which is not an arc and of which every edge has the same parity while all other components are arcs. SECTION 7 SEQUENTIAL GRAPHS; LINE-GRAPHS AND HAMILTON CIRCUITS In this section it is shown that if a graph contains a Hamilton circuit, then its line-graph also contains a Hamilton circuit. In addition, necessary and sufficient conditions are given for a graph in order that its line- graph contain a Hamilton circuit. The main result of this section is that for nearly all connected graphs, some re- peated line-graph must contain a Hamilton circuit. Definition 7.1 A graph G is said to contain a Hamilton circuit if there exists a circuit in G passing through every vertex of G, and every such circuit is called a Hamilton circuit. A graph containing a Hamilton circuit is called a Hamilton grapp. It follows directly from the definition that every Hamilton graph is connected, in fact, biconnected. In spite of the strong similarities in the definitions of Euler graphs and Hamilton graphs, the differences in the two are so great that no useful characterization of Hamilton graphs has yet been found. The independence of these two definitions is illustrated in Figures 7.1 through 7.4, where all graphs are of order eight and have twelve edges. 56 V A Euler and Hamilton Fig. 7.1 V A Hamilton but not Euler Fig. 7.3 57 Euler but not Hamilton Fig. 7.2 Neither Euler nor Hamilton Fig. 7.4 58 If G is a connected graph which is regular of degree two, then G is a Hamilton graph. This fact is trivial since 0 is then a circuit; however, on the other extreme, if the degrees of the vertices are large enough in comparison with the order of the graph, then G must also contain a Hamilton circuit. A well-known theorem of this type is the following. Theorem of Dirac If G = G(V) is a graph of order n and /0 (v) E: n/2 for all v e V, then G is a Hamilton graph. This result was slightly strengthened by Ore [11]. Theorem of Ore If G = G(V) is a graph of order n and ’01 + P2 2 n, where ’01 and [02 denote the two smallest degrees in G, then G is a Hamilton graph. We find the following definition of considerable use to us in this section. Definition 7.2 A graph G having m edges, where m 52 3, is called a sequential graph if the edges of G can be ordered in SUCh a way, say E0, E1, E2, 0 o o , Em_l, Em = E that O) the edges E1 and E. 1+1, 1 = O, l, . . . , m-l, are adjacent. Although a sequential graph has its edges arranged in a certain cyclic order, this does not imply the existence of circuits, for the star graphs K , n 5:3, are sequential l,n graphs. Two important classes of connected graphs, the Euler graphs and the Hamilton graphs, are sequential graphs. We verify these facts below. 59 Theorem 7.1 An Euler graph is a sequential graph. Proof. If G is an Euler graph, then G has a cyclic path P containing all the edges of G, say P : E0, E1, E2, , Em-l’ Em = E0, where E1 and Ei+l are adjacent for all i = 0, l, . . ., m-l. Hence, G is sequential. Q.E.D. Theorem 7.2 A Hamilton graph is a sequential graph. Proof. Let C = (a0, a1, a2, . . . an_l, an = a0) be a Hamilton circuit of the graph G. It is clear that every edge of G joins two vertices lying on C. In order to show G is sequential, we must exhibit an ordering of the edges of G which satisfies the property stated in Definition 7.2. Begin the ordering of the edges of G with all edges incident with aO not lying on C (there may be none). These may be taken in any order and are clearly adjacent to one another. We follow these with the edge (a0, al) of C. The next edges in the sequence are the edges incident with al which are not in C (again, there may be none). Once again, they may be permuted in any way among themselves. This is followed by (a1, a2) and all edges incident with a2 which are not on C and which have not been previously considered. We continue in this way until we finally arrive at the edge (an_l, an) = (an_1, a0), which is adjacent to the first edge in the sequence. It is now a routine matter to check that every edge of G appears in the sequence once and only once and that every two consecutive edges in the sequence are adjacent, so G is a sequential graph. Q.E.D. 60 The chief reason for introducing sequential graphs is the following theorem. Theorem 7.3 A necessary and sufficient condition that the line-graph L(G) of a graph G be a Hamilton graph is that G be a sequential graph. Proof. Let G be a sequential graph having m edges. Then the edges can be ordered, say E0, E1’ E2, . . . , Em-1, Em = E0, such that consecutive edges in the sequence are adjacent. Let e0, e1, e2, . . . , em-l’ em = eO be the corresponding vertices in L(G). Since Bi and Ei+l are adjacent for i = O, l, . . . , m-l, (ei, ei+l) is an edge in L(G) for i = o, 1, . . . ,m—l, and so c = (e0, e1, e2, , em—l’ em = e0) is a circuit in L(G) which contains all vertices of L(G); hence, C is a Hamilton circuit of L(G), and L(G) is a Hamilton graph. . Conversely, suppose the line-graph L(G) of the graph G is a Hamilton graph. This means that there is a circuit C = (a0, a1, . . . , an—ls an = a0) in L(G) containing every vertex of L(G). Let A0, A1, . . ., An_l, An = A0 be the edges in G which correspond to the vertices a0, a1, . . . , an-l’ an = a0, respectively. Consider the edges of G in the order just given. Since (a1, ai+1) is an edge of L(G) for i = 0, l, . . . ,n-l, A1 and A1+1 are adjacent for i = 0, l, , n-1, and therefore G is a sequential graph. Q.E.D. 61 Theorem 7.4 If G is a Hamilton graph, then L(G) is a Hamilton graph. Proof. If G is a Hamilton graph, then G is also a sequential graph by Theorem 7.2. By Theorem 7.3, it then follows that L(G) is a Hamilton graph. Q.E.D. Corollary 7.4.1 If G is a Hamilton graph, then Lp(G) is a Hamilton graph for all p 2.0. Theorem 7.57 If G is a sequential graph, then L(G) is a sequential graph. Proof. By Theorem 7.3, if G is a sequential graph, then L(G) is a Hamilton graph, and by Theorem 7.2, L(G) is a sequential graph. Q.E.D. Theorem 7.6 If G is an Euler graph, then L(G) is an Euler graph which contains a Hamilton circuit. .Proof. By Theorem 6.2, if G is an Euler graph, then L(G) is an Euler graph. However, by Theorem 7.1, G is also a sequential graph, and so L(G) is a Hamilton graph. Q.E.D. As Theorem 7.4 indicates, if G is a graph having a Hamilton circuit, then L(G) has at least one Hamilton circuit. Although there are examples of Hamilton graphs (namely, circuits) whose line-graphs have exactly one Hamilton circuit, for the most part, the line-graphs of such graphs contain more than one Hamilton circuit. (Two Hamilton circuits are called different if there is at least one edge in one not in 62 the other and vice versa). We shall obtain next a lower bound for the number of Hamilton circuits in the line-graph L(G) of a Hamilton graph G. To do this, we shall make use of directed graphs. Theorem 7.7 Let G = G(V), where V = {Vo’ v1, . . . , Vn-l} , be a Hamilton graph of order n, and let C be a fixed Hamilton circuit of G. Assume G has d diagnoals so that G has m = n + d edges. Let S denote the set of the 2d directions for G obtained by directing all edges of C in one of the two possible cyclic manners and directing the diagonals in an arbitrary manner. For each s e S let /%s (v) denote the number of outgoing edges at v when the edges of G are directed according to s. It then follows that the number of Hamilton circuits in L(G), denoted by HG (L(G)), satisfies the following inequality: n-l Hc (L(G)) E: Z {Tr [( f’oSm) — 1) I 1] s e S j=o -1 2 2d { min {[17 [(IDOS(vj)-l)1]} s e S j=o 3: 21. _Proof. First, we notice that for any 8 5 S and every vertex v in G, /%S(vj 2:14 since there is a circuit edge of C which is incident with v and directed away from v. A Hamilton circuit in L(G) is produced from each sequence of all the edges of G which can be constructed so that consecu- tive edges in the sequence are adjacent as well as the first 63 and last edges in the sequence being adjacent. Two sequences will be called different if there exist two edges which are consecutive (or first and last) in one sequence but are not consecutive in the other sequence. Two such ”different” se- quences in G correspond to two different Hamilton circuits in L(G). We now derive the first inequality given in the conclusion of the theorem, the others following directly from the first. Let C = (v v1, . . . , v = v0), and let 0’ n s be a fixed direction in the set S. The ,F28 (VJ) - l outgoing edges at VJ not lying on C may be permuted in ( fzs (v3) — l) 1 ways, so as we proceed around C in a fashion similar to that in the proof of Theorem 7.2--only this time considering only outgoing edges--we see that QF% [( fo (VJ) - l) 1] different sequences are obtained, eggh one satisfying the property required of sequential graphs. ince we may do this for each 8 ea S obtaining se- quences not previously encountered, we arrive at the first inequality. Q.E.D. Although the first inequality in the preceding theorem can easily be seen to be an equality in the case where a Hamilton graph G contains only a single Hamilton circuit, if it should occur that G contains two or more Hamilton circuits, the procedure employed in Theorem 7.7 may be used for each Hamilton circuit, thereby obtaining a strict inequality. Since duplication of previous sequences may arise when using different Hamilton circuits of G, the lower bound in the first 64 inequality of Theorem 7.7 cannot be replaced by summing this expression for the bound over all Hamilton circuits in G. It is a straightforward problem to show that if C is a Hamilton circuit in a graph G such that G contains at least one diagonal, then the number of diagonals in the graphs in the sequence { Ln(G)} of Hamilton graphs forms a strictly increasing sequence. Combining this property with the last inequality involved in the conclusion of Theorem 7.7, we are led directly to a corollary. Corollary 7.7.1 Let G be a Hamilton graph containing at least one diagonal. Then lim [ HC (Ln(G) ] =oo Before presenting the main theorem of this section, we state two lemmas. Lemma 7.8 If G is a graph containing a circuit C such that every edge of G is incident with at least one vertex on C, then L(G) is a Hamilton graph. _Proof. We show that the graph G having the properties stated in the lemma is sequential. To produce the desired ordering of the edges of G we use the same procedure as that employed in the proof of Theorem 7.2 except that after con- sidering the diagonals at a given vertex of C, we insert in the sequence all edges which are incident with that vertex but with no other vertex of C and follow these edges, as before, by the appropriate circuit edge of C and continue in 65 this way. The sequence of edges of G so produced is seen to have the desired properties, and G is sequential. The result now follows by Theorem 7.3. Q.E.D. Lemma 7.9 Let G be a graph consisting of the section graph [C] of a circuit C and m arcs P1, P2, . . . , P where each m’ arc has precisely one endpoint in common with C while for i £ j, Pi and P3 are disjoint except possibly having an endpoint in common if it is also common to C. If M is the maximum of the lengths of the arcs Pi, then Lp(G) is a Hamilton graph for all pZM. Proof. It is easily observed that L(G) has the same properties as G except that the lengths of the m resulting arcs Will have decreased by one so that the maximum length among the remaining arcs is M-1 and that LM(G) consists of a section graph of a circuit (hence is a Hamilton graph), and LP(G) is a Hamilton graph for all p _>_M by Corollary 7.4.1. Q.E.D. Theoremp7.10 If G is a connected graph of order n which is not an arc (then necessarily n52 3), then Lp(G) is a Hamilton graph for every p E: n—3. Proof. We proceed by induction on n. Later develop- ments in the proof make it necessary for us to investigate the graphs having order 3, 4, or 5. We do this now. The only connected graph of order 3 which is not an arc is the triangle, and this is already a Hamilton graph, so the result follows (with the aid of Corollary 7.4.1). For n = 4, there 66 are only two connected graphs which are not arcs and which are not already Hamilton graphs. These graphs are shown in Figure 7.5. G41: GA2‘ Figure 7.5 We readily see that L(G4l) and L(G42) are both Hamilton graphs, and the result is established for n = 4. There are twelve connected graphs of order 5 which are not arcs and which do not already contain Hamilton Circuits. These are presented in Figure 7.6. It is then a routine matter to verify that L2(G51) and L2(G52) contain Hamilton circuits and that L(GSi), i = 3, A, . . . , 12, contain Hamilton circuits. This establishes the theorem for the case when n = 5. Let us assume then that for all connected graphs G' which are not arcs and which have order s, where s‘< n and n 26, Lp(G') is a Hamilton graph for every p as - 3. Let G be a connected graph of order n which is other than an arc. G5, ll: GSA: 67 Figure 7.6 G56: G5,10: G5.12= A vi 68 We shall show that Ln‘3(G) is a Hamilton graph which, with the use of Corollary 7.4.1, will provide a proof of the theorem. The theorem is clearly true if G is a circuit, so, without any loss in generality, we may assume that G is not a circuit and that G contains at least one vertex v of degree three or more. Let H denote the subgraph of G con- sisting of v and those edges of G which are incident with v. We denote the vertex set of G by V and let U = V - '{v] . Denote the section graph G(U) of G by Q. We then can write G = H + Q, where H and Q are edge disjoint. (If G is a star graph, then Q consists only of isolated vertices.) Let the connected components of Q be denoted by G1, G2, . . . , Gk: where Gi, i = l, 2, . . . , k, is of order ni. Then k E n1 = I’l’l. i=1 If G1 is an arc, then Lni(Gi) is an empty set while if G1 is other than an arc, then Lp(Gi), for p 2: n1 - 3, contains a Hamilton circuit by the inductive hypothesis. The line-graph H1 = L(H) of H is a complete subgraph of L(G) which, considered as a graph by itself, contains a Hamilton circuit. Let Jl denote the subgraph of L(G) con- sisting of H1 and all the ”cross edges” from Hl to the L(Gi), i = l, 2, . . . , k. Therefore, L(G) can be expressed as the edge direct sum J1 + L(Gl) + L(G2) + . . . + L(Gk), where for 1 £ j, L(Gi) and L(Gj) are disjoint. Observe that any arc joining a vertex of L(Gi) to a vertex of L(GJ) must 69 necessarily contain at leastinwpedges of J1. Let H2 = L(Jl) and let J2 denote the subgraph of L2(G) consisting of H2 and all the cross edges from H2 to the L2(Gi), i = l, 2, . . . , k. Then L2(G) = J2 + L2(Gl) + L2(G2) + . . . + L2(Gk). since J1 satisfies the hypotheses of Lemma 7.8, H2 contains a Hamilton circuit. In general, let Jm denote the subgraph of Lm( G) consisting of Hm plus all the cross edges joining Hm to the Lm(Gi), and let Hm+l = L(Jm). Lm(G) can then be expressed as the edge direct sum Jm + Lm(Gl) + Lm(G2) + . + Lm(Gk). By Lemma 7.8, it also follows that Hm (considered as a graph itself) contains a Hamilton circuit. We now consider two cases. Case 1. Suppose the components G1, G2, . . . , Gk of Q are all arcs (which includes the possibility of isolated vertices). If the number of components k is at least three, then no hi can exceed n - 3, and Ln-3(G) = Hn-3’ which con- tains a Hamilton circuit. If k = 2 and the orders of G1 and G2 do not exceed n - 3, then, as before, Ln_3(G) = Hn—3' If, on the other hand, k = 2, and one component, say G1, has order n - 2 while G2 is an isolated vertex, then H and G1 have at least two vertices in common, and G consists of a section graph of a circuit and j pairwise disjoint arcs, l gzj g_ 3, each having precisely one endpoint in common with the circuit. Since none of these arcs has length ex- ceeding n - 4, it follows by Lemma 7.9 that Ln-4(G) (and so also Ln-3(G)) contains a Hamilton circuit. 70 If k = 1, then Q is an arc Gl having at least three vertices in common with H so that G consists of a section graph of a circuit and j pairwise disjoint arcs, 0 ff j is 2, each arc having exactly one endpoint in common with the circuit. If j = O, G contains a Hamilton circuit while if j >‘0: no arc extending from the aforementioned circuit can have length exceeding n - 4, and by Lemma 7.9, L _ (G) con- tains a Hamilton circuit as does Ln_3(G). Case 2. Assume the first ,2 components, 1 g [5 k, of 91: G2, . . . , Gk are not arcs. Clearly, each of the components G1, G2, . . . , G1 must have order at least three. I If ,€<:k, then G£+l, G£+2, . . . , Gk are arcs, each having an order not exceeding n - 4, so Ln'4(G) = Jn_4 + Ln_4(Gl) + . . . + Ln’4(G2). Since each G1, i = 1, 2, . . . , E , has order not exceeding n - l, the subgraphs Ln-4(Gi), considered as graphs, each contains a Hamilton circuit by the inductive hypothesis. There is clearly at least one edge from Hn_5 to each of the subgraphs Ln-5(Gl), . . . , IP—EKGoQ). We next show that there is at least one cross edge from Hn-5 adjacent to at least two edges of Ln_5(Gi) for each i = l, 2, . . . , fl. 117,Z==l, then G1 is the only component of Q which is not an arc. If k > 1, 01 has order at most n - 2, so Ln-5(Gl) contains a Hamilton circuit and clearly such a cross edge exists. If k = 1, then Q = G1 and all edges of H are incident with vertices of 01. Since a cross edge to a sub- graph which is not an arc results in one or more new cross edges in the following line-graph, there are at least three 71 cross edges from Hn-5 to Ln’5(Gl). If no such cross edge were adjacent to at least two edges of Ln—5(Gl), then clearly each of the three or more cross edges is adjacent to precisely one edge of Ln-5(Gl). This implies that Ln'5(Gl) contains three or more separating edges, which implies, by Corollary 4.13.3, that G1 contains three arcs, each having n - 4 separating edges, meaning that G1 contains at least 3(n-4) + 1 vertices, but for n E: 6, 3(n-4) +1 >»n-1 contradicting the order of G1. Suppose [:>l, i.e., suppose Q contains two or more components which are not arcs. Therefore, G1 and G2 are not arcs and have orders at most n - 4. If there is a cross edge from Hn-5 adjacent to only one edge of Ln—5(Gl), say, then Ln-5(Gl) contains a separating edge, and by Corollary 4.13.3, G1 must contain an arc of n — 4 separating edges which contradicts the order of G1. We can thus conclude that there exists a cross edge from Hn-5 to Ln-5(Gi) adjacent to two edged of Ln_5(Gi) for each i = l, 2, . . ., E . This implies that for each i = l, 2, . . . , .1 , there is a vertex ui in Hn-4 adjacent to both A endpoints of an edge in Ln— (G i)' We now claim that Ln-u(G) is a sequential graph so that Ln'3(G) contains a Hamilton circuit. To show this we order the edges of Ln‘u(G) as follows. Since Hn-4 itself contains a Hamilton circuit C, we start at some vertex v of C. If the vertex v is not one of the ui, we begin with the 72 diagonals of C at v, the edges incident with v but with no other vertex on C, and then take an edge of C incident with v leading us to a new vertex of C. We continue with this method, proceeding around C, until one of the vertices ui is encountered. At such a vertex u~, we begin with the 1 diagonals of C at ui not previously taken (as before), all the edges incident with ui but incident with no other vertex on C except those two edges previously singled out, say Eil and Bi which lead to the endpoints of an edge F1 2, in Ln'4(Gi). Next, take Bil, say, leading us into Ln‘4(Gi), which, by the inductive hypothesis, contains a Hamilton cir- cuit Ci. If Fi is on Ci, we proceed around Ci in the customary way (i.e., taking diagonals and a circuit edge of Ci in that order), taking F1 last and then taking E12 back to ui. If F1 is not on Ci: i.e., if Pi is a diagonal of C1, then as we proceed around Ci: leave out F1 until all other edges in Ln-4(Gi) have been taken, then take F1, and then E12 back to ui on C. We then continue around C following one of the two procedures outlined depending on whether the vertex encountered is or is not one of the ui. It is easily seen that the sequence has the properties necessary for Ln_4(G) to be a sequential graph. QOEODO The preceding theorem now permits us to make the following definition. Definition47.3 Let G be a connected graph which is not an arc. The Hamilton index of G, denoted by h(G), is the 73 smallest nonegative integer p such that Lp(G) contains a Hamilton circuit. We can now restate Theorem 7.10 in the following way: If G is a connected graph of order n which is not an arc, then h(G) exists and h(G) S n-3. To show that the bound given in Theorem 7.10 cannot be improved, we note that for every n 2:3, there are graphs whose Hamilton index is n - 3. The graphs G1 and G2 shown in Figure 7.7 have Hamilton indices n - 3. 0 ° 0 1D 0 a 5 N p- C) ID \/ 041‘ 0W 0 0 p 1" ,CS Figure 7.7 We conclude this section with a conjecture. Conjecture. Let G be a connected graph of order n, n 2:4, containing a vertex v with )0(v) = r, where 3 g r <_ n - 1. Then h(G) f} n - r. SECTION 8 TRIANGLE RELATIONS IN REPEATED LINE-GRAPHS OF REGULAR GRAPHS In this section we investigate some numerical results concerning the number of vertices and edges in repeated line-graphs of arbitrary regular graphs having degree r, where r > 2, as well as some related triangle relations in such graphs. We show that in spite of the ever-increasing maze of edges which appears in repeated line-graphs of such graphs G, the more probable it becomes as n approaches infinity that if three vertices are selected at random from Ln(G), no two of the three vertices will be adjacent. Let GO be an arbitrary regular graph of degree rO‘> 2 having nO vertices, mO edges, and T30 triangles. Let G1 = L(GO) and, in general, define Gi+l = L(Gi) = Li+1(GO) for each i = 0, l, 2, . . . . As we proved in Section 4, each G1 is regular. To fix the notation, let G1 be of order hi and regular of degree ri having mi edges and T31 triangles. For the graph Gi+l the following relations are a direct consequence of Theorems 4.1 and 4.4. (1) r1i+1 = mi ( ) r1+1 = 2 (3) m1+1 = “i(2l) 74 75 1+]. _ 1 Pi (11) T3 .. T3 +n1 (3 ). We introduce the even integers Qi+l’ i = O, l, 2, , by means of the following equation. 2 (5) 29i+1 = ni+1 ri+l We find it useful to repeat a result of Theorem 4.4 here which was derived using mathematical induction and (2). (6) r1 = 21(rO-2) + 2. Because of the fact that (7) 2m1+1 = ni+l r1+1 , it follows by (l) and (2) that (8) mi+l = (ri-l) mi , and by repeated application of (8), we find, using (6), that (9) mi+1 = mO TE. (rk-l) = mO 23; [2k( r -2 + l . Lemma 8'1 Qi+l = mi+1 ri+l = mi+l + mi+2 Proof. By (5) and (7), it follows that Qi+l = mi+lri+l‘ Rewriting, Qi+l = mi+1 + mi+l(ri+l-l) = mi+l + m1+2 by (8). Q.E.D. We define the quantity Ai, i = 0, l, 2, . . . , as follows. I 1 Lemma 8.2 Ai+l = Ai’ i.e., A1 is independent of 1. Proof. By (10) we have 1+1 (1) Ai+l = 6 T3 ‘ mi+2 i r1 _ (ii) = 6 T3 + 6n1 (3 ) - mi+2 mi+l + mi+l ) by (4) and by subtraction and addition of mi+l° By (10) again, it follows that 76 . I" (iii) A1+1 = Ai + 6ni (31) + mi+l - mi+2 P. It is now sufficient to show that (iv) has the value Ai. By (3) and (2), m1+1 = ni (g1) and 2 (ri—2) = 2(ri-l) - 2 = ri+1 - 2 so that (iv) can now be written as (v) A1 + mi+l (ri+l - 2) + m1+1 - mi+2 = A1 + m1+1 Iji+l ' (mi+1 + mi+2) = A1 by Lemma 8.1. Q.E.D. 1 Corollary 8.2.1 6T3 = mi+1 + AO In any graph the section graph determined by three vertices may consist of three edges (thereby resulting in a triangle) two edges, one edge, or no edges at all. Using the terminology originated by Nordhaus and Stewart [10], we say that a subgraph consisting of three vertices and the j edges, j = O, l, 2, 3, which they determine is a triangle of type fl. A triangle of type T3 is simply a triangle while a triangle of type TO is a subgraph consist- ing of three isolated vertices, i.e., an ”empty” triangle. We denote the number of triangles of type Tj in G1 by TJi. Since any three vertices in G1 determine a triangle T2, or T3, it follows that: of type To’ T1’ (11) T: + T11 + T21 + T31 _ ( i), or i i i i T T T T (31) ($1) (“1) ($1) 77 We state two relations given in [10], which may readily be derived from elementary considerations: (13) T21 + 3 T3i = Q1 - mi (14) 3T3l 2 T11 + 2Qi ‘ mi ni' Eliminating T l in (13) and (14), we obtain 3 (15) T11 + T21 = (“i-l) mi - Qi Lemma 8.3 2 T21 = mi+l - AO Proof. From (13), we have 2Qi-2m0-6Ti i 2 T2 1 3 = 2(mi + mi+l) ' 2mi ‘ (mi+1 + A0) = mi+l ' Ao by Lemma 8.1 and Corollary 8.2.1. Q.E.D. It is now possible to compute T11 and TO1 using Corollary 8.2.1 and equations (14) and (11); however, in order to consider limiting cases it is convenient to obtainex- plicit eXpressions for these values. Lemma 8.4 2Tli = A0 + 2mi-l mi - “mi ‘ 3mi+1 Proof. From (15) we can write 1 2T = 2(ni-l) mi - 2Qi - 2T2 From (1) and Lemma 8.1, it follows that i 2T1i = 2(mi_l-l) mi - 2(mi + mi+l) - 2T2 _ - - 1 and by Lemme i _ 2Tl — Lemma 8.5 Proof. i 6T0 by Lemmas 8. It is 78 8.3, we have 2mi-l mi ‘ 4mi ‘ 2mi+1 ‘ (mi+l ’ A0) A0 + 2mi_l m1 — Ami - 3mi+l Q.E.D. 6 T i 6 (n1) 6 12 - o = 3 - mi-l mi + mi + 5mi+l A0. By (11) we have = 6 (E1) - 6 T11 - 6 T21 — 6 T31 {1 . = 6 (31) - 3 (A0 + 2mi—l mi - 4 mi - 3 mi+l) ' 3 (mi+l ’ A0) ' (mi+l + A0) = 6 (31) - 6 mi-l mi + 12mi + 5 mi+l - A 3 and 8.4 and Corollary 8.2.1. convenient to introduce the numbers 21 , , by the equation: m1 = (Pi—1 '1) ' mi-l m ri 2(r1_1 ' 1) 2 Q.E.D. From (9) and the fact that rO >»2, it follows that: (l7) lim Zi =00 i—voo Lemma 8.6 lim r1 _ 0 i~+°0 ‘__ _ ' Zi Proof By (2) and (3), we can write El. _ 8 (l-l/ri_l) Zi ni-l and so lim .32 = 0. i-vm: Zi Lemma 8.7 (n1) _ 221 (2 Proof. (31) = ni(n 79 Zi - l ) (21 '1) /3. 1-1) (hi-2) /6, and from (7), 1’11 = 21111 ’ r1 ni_ l = 21111 ' r’i , r1 n1- 2 = 2 (mi-r1) , ri so then <§i> = 2 m- <2 We are now in a po results of this section. sition to present one of the main 1 Theorem 8.8 lim T 11m T l' T i i—eoo n1 140° 2 = ”1.3— :0 and i 3 3 3 lim TO _ l n _ . 1"” (31) Proof. By Corolla 1 i—+oo = n i-fioo ( i) 3 lim i-+°O _ lim _ if+oo = O by (17) and Lemma 8.6. ry 8.2.1 and Lemma 8.7, we have mi+l + Ao 421(2zi-l)(zi-l) (P1 ‘1) mi + Ao 421(221-1> (Zr—1) (vi/21> (vi/zi-l/zi> + Ao/Zi3 A (2 - l/zi) (1 - l/zi) by (8) 8O , 1 With regard to 1:323 T2 , we can first use n (31) Corollary 8.2.1 and Lemma 8.3 to eliminate mi+l and write i _ i _ T2 — 3 T3 A0 so that i 3; = 3 - A. l '_——T ’ T3 T3]. and by Corollary 8.2.1, it follows that lim T2i 1400 , = 3. T l 3 Hence, 1 i i lim T2 = lim T2 , lim T3 = o i~§OO n- i—‘W i—‘OO no (31> T3i (31> With the aid of Lemma 8.4, we have 1 lim 2 T1 lim Ao lim 2m1-1m1 lim ”m1 _lim 3m1+1 1...... —— =1...» ———+1_..° —_ i*°°_ 1“” ° (3 ) (3 ) (3 ) (3 ) (3 ) A 11m 0 = 0. Clearly, i-voo _—Ui (3 ) m w lim 1221 mi by (16) n1 1 1—900 (3 ) _’°° 221 (221-1) (Zi’l) _ lim 6 mi lim 501?3 O 1...... (in-l)(zi-l) 1"” (2-1/21‘) (1-1/21) Now, um 24 T 1‘1 - 4A lim .2_ = lim 3 O = 0 ’ 1-900 i-‘ (31) °° <§i> 81 and lim 3mi+l = lim 18 T31 - 3 A0 = o 1900 Hi 11—.” (3 ) (gi) with the aid of Corollary 8.2.1 and the first part of this theorem; therefore, 1 lim T1 1400 2 0. (gm By (12) it now follows immediately that 11 T i m 1%” i = 1. Q.E.D. (31) Theorem 8.8 says, then, that for large i, Gi resembles an empty graph in the sense that nearly all triangles are empty triangles despite the fact that the orders of the com- plete subgraphs of G1 become unbounded as i approaches infinity. SECTION 9 MISCELLANEOUS RESULTS ON LINE-GRAPHS The purpose of this concluding section is to present a few results dealing with line-graphs and some special types of graphs, namely, trees, bipartite graphs, and planar and nonplanar graph. I. Trees and Line-Graphs The line-graph of a graph containing vertices of degree three or more clearly contains triangles. The only graphs not having such vertices are arcs and circuits. We have already seen that the line-graph of an arc is an arc (and is therefore a tree) while the line-graph of a circuit is an isomorphic circuit. This leads us at once to the following. Theorem 9.1 The only line—graphs which are trees are the arcs. Definition 9.1 A connected graph in which every block is either a single edge or a single circuit is called a Husimi t_re_e_- A concept related to the Husimi tree (see [7]) is the following, whose connection with trees and line-graphs will be evident shortly. 82 83 Definition 9.2 A connected graph in which every block is a complete graph is called a completed Husimi tree. The next definition and theorem are due to Harary [4]. Definition 9.3 With every graph G there is associated a graph B(G), called the block-graph of G, whose vertex set can be put in one-to-one correspondence with the blocks of G in such a way that two vertices of B(G) are Joined by an edge if and only if the corresponding blocks of G have a (separating) vertex in common. Unlike line-graphs, there is no ”near” one-to-one correspondence between graphs and block-graphs. We shall see, however, that there is a one-to-one correspondence between trees and certain types of block—graphs. We state the aforementioned result of Harary using our terminology. Theorem of Harary A necessary and sufficient condition that a graph be a block-graph is that it be a completed Husimi tree. Theorem 9.2 A necessary and sufficient condition that a graph be the line-graph of a tree is that it be a completed Husimi tree in which all vertices have connective index at most two. 3322;. If G is a tree, then the line—graph L(G) and the block-graph B(G) are clearly isomorphic since the blocks of G are simply the edges of G. Harary's theorem then implies that L(G) is a completed Husimi tree. That the connective 84 indices of the vertices in L(G) are at most two follows since L(G) is a line-graph. Conversely, let H be a completed Husimi tree, all of whose vertices have connective index one or two. By Krausz' theorem, there exists a graph G such that L(G) = H. We shall show that G can be taken to be a tree. If G were not a tree, then G would contain a circuit. If G consists only of a circuit, then L(G) is an isomorphic circuit. Since L(G) is a completed Husimi tree, L(G) is a triangle, and we can take G to be Kl,3’ which is a tree. If G con— sists of more than a circuit, then it is easily seen that G contains an edge E adjacent to two edges of a circuit C in G but not adjacent to some edge F of C. The corresponding vertices e and f of L(G) must lie on a circuit of L(G), and they are not adjacent. This contradicts the fact that L(G) is a completed Husimi tree. Q.E.D. II. Bipartite Graphs and Line-Graphs As already mentioned, Moon (with the aid of Hoffman) has characterized the line-graph of nearly all complete bi- graphs. The problem of dealing with the line-graphs of bi- graphs in general does not seem to be particularly easy. We next determine the class of all connected bipartite line- graphs. The proof of the theorem which we shall give depends heavily on the following well-known theorem which can be found in Ore [ll]. 85 Theorem. A graph G is a bigraph if and only if all circuits contained in G are of even length. Theorem_9.; The only connected bipartite line-graphs are arcs and circuits of even length. 23993. Let G be a connected graph and L(G) a bigraph. If G contains a vertex of degree three or more, then L(G) contains a triangle, and by the previous theorem, L(G) is not bipartite. Thus, G is either an arc or a circuit. If G is an arc, then L(G) is an arc, thus contains no circuits of any kind and is a bigraph. If G is a circuit, then L(G) is an isomorphic circuit, so L(G) will be bipartite if and only if G is a circuit of even length. Q.E.D. III. Planar and Nonplanar Graphs and Line-Graphs One of the most important concepts in all of graph theory is that of the planar graph. Definition 9.4 A graph is called planar if it can be drawn in the plane in such a way that no two of its edges inter- sect except at a vertex. A result of Kuratowski which may very well be termed ”the fundamental theorem” of topological graph theory com- pletely determines whether a graph is planar (see, for example, Harary [5]). One more definition is required before stating this result. 86 Definition 9.5 Two graphs are homeomorphic if it is possible to insert new vertices of degree two into their edges in such a way that the two resulting graphs are isomorphic. Theorem of Kuratowski A graph G is planar if and only if it has no subgraph homeomorphic to the complete graph K5 or the complete bigraph K3’3. If G is planar, it is quickly seen, by examples, that L(G) may or may not be planar. If G has a vertex of degree five or more, then certainly L(G) is nonplanar since L(G) contains the subgraph K5. However, planar graphs exist in which every vertex has degree less than five but whose line- graph is nonplanar. What conditions must be placed on a planar graph in order to assure that its line—graph be planar also is, at present, not clear. We do present, however, the following result. Theorem 9.4 The line-graph of a nonplanar graph is non- planar. Proof. Let G be a nonplanar graph. Then either G contains K or K3 5 phic to K5 or K3 3. We shall show that under any circum- .9 3 as a subgraph or some subgraph homeomor- ) stance, L(G) contains a subgraph homeomorphic to K3 3 and hence is nonplanar by the Theorem of Kuratowski. If G contains the subgraph K then let us denote the 5) vertices of K5 by l, 2, 3, 4, and 5, and the edges by Eij’ 87 where Eij joins vertex i to vertex j, i < j. Let eij denote the vertex in L(G) corresponding to Eij' The following graph is then seen to be a subgraph of L(G). €12 elbr €25 €13 €35 e24 e15 'e45 Figure 9.1 This subgraph H is homeomorphic to Suppose that G K3,3. does not contain K5 as a subgraph but only a subgraph homeo- morphic to it. Then this subgraph differs from K5 only in that it has additional vertices of degree two inserted in the edges. Suppose that G contains a subgraph homeomorphic to K5 having only one more vertex than K5. If the additional vertex is inserted in an edge of K5 whose corresponding vertex is not in H, then H is a subgraph of L(G) in this case also. Suppose, however, that the vertex k is placed in the edge Eij in K5 and that the corresponding vertex eij is a vertex of H. If the degree of eij in H is two, then let E now denote the edge which joins vertex i and vertex 1J k and let Ejk be the edge joining vertex k and vertex j. If we now place the corresponding vertex ejk of L(G) in the 88 appropriate edge of H, we obtain a subgraph of L(G) which is homeomorphic to H and to K3,3. If, on the other hand, the degree of e13 in H is three, we proceed somewhat dif- ferently. We observe that in H’eij is either adjacent to exactly one vertex of the type eip (or epi) or adjacent to exactly one vertex of the type eiq (or eqj)‘ (For example, in the case of the vertex e14, 1 = l and j = 4, and e14 is ). adjacent to e but adjacent to neither el2 nor e l5 13 Assume eij is adjacent to exactly one vertex of the type eip, say eir (or eri’ if r < i). Now if the vertex k is inserted in the edge Eij of K we let Eij denote the edge 5, joining vertex i and vertex k, and we let Ejk denote the edge joining vertex k and vertex j. It is now seen that L(G) contains a subgraph which differs from H only by the addition of a vertex of degree two in the edge joining e13 and eir‘ This subgraph is homeomorphic to K If addi— 3:3. tional vertices of degree two are now inserted in the edges of K5, it is possible to continue the above procedure, each time arriving at a subgraph of L(G) which is homeomorphic to K3,3. Should G actually contain K3)3 as a subgraph then the vertex set U of this subgraph can be expressed as U = U'LJU", where U' ==‘{l, 2, 3‘} and U” = {4, 5, 6'} and where Eij: i 6 U', j e U”, denotes the edge joining vertex i and vertex j. Let e1J be the corresponding vertex in L(G). A subgraph of L(G) is shown in Figure 9.2. 89 €14 €35 €25 e26. . . 634 815 eio 624 Figure 9.2 This subgraph is homeomorphic to K3’3. If G contains only a subgraph homeomorphic to K3,3, then the graph of Figure 9.2 has the desirable properties which allow us to proceed in a completely analogous way to that in the preceding case to show L(G) must have a subgraph homeomorphic to K3,3. Q.E.D. We conclude this topic, this section, and this thesis with a conjecture after giving a definition (see [1]) and a remark. Definition 9.6 The thickness t(G) of a graph G having at least one edge is the minimum number of pairwise edge dis- joint planar subgraphs of G whose sum is G. Theorem 9.4 may now be stated as follows: If t(G)3:2, then t(L(G))_>_ 2. Conjecture. If t(G) _>_ n, then t(L(G)) _>_ n. INDEX OF DEFINITIONS The number opposite the term refers to the page on which the term is first defined or explained. adjacent edges -- 4 adjacent vertices —- 4 are -— 6 automorphism group of a graph-l4 biconnected —-4O bigraph -- 8 bipartite graph ——8 block -- 26 block-graph -- 83 circuit -- 6 circuit edge -- 25 complement of a subgraph in a graph -- 5 complete bigraph -- 8 complete graph —- 4 completed Husimi tree -- 83 component -- 7 connected component -- 7 connected graph —- 7 connected, m - -- 40 connected vertices -- 6 connective index —— 27 connectivity -— 4l cycle -- 6 cyclic path -- 6 cut edge -- 25 cut point-- 25 degree of an edge -- 17 degree of a vertex -- 4 diagonal —- 6 digraph -- 3 direct sum -— 7 directed edge —- 3 directed graph-- 3 disjoint subgraphs -- 7 doubly connected -- 4O 9O edge -- 3 edge connected, m - -- 32 edge connectivity -- 32 edge direct sum -- 7 edge disjoint subgraphs -- 7 edge incidence matrix -- ll edge regular graph-- 17 empty graph -- 4 empty triangle -- 76 Euler graph -- 50 Euler path -- 50 even edge -' 50 even vertex-- 5O graph -- 3 Hamilton circuit -- 56 Hamilton graph -- 56 Hamilton index -- 7l homeomorphic graphs -- 86 Husimi tree -- 82 incidence matrix -- ll incidence of edge and vertex -- 4 interior vertex -- 40 isolated vertex -- 4 isomorphic graphs -- 6 limit graph -- 24 line ’- line-graph -- 1 loop -- 3 nonseparable graph -‘ 27 odd edge -- 50 odd vertex -- 50 order of a graph -- 4 ordinary graph -— 3 path -- 6 planar graph point-- 3 regular graph -- repeated line-graph —- section graph -- section graph of a circuit-- 6 -- 85 8 separating edge —- 25 separating vertex -- 25 sequential graph -- 58 star graph -- 8 subgraph -- 5 l 91 terminal edge-- 4 terminal vertex-- 5 thickness of a graph-- 89 tree -- 7 triangle-- 4 triangle of type T -- 76 triangle of type Tl -- 76 triangle of type T2 -- 76 triangle of type T3 -- 76 triply connected -- 41 trivial graph—- 4 vertex vertex vertex vertex vertex vertex " 3 connected, m - -- 4O connectivity -- 41 incidence matrix -- ll of attachment—- 40 set -- 3 10. ll. l2. l3. 14. 15. BIBLIOGRAPHY L. W. Beineke and F. Harary. On the Thickness of a Complete Graph. Bull. Amer. Math. Soc., (to appear). C. Berge. The Theory of Graphs and its Applications. (London, 1962) W. S. Conner. The Uniqueness of the Triangular Association Scheme. Ann. Math. Statist, l5l-l9O (19587- F. Harary. A Characterization of Block-Graphs. Can. Math. Bull., l-6(l963). F. Harary. Recent Results in Tppological Graph Theory. Acta Math. Hung., (to appear). F. Harary. Some Historical and Intuitive Aspects of Graph Theory. SIAM Review, l23-l3l (1960). F. Harary and R. Z. Norman. The Dissimilarity Charac- teristic of Husimi Trees. Ann. Math., 134-141 (1953). A. J. Hoffman. On the Uniqueness of the Triangular Association Scheme. Ann. Math. Statist., 492-497 (19607. J. W. Moon. On the Line-Graph of the Complete Bigraph. Ann. Math. Statist., 664-6677(l963). E. A. Nordhaus and B. M. Stewart. Triapgles in an Ordinary Graph. Can. J. Math., 33-41(1963). O. Ore. Theory of Graphs. (Providence, I962). G. Sabidussi. Graph Derivatives. Math. Zeit., 385-401 1961). S. S. Shrikhande. On a Characterization of the Triangular Association Scheme. Ann. Math. Statist., 39- 47 (1959)- S. S. Shrikhande. The Uniqpeness of the L2 Association Scheme. Ann. Math. Statist., 781-798 (1959). H. Whitney. Congruent Graphs and the Connectivity of Graphs. Amer. J. Math., 150-168 (1932). 92 "‘111111111111S