Citation
P-competition graphs and p-neighborhood graphs

Material Information

Title:
P-competition graphs and p-neighborhood graphs
Creator:
McKenna, Patricia A
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
vii, 97 leaves : illustrations ; 28 cm

Subjects

Subjects / Keywords:
Geometry ( lcsh )
Graph theory ( lcsh )
Geometry ( fast )
Graph theory ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 93-97).
Thesis:
Submitted in partial fulfillment of the requirements for the degree, Doctor of Philosophy, Applied Mathematics
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Patricia A. McKenna.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
36474202 ( OCLC )
ocm36474202
Classification:
LD1190.L622 1996d .M355 ( lcc )

Downloads

This item is only available as the following downloads:


Full Text

PAGE 1

p-COMPETITION GRAPHS AND p-NEIGHBORHOOD GRAPHS by Patricia A. McKenna B.A., Potsdam College of the State University of New York, 1988 M.S., University of Colorado at Denver, 1994 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Doctor of Philosophy Applied Mathematics 1996

PAGE 2

This thesis for the Doctor of Philosophy degree by Patricia A. McKenna has been approved for the Department of Mathematics by J.Richard Lundgren David C. Fisher Sta ey E. Payne Date

PAGE 3

McKenna, Patricia A. (Ph.D., Applied Mathematics) p-Competition Graphs and p-Neighborhood Graphs Thesis directed by Professor J. Richard Lundgren ABSTRACT The competition graph was introduced in the late sixties by Joel Cohen in the context of competition among species in an ecosystem. Since that time, a substantial body of research has developed on the topic and its generalizations. Competition graphs also have applications in communications networks, since they are a useful tool in solving the frequency problem. Extensive study of the competition graph began in the late seventies and continues today. In this paper, we consider the generalizations of Cohen's ideas known as the pcompetition graph, introduced in 1989, and the p-neighborhood graph, generally concentrating on the case in which p = 2. We identify classes of graphs which are the 2-competition graphs of loopless symmetric digraphs. We give a sufficient condition for the (2)-neighborhood graph of a chordal graph to be an interval graph, as well as a necessary and sufficient condition for an interval graph to have an interval (2)-neighborhood graph. Finally, we consider the properties of those interval graphs which do not have interval (2)-neighborhood graphs and show that every interval graph has a perfect graph as its (2)-neighborhood graph. All of this work generalizes what was done in the case p = 1, and to our knowledge, this is the first extensive study of the case p = 2. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. iii

PAGE 4

Contents Chapter 1. Introduction 1.1 History of Competition Graphs ................... 1.2 p--Competition Graphs ............... ....... 1.3 Overview ....... ........................ 2. The p--Competition Graphs of Symmetric Digraphs and p--Neighborhoo(' Graphs 2.1 Introduction .............................. 2.2 p--Neighborhood Graphs as p--Competition Graphs of Symmetric Digraphs .................... 2.3 Which Graphs are (2)-Neighborhood Graphs? 3. Interval p--Neighborhood Graphs 3.1 Introduction . . . . 3.2 Which graphs have interval (2)-neighborhood graphs? 3.3 Interval graphs have interval [2]-neighborhood graphs 4. Interval Graphs with Interval (p)-Neighborhood Graphs iv 1 1 4 6 8 8 8 15 32 32 33 41 45

PAGE 5

4.1 Introduction . . . . . . . . . . . . . . 45 4.2 Categorization of Nonsimplicial Edges, and Definitions of Sets 47 4.3 Main Result . . . . . . . . . . . . . . 50 5. The (2)-Neighborhood Graphs of Interval Graphs Are Weakly Chordal. 78 5.1 Introduction . . . . . . . . . 5.2 If G is interval, then N2 (G) is weakly chordal. 5.3 What if N2 ( G) contains a chordless 4-cycle? 6. Conclusion References ........ ' ................. v 78 78 81 92 93

PAGE 6

Figures Figure 1.1 G is the competition graph of D. Note that the inset of any vertex in D forms a clique in G. . . . . . . . . . . 2 1.2 From left to right, a graph G, its 2-step graph, and its square. 4 1.3 A digraph and its 2-competition graph. . . . . . . 5 2.1 If the graph above is a subgraph of H, then triangle abc is a subgraph of N2(H). . . . . . . . . . . . . . . 16 2.2 Zs is the (2)-neighborhood graph of the Mobius ladderon 8 vertices H, while Z6 is the (2)-neighborhood graph of the ladder on 6 vertices H'. . . . . . . . 2.3 P7 is the (2)-neighborhood graph of H. 2.4 A caterpillar labelled as in the proof of Theorem 8. Note that it is possible (although not depicted here) that both ek and ek+l are pendant edges at Vx, or that ek is nonpendant (hence ek = eq} and ek+l is pendant, or that both edges are nonpendant. Also note that eq+k may or may not be a pendant edge. In either case, y = v; is 17 18 a nonpendant vertex. . . . . . . . . . . . . 19 Vl

PAGE 7

2.5 The caterpillar' above is the (2)-neighborhood graph of H. . . 20 2.6 Although tree NC7 satisfies e(NC7 ) = 2k 2: 21:l(NC7 ), NC7 is not a (2)-neighborhood graph. . . . . . . . . . . . 24 2. 7 We illustrate the use of Lemma 2 by choosing an edge in H (in this case, edge [2,8}), and add 4-cycle 2pq8 to H to create H'. This gives tree G' = N2(H'), which has caterpillar G as a generated subgraph ............... ................. 26 2.8 Graph G (the caterpillar in bold) is a subgraph of B31, and N2(H) = G................................. 27 2.9 B7 is a (2)-neighborhood graph, since it satisfies Theorem 8, and B15 is a (2)-neighborhood graph, since B15 = Nz(H). 2.10 Labels for leaves and their neighbors in B2n_1 3.1 3.2 A gr-aph G and its (2)-neighborhood graph ... Three graphs and their (2)-neighborhood graphs. 3.3 G is not chordal, and 7 = 0 does not form a. (2)-neighborhood cover of G. ........................... 5.1 If N2(G) has a chordless 4-cycle as a generated subgraph, then G 29 30 33 34 39 has one of the graphs above as a generated subgraph. . . . . 81 Vll

PAGE 8

1. Introduction 1.1 History of Competition Graphs Competition graphs were first introduced by Joel Cohen [9] in 1968 in relation to food webs. Since then, the topic has been extensively studied and generalized, proving to be a rich area of research. Applications of competition graphs also can be found in the study of communications networks, in particular, the frequency assignment problem. Various authors have studied a multitude of questions related to competition graphs since the late 1970's. These authors include Roberts and Steif [29], Brigham and Dutton [5], and Kim [15]. The competition graphs of strongly connected and Hamiltonian digraphs were investigated by Fraughnaugh, Lundgren, Maybee, Merz, and Pullman [11], while the competition graphs of tournaments were studied by Fisher, Lundgren, Merz, and Reid [10]. 'Langley, Lundgren, and Merz [19] explored the competition graphs of interval digraphs. A generalization called the -tolerance competition graph was introduced by Brigham, McMorris, and Vitray [7], and explored further by the same authors [8] as well as Anderson, Langley, Lundgren, McKenna and Merz [2]. 1

PAGE 9

For basic graph theory definitions and terminology, the reader is referred to Roberts [30]. Throughout the paper we let E(G), V(G), e(G), Z4(G), l:>(G), d(x, y), Pn, and O(x) denote the edge set of G, the vertex set of G, the number of edges of G, the number of 4-cycles in G, the highest vertex degree in G, the distance between vertices x and y, the path on n vertices, and the outset of a vertex x in a digraph respectively. Unless otherwise stated, a graph is on n vertices. Basic knowledge of competition graphs is helpful before proceeding to generalizations such as p-competition graphs and p-neighborhood graphs. We will start with the definition. The competition graph of a digraph D = (V ,A) is the graph G = (V,E) where [x, y] E E if and only if 3 z E V such that both (x, z) and (y, z) E A. Example 1 Graph G of Figure 1.1 is the competition graph of digraph D. b a c f e d Figure l.l:G is the competition graph of D. Note that the inset of any vertex in D forms a clique in G. 2

PAGE 10

A collection C of sets of vertices from a graph G is called an edge-clique cover (ECC) of G if each set in C is either a (not necessarily maximal) clique or the empty set, and every edge in G is in at least one of the cliques of C. The number of cliques in a smallest edge-clique cover is the edge-clique cover number of G, denoted 11e(G). In studying competition graphs, the edge-clique cover number of a graph is of utmost importance, since it is proved in [5] that 11e(G) ::; n if and only if G is the competition graph of some digraph. Other applications of edge clique covers can be found in Roberts [31]. Given a graph G we construct the open neighborhood graph N(G) introduced by Acharya and Vartak [1], as follows. There is an edge between two vertices x and y in N(G) if and only if N(x) n N(y) # 0 in G (where N(v) is the open neighborhood of vertex v, i.e., those vertices which are adjacent to v, not including v). Similarly, [x, y] is an edge in the closed neighborhood graph of G, N[G], if and only if N[x] n N[y] oft 0 in G, where N[v] = N(v) U {v}. For more on neighborhood graphs, see Boland, Brigham, and Dutton ([3] and [4]), and Brigham and Dutton [6]. The 2-step graph S2 (G) has an edge between vertices x and y if and only if there is a path of length 2 between x and y in G. The square G2 has an edge between x and y if and only if there is a path of length 2 or less between x 3

PAGE 11

and y in G. Note that S2(G) = N(G) and G2 = N[G]. For results on 2-step graphs, see Lundgren, Maybee, and Rasmussen [24], Lundgren, Merz, Maybee, and Rasmussen [21], and Lundgren and Rasmussen [23]. For work on the square of a graph, see Harary and McKee [13], Lundgren, Merz, and Rasmussen [22], Raychaudhuri [27], and Raychaudhuri and Roberts [28]. See Figure 1.2. Figure 1.2: From left to right, a graph G, its 2-step graph, and its square. 1.2 p-Competiton Graphs The p-competition graph H of a digraph D introduced in 1989 by Kim, McKee, McMorris, and Roberts [17], has the same vertex set as D, with edge [x, y] in E(H) if and only if x and y have at least p common outneighbors in D. The graph H is denoted Cp(D). See Figure 1.3. The research in this area has thus far focused on determining whether or not a given graph is the p-competition graph of some digraph. The case where the digraph is acyclic is discussed by Kim, McKee, McMorris, and Roberts in (16], while p-competition graphs of loopless Hamiltonian and loopless strongly 4

PAGE 12

Figure 1.3: A digraph and its 2-competition graph. connected digraphs are explored by Langley, Lundgren, McKenna, Merz, and Rasmussen in [18]. In this paper, we focus on the case where D is symmetric, by considering the (p)-neighborhood graph (read "p-open-neighborhood graph") of a graph G, denoted Np(G), where [x,y] E E(Np(G)) if and only if IN(x) n N(y)l2: pin G. The [p]-neighborhood graph (read "p-closed neighborhood graph") of G, denoted Np[G], is defined in the expected fashion. That is, [x, y] E E(Np[G]) if and only if IN[x] n N[y]l 2: pin G. The graph Np(G) is the p-competition graph of a loopless symmetric digraph D, where G is the graph underlying D. Similarly, Np[G] is the p-competition graph of a symmetric digraph D' that has a loop at every vertex, where G is the graph underlying D'. These graphs are generalizations of the neighborhood graphs (or 2-step graph and square) mentioned in Section 1.1, which have been extensively studied. In those instances, the case p = 1 was under consideration. 5

PAGE 13

Until now, that was the only p to be explored. Study of (p)-neighborhood graphs in the case p = 2 is the main subject of this paper, with occasional discussions about larger p. 1.3 Overview We concentrate in this paper on the study of p-competition graphs in the in stance where the digraph is symmetric. We relate the problem to 2-step graphs, squares, (p )-neighborhood graphs, and [p]-neighborhood graphs in Section 2.2. In Section 2.3 we identify some familiar graphs as 2-competition graphs of loopless symmetric digraphs. A question that has been studied previously in the case p = 1, because of its applications in the frequency assignment problem, is "which symmetric digraphs have interval competition graphs?" In [20], Lundgren, Maybee, and Rasmussen give a necessary and sufficient condition for an interval graph to have an interval open neighborhood graph, thus answering the question for those symmetric di graphs whose underlying graphs are interval. We answer the analogous question in Chapters 3, 4 and 5 for the case p = 2, giving a necessary and sufficient condi tion for an interval graph to have an interval (2)-neighborhood graph. Chapter 3 consists of a lead-in to the main result which is presented in Chapter 4. In Chapter 5, we consider the properties of those interval graphs which do not have 6

PAGE 14

interval (2)-neighborhood graphs and show that every interval graph has a (2) neighborhood graph which is a perfect graph. 7

PAGE 15

2. The p-Competition Graphs of Symmetric Digraphs and p-Neighborhood Graphs 2.1 Introduction The focus of this and the following chapters is on the study of p-competition graphs of symmetric digraphs. We discuss in Section 2.2 the relationship between such a graph and the p-neighborhood graph of the underlying graph of the symmetric digraph. In Section 2.3, we identify classes of triangle-free graphs as (2)-neighborhood graphs, and discuss the difficulties in producing a concise list of all such triangle-free graphs. Such a list was possible in the case p = 1, but proves elusive when p = 2, as we shall see. 2.2 p-Neighborhood Graphs asp-Competition Graphs of Symmetric Digraphs We now consider only symmetric digraphs, and establish the relationship between p-competition graphs and p-neighborhood graphs. This generalizes the work in [20] on 2-step graphs and in [28] on the square of a graph. Proposition 1 If the symmetric digraph D is loopless, then Cp(D) Np(G), where G is the graph underlying D. 8

PAGE 16

Proof: We need to show that [x, y] is an edge in Cp(D) if and only if [x, y] is an edge in Np(G). [x,y] E E(Cp(D)) <==} IO(x) n O(y)I::C: pin D <==} IN(x) n N(y)l 2': pinG<==} [x, y] E E(Np(G)). Proposition 2 If the symmetric digraph D has a loop at every vertex, then Cp(D) = Np[G], where G is the loopless underlying graph of D. Proof: We need to show that [x, y] is an edge in Cp(D) if and only if [x, y] is an edge in Np[G]. [x, y] E E(Cp(D)) <==} IO(x) n O(y)I::C: pin D <==} IN[x] n N[yJI 2': pinG<==} [x, y] E E(Np[G]). Example 2 The graphs and digraph of the figure below illustrate the principles of Proposition 1. 9

PAGE 17

D: a C,(D): a d c G: a N2(G): a Using the propositions and a characterization of p-competition graphs of [17], we characterize those graphs which are p-neighborhood graphs as follows. The result in Theorem 2 is mentioned by Majors and McMorris in [26], and Theorems 1 and 2 are proved by Majors in [25]. The proofs in [25] do not make use of the competition graph relationship, and as a result are considerably more lengthy than those presented here. Theorem 1 [25] A graph G is a (p }-neighborhood graph if and only if there is a family F = {51 ... Sn} of subsets of V(G) with n = jV(G)! satisfying the following three conditions: 10

PAGE 18

1. For every set i1 ... ip of p distinct indices, T = S;, n ... n S;p is either empty or induces a clique of G and the collection of sets of the form T covers all edges of G. 2. Vertex i E Sj if and only if vertex j E S;. 3. Vertex i if S; for all i E {1, ... n}. Proof: ( *) If G is a (p )-neighborhood graph, then there exists a graph H such that Np(H) =G. LetS;= NH(i) for every vertex i. Then the family of sets S; satisfies conditions (1)-(3). (-=) Condition (1) convinces us that G is the p-competition graph of some digraph D. We can construct D by letting S; = In(v;) for all vertices vi in D. Condition (2) forces D to be a symmetric digraph, and condition (3) forces D to be loopless. We conclude that G is the p-competition graph of a loopless symmetric digraph D, and by Proposition 1 G is the (p)-neighborhood graph of the underlying graph of D. Theorem 2 [25], [26] A graph G is a {p}-neighborhood graph if and only if there is a family F ={51 ... Sn} of subsets of V(G) with n = [V(G)[ satisfying the following three conditions: 11

PAGE 19

1. For every set i1 ... ip of p distinct subscripts, T = 5;1 n ... n 5;v is either empty or induces a clique of G and the collection of sets of the form T covers all edges of G. 2. Vertex i E 5j if and only if vertex j E 5;. 3. Vertex i E 5; for all i E {1, ... ,n }. Proof: The proof is analogous to that of Theorem 1, with condition (3) convinc ing us that D has a loop at every vertex. The result follows from Proposition 2 We now consider the relationship between p-neighborhood graphs and 2-step graphs and squares. The case p = 1, where a digraph Dis loopless and symmetric, is studied in [20], and we have 52(G) = C(D) = N(G), where G is the graph which underlies D. Similarly, if symmetric D has a loop at every vertex, we find in [28] that G2 = N[G], where G is the loopless graph which underlies D. We next give a necessary condition for the 2-step graph of a graph G to be the (p )neighborhood graph of G (for p > 1), and a necessary condition for the square of a graph G to be the [p]-neighborhood graph of G (for p > 1). Theorem 3 Given a graph G, if Np(G) =52 ( G)= N(G) and p > 1, then every ?3 of G lies in a K2,p 12

PAGE 20

Proof: Suppose Np(G) = S2(G), and assume there exists a P3 in G which does not lie in a K2,p Let the consecutive vertices of the P3 be x, y, and z. Vertices x and z have fewer than p common neighbors, so [x, z] E(Np(G)). However, since x and z have a path of length 2 between them through y, we know [x, z] E E(S2(G)), a contradiction. Hence every P3 of G lies in a K2,p For [p]-neighborhood graphs and squares, we present a similar necessary con dition. Theorem 4 Given a graph G, Np[G] induced Fa of G lies in a K2,p G2 -N[G] and p > 1 imply every Proof: Assume Np[G] = G2 and there exists an induced P3 xyz, that does not lie in a K2,p Since xyz is an induced P3 we know [x, z] is not an edge of G, so IN[x] n N[z]l :S p-1, and [x, z] E(Np[G]). However, [x, z] E E(G2), a contradiction. Note that for general p, every induced P3 of G lying in a K2,p is not a sufficient condition for Np[G] = G2 This is because [x, y] E E(G2 ) does not imply [x, y] E E(Np[G]) (let p = 3 and G = K3 3 for example). However, when p = 2 it is a sufficient condition. Theorem 5 Given a graph G, 13

PAGE 21

(a) Nz(G) = Sz(G) = N(G) if and only if every P3 ofG lies in a 4-cycle, and (b) N2[G] = G2 = N[G] if and only if every induced P3 of G lies in a 4-cycle. Proof: For both (a) and (b), necessity follows as a corollary of Theorem 4, since Z4 = K2 2 To prove sufficiency in part (a), suppose every P.1 of G lies in a Z4 Then [x,y] E E(N2(G)) '* x andy have at least 2 common neighbors in G > [x, y] E E(S2(G)). The last reverse implication is valid since [1:, y] E E(S2(G)) implies x and y have at least one common neighbor, and by our assumption, one common neighbor implies the existence of another. For sufficiency in part (b), suppose every induced P3 of G lies in a Z4 Then [x, y] E E( G2 ) if and only if x and y have a path of length 2 between them in G or [x, y] E E( G) (perhaps both) if and only if x and y have an induced path of length 2 between them in G or [x, y] E E( G) (not both) if and only if x and y have 2 induced paths of length 2 between them or [x, y] E E( G) (not both) if and only if x and y are diagonally opposed on an induced 4-cycle of G or [x, y] E E(G) (not both) if and only if IN[x] n N[y]l 2: 2 if and only if[x, y] E E(N2[G]). Hence. N2[G] = G2 In the next section we identify some familiar graphs as (p )-neighborhood graphs for the case p = 2. 14

PAGE 22

2.3 Which Graphs are (2)-Neighborhood Graphs? It is a relatively simple matter to construct the (p)-neighborhood graph of a graph G, simply examine the off-diagonal entries of A(G)2 where A(G) is the adjacency matrix of G. However, identifying those graphs which are (or are not) (p )-neighborhood graphs is considerably more complicated. Given a graph G, we must find a graph H such that Np(H) = G, or prove that no such H exists. The case p = 1 is fully explored in [4] for triangle-free graphs G, where the authors prove that the only nontrivial connected triangle-free open neighborhood graphs are the odd cycles on 5 or more vertices. For the case p = 2 we have identified some familiar graphs as (p )-neighborhood graphs and continue to seek a full classification of such graphs. The following result regarding triangle-free graphs is a useful tool in proving the theorems of this section. Lemma 1 If a triangle-free graph G is the (2)-neighborhood graph of a graph H, then the number of edges in G is twice the number of 4-cycles in H, 2(Z4(H)) = e(G). Proof: Suppose G = N2(H) and G is triangle-free. To see that 2(Z4(H)) 2 e( G), we simply note that each 4-cycle in H produces at most two edges in G. In fact, this inequality holds whether or not G is triangle-free. Now assume 2(Z4(H)) > e(G). Then some 4-cycle of H does not produce its quota of two 15

PAGE 23

edges in G, and therefore some pair of vertices x and y is diagonally opposed on more than one 4-cycle of H, as shown in Figure 2. 1. However, if the graph shown in Figure 2.1 is a subgraph of H, then triangle abc is a subgraph of N2(H) = G, a contradiction. Hence 2(Z4(H)) = e(G). X a c y Figure 2.1:If the graph above is a subgraph of H, then triangle abc is a subgraph of N2(H). Theorem 6 The cycle Zn is a (2)-neighborhood graph if and only if n 2: 6 is even. Proof: By the lemma, odd cycles are not (2)-neighborhood graphs, so we consider the cycle z2k If k = 2, we know from [14] that z4 is not the 2-competition graph of any digraph; in particular it is not the 2-competition graph of a loopless symmetric digraph, i.e., a (2)-neighborhood graph. The Mobius ladder (e.g. graph H in Figure 4 is a Mobius ladder of order 8) has Z2 k as its (2)-neighborhood graph when k is even and k 2: 4, and the ladder (e.g. graph H' in Figure 4 is 16

PAGE 24

a ladder of order 6) has Z2 k as its (2)-neighborhood graph when k is odd. (See Figure 4 for examples.) k=4 k=3 a e a d b f b b e c g c c f d h d h ' H G = N, (H)= Z8 L H' G' = N,(H'! = z, Figure 2.2:Z8 is the (2)-neighborhood graph of the Mobius ladder on 8 vertices H, while Z6 is the (2)-neighborhood graph of the ladder on 6 vertices H'. In the triangle-free case, the challenge in determining whether or not a graph G is a (2)-neighborhood graph is in finding a special pairing of the edges of G. This pairing must determine the 4-cycles of H, so that N2(H) =G. With C2k, we see that if an edge is paired with the edge directly qpposite it on the cycle and these pairings are used to determine the 4-cycles of H, we have a method of creating H such that N2(H) = Czk A similar idea works for Pn. Theorem 7 Pn is a (2)-neighborhood graph if and only if n is odd and n 5. 17

PAGE 25

Proof: Suppose Pn is a (2)-neighborhood graph. By Lemma 1, e(Pn) must be even, so n is odd. The graphs on 3 vertices are K3 P3 K2 U h, and !3 ; none of these has P3 as its (2)-neighborhood graph, so P3 is not a (2)-neighborhood graph. Thus n 2: 5. Conversely, let the vertices of Pn be labelled consecutively as v1 v2, .. Vn, with n 2: 5, n = 2k + 1. We must construct H such that N2(H) = Pn. Label the edges of Pn consecutively as e1 e2 ... ek, e;, ... If we pair edge ei with edge e:, then the four endpoints of those two edges are distinct for all i (since n 2: 5). With those four vertices we create the 4-cycle ViVi+kVi+lVi+k+l in H. The diagonals of this 4-cycle are {vi,vi+l} and {vi+k,vi+k+l}, giving edges [vi, vi+l] = ei and [vi+k> vi+k+l] = e: in N2(H). Let H be the graph consisting only of these 4-cycles. Then N2(H) = Pne' 3 Figure 2.3: P7 is the (2)-neighborhood graph of H. H See Figure 2.2 for an example of the method described in the proof of Theorem 7 for P7 The problem of determining which trees are (2)-neighborhood graphs remains unsolved. However, we do know exactly which caterpillars G are (2)-18

PAGE 26

neighborhood graphs, as presented next. The proof uses a pairing of the edges of G that is similar to ideas used in the last two proofs. Theorem 8 A caterpillar G is a (2)-neighborhood graph if and only if e( G) = 2k 2: 26.(G). Proof: For necessity, suppose G = N2(H). By the lemma, e(G) = 2k. To see that e( G) 2: 26.( G), note that a vertex of degree 6.( G) in G must be on 6.( G) 4-cycles in H. Thus Z4(H) 2: 6.(G), and by the lemma, e(G) = 2(Z4(H)), so 2: 6.(G) and e(G) 2: 2(6.(G)). The proof of sufficiency is algorithmic. We present the algorithm next, and give an example of its use in Figure 2.5. vl v2 va Vx-1 Vx Vs a+l ea+b+l e, ek+l eq+k f.\:a f\:a+l\',. 1\k \e2k y z Figure 2.4: A caterpillar labelled as in the proof of Theorem 8. Note that it is possible (although not depicted here) that both ek and ek+1 are pendant edges at Vx, or that ek is nonpendant (hence ek = eq} and ek+l is pendant, or that both edges are nonpendant. Also note that eq+k may or may not be a pendant edge. In either case, y = Vi is a nonpendant vertex. Let G be a caterpillar with e( G) = 2k 2: 26( G). Label G as in Figure 2.4. That is, choose as a starting point one of the nonpendant vertices which is adjacent to exactly one other non pendant vertex and call it v1 (There are two 19

PAGE 27

e e4 t e I 10 II I! e, % c d f g z h j H: g c f d z h j Figure 2.5: The caterpillar above is the (2}-neighborhood graph of H. such vertices from which to choose.) Label the pendant edges incident at vertex v1 with e1 ... e . Assign the label ea+l to the edge connecting v1 with the next nonpendant vertex, v2 Label the pendant edges incident at v 2 as ea+2 . ea+b Assign the label ea+b+l to the edge connecting v2 with its one unlabelled (and non pendant) neighbor v3 Continue in this manner until the edges of G have been labelled e1 e2, ... e2k Note that fori= 1 to k, edges ei and ei+k have four 20

PAGE 28

distinct vertices as endpoints. This is due to the method used in labelling the edges and to the fact that k ;:: D. (G). Consider the edges of G to be in two halves, the first one being e1 ... ek (call this the red half) and the second one being ekH, ... e 2 k (call this the blue half). Because of the method used to label the edges of G, exactly one vertex appears in both halves, call it vertex Vx. Vertex Vx is an endpoint of edge ek+l and is nonpendant. It is also an endpoint of edge ek and possibly some edge(s) preceding ek. Let eq be the "first" edge in e1, ... ek which has vertex Vx as an endpoint. Then eq connects two nonpendant vertices. We use these labels and facts to construct a graph H such that N2(H) = G. First, pair edge e1 with edge ek+l By construction, the endpoints of these edges are distinct. With these four vertices, form a 4-cycle 01 on which the endpoints of e1 are diagonally opposed and the endpoints of ek+l are diagonally opposed. Create a 4-cycle, 02 using the four vertices of e2 and ek+z in the same manner. Note, however, that 02 shares an edge with 01 since e, and e2 are adjacent in G and ek+l and ek+2 are adjacent in G. Continuing in this manner, building one 4-cycle after another, each new 4-cycle will share exactly one edge with some 4-cycle(s) which preceded it, until we reach edge eq. This edge will be paired up with edge eq+b but we cannot build the necessary 4-cycle by simply adding 21

PAGE 29

two new vertices as we have up to this point. This is because Vx was one of the vertices of C1. The endpoints of eq are Vx-! and Vx Let the endpoints of eq+k be y and z. Let y = v; for some i (so y is a nonpendant vertex), and if z is a nonpendant vertex, then z =vi+! Up to this point, the graph (call it H') consists of 4-cycles connected in such a way that any given 4-cycle shares exactly one of its edges with other 4-cycles, so H' is bipartite. In fact, we can color the vertices from the red list red, and those from the blue list blue. Note that vertex Vx is colored blue, since it has not yet been used to form an edge from the red half of the list. Vertex Vx-1 is red and vertex y is blue (vertex z is not yet part of the construction). The graph H' does contain edge [vx_1 y] (by construction). To create the 4-cycle Vx_1yvxz, which we need to get edges eq and eq+k in N2(H), we must add edge [y, vx] to H' without creating any unwanted 4-cycles. So, we must check to see if there are any paths of length 3 between y and Vx in H'. Any path of length 3 in H' would have vertices of different colors as endpoints. Since y and Vx are both blue, no such path exists between them, so we can add edge [y, vx] to H' without creating any unwanted 4-cycles. By a similar argument, there is no path of length 2 between Vx and Vx-1 (other than the new one through y), so we can add vertex z with edges [z, Vx-1 ] and [z, vxJ, creating only the 4-cycle 22

PAGE 30

desired, Vx-IYVxZ. From this point on, continue as before, building the necessary new 4-cycles from already existing edges by adding two new vertices each time. Continuing in this manner until all k 4-cycles have been completed yields a graph H such that Although e( G) = 2k :::0: 26.( G) is a necessary condition for any tree to be a (2)-neighborhood graph, it is not a sufficient condition, as the tree G in Figure 2.6 illustrates. That graph is the smallest tree that is not a caterpillar, and we refer to it as NC7 Theorem 9 The tree NC7 is not a (2)-neighborhood graph. Proof: Let NC7 be labelled as in Figure 2.6. Suppose there exists a graph H such that N2(H) = NC7 Then vertex e must be on three distinct 4-cycles in H, no two of which share an edge. This is because if e is on two 4-cycles that share two edges in H, N2 (H) contains a triangle (a contradiction), and if e is on two 4-cycles that share exactly one edge in H, then N2 (H) contains a path of length 2 that does not include vertex e (also a contradiction). However, if in H vertex e is on 3 distinct 4-cycles, no two of which share an edge, H must consist of at least 10 vertices. We conclude that no graph H exists such that N2(H) = NC7 23

PAGE 31

a b c d e f g Figure 2.6:Although tree NC7 satisfies e(NC7 ) = 2k 2: 2!:J.(NC7 ), NC7 is not a (2)-neighborhood graph. The argument in the proof of Theorem 9 leads to an infinite family of trees that are not (2)-neighborhood graphs. If we append at vertex e paths of length one and/or two to NC7 then the resulting tree is not a (2)-neighborhood graph. This result follows from precisely the same type of argument as in the proof. There are, however, some trees which are not caterpillars which are (2)neighborhood graphs, as we discuss next. We conclude that no forbidden subgraph characterizations are available in classifying those graphs which are (2)neighborhood graphs, since every tree that is not a caterpillar has N C7 as an induced subgraph. Given any caterpillar G satisfying e(G) = 2k 2: 2!:J.(G), we can create larger trees which have Gas a subgraph and are (2)-neighborhood graphs. Lemma 2 Let G be a caterpillar, and suppose G = N2(H) for some graph H. Then if [x, y] E E(H), we can create a tree G', consisting of G with two new 24

PAGE 32

pendant vertices, one adjacent to x and one adjacent to y, such that G' is a (2)-neighborhood graph. In fact G' = N2(H'), where H' isH plus a new 4-cycle appended to edge [x, y]. Proof: Suppose G = N2(H) is a caterpillar, and [x, y] E E(H). We create graph H' as follows. Begin with graph H. Add vertices x' and y' to H, with edges [x, y'], [y', x'], and [x', y]. Since [x, y] E E(H), we have created the 4-cycle xy'x'y without making any other changes to H. Then G' = N2(H') is simply G plus two new pendant vertices x' and y', adjacent to x and y respectively. We illustrate the use of Lemma 2 with an example in Figure 2.7, and give a sufficient condition for a tree to be a (2)-neighborhood graph in Lemma 3. Lemma 3 Let T be a tree. If there exists a pair of vertices x andy in T meeting the conditions below, then T is a (2)-neighborhood graph. 1. Vertices x and y are pendant in T with respective neighbors x' andy', x' f y'. 2. There exists a graph H' such that N2(H') = T' and [x', y'] E E(H'), where T'=T-{x,y}. Proof: This follows from Lemma 2. I 25 I

PAGE 33

N2 (H)= G: N2 (If')= G' 1 2 6 7 9 11 1 2 6 7 9 11 11\ I l 8 10 3 4 5 8 10 3 4 5 q p If: 4 }{': 4 1 11 11 6 10 9 9 5 5 Figure 2.7: We illustrate the use of Lemma 2 by choosing an edge in H (in this case, edge [2,8}), and add 4-cycle 2pq8 to H to create H'. This gives tree G' = N2(H'), which has caterpillar G as a generated subgraph. The next class of trees we consider are the balanced binary trees, where all leaves are at the same level, and every internal vertex has two children. We use Lemma 3 to show that all balanced binary trees are (2)-neighborhood graphs. Lemma 4 The balanced binary tree on 31 vertices, B31, is a (2)-neighborhood graph. Proof: We begin with the caterpillar shown in bold in Figure 2.8; call this caterpillar G. We have e(G) = 2k 2t..(G), so we know G is a (2)-neighborhood 26

PAGE 34

B 31: (Gin bold) 1 10 16 17 24 25 26 27 28 29 30 31 22 23 15 9 H: 15 Figure 2.8: Graph G {the caterpillar in bold} is a subgraph of B31, and N2(H) =G. graph, and certainly G is a subgraph of B31 (as depicted in the figure). We use G and the lemmas to show that B31 is a (2)-neighborhood graph. We find H such that N2(H) = G, with the added property that H contains edges [1,9], [10,15], [11,14], and [12,13] (see Figure 2.8). Using H and the lemmas, we can create a graph H' such that N2(H') = B31 and H' contains edges [1,9], [10,15], [16,23], [17,22], [24,31], [25,30], [26,29], and [27,28]. We accomplish this by appending 27

PAGE 35

4-cycles to existing edges in H. The graph H' consists of H plus the following 4-cycles: < 12, 13, 18,21 >, < 12, 13, 19,20 >, < 11, 14, 16,23 >, < 11, 14, 17,22 > < 21, 18, 31,24 >, < 21, 18, 30,25 >, < 20, 19, 29,26 >, and < 20, 19, 28,27 >. Theorem 10 All balanced binary trees En on n = 2k -1 ::?: 7 vertices are (2) neighborhood graphs. Proof: We begin by considering the three smallest balanced binary trees. P3 is the smallest, and as noted earlier is not a (2)-neighborhood graph. The next balanced binary tree E7 is on 7 vertices and is pictured in Figure 2.9. E7 is a caterpillar satisfying e(B7 ) = 2k ;:::: 2f'.::.(E7 ), so B7 is a (2)-neighborhood graph by Theorem 8. The next En we must consider is E15, which is shown in Figure 2.9 with a graph H such that B15 = N2(H), so B15 is a (2)-neighborhood graph. For k ::?: 5 we proceed using induction on k. We claim: Given a balanced binary tree B2'-1 with k ::?: 5, there exists a graph H such that N2(H) = B2._1 and there is an edge in H between every pair of "mirror image" leaves in B2'-l (Note : we consider the graph to be drawn in the standard fashion as depicted in Figures 11 and 12 and can consequently pair each leaf with its reflection in the vertical line through the root vertex.) See Lemma 4 for the base case, k = 5, E31 Suppose for every k with 5 < k < n, there exists a graph H satisfying the conditions just listed. Consider B2n-1 It 28

PAGE 36

B,: B15 ; N2 (H): H: I 2 3 8 9 IO II 12 13 14 15 Figure 2.9: B7 is a (2)-neighborhood graph, since it satisfies Theorem 8, and B15 is a (2)-neighborhood graph, since B15 = N2(H). has 2n-l leaves. Label them and their neighbors as shown in Figure 2.10. Note that ( x 1><1 y) is the parent of leaves x and y. Remove vertices 1, 2, ... 2n-2 1, 2n-2 2n-2*, 2n-2 -1*, ... 2*, and h. We now have B2n-l_1 a balanced binary tree whose leaves are labelled (11><1 2), (3 1><1 4), ... (2n-2 -1 1><1 2n-2), (2n-2 -1 1><1 2n-2)*, ... (3 1><1 4)*, and (1 1><1 2)* By induction, we can create graph H such that N2(H) = B2n-1_1 and H contains edges [(11><1 2), (11><1 2)*], [(3 1><14), (3 1><1 4)*], ... and [(2n-2-11><1 2n-2), (2n-2-1 N 29

PAGE 37

(1 l> and < (1 N 2), (1 N 2)*, 2, 2* >; to edge [(3 N 4), (3 N 4)*] in H we append 4-cycles < (3 N 4), (3 N 4)*, 3, 3* > and < (3 N 4), (3 N 4)*, 4, 4* >; ... ; and to edge [(2n-z1 N 2n-2), (2n-z1 N 2n-2)*] in H we append 4-cycles Nz(H') = B2n_1 and H' contains edges [1, h], [2, 2*], ... [2n-z, 2n-z*], as desired The work presented in this chapter just begins the effort of determining classes of graphs which are or are not (2)-neighborhood graphs. A necessary and sufficient condition for a tree to be a (2)-neighborhood graph remains elusive. We have not yet begun to study the possibilities for graphs with triangles, since the 30

PAGE 38

triangle-free case has been so interesting. Another as yet untouched question is "which graphs are [2]-neighborhood graphs?" 31

PAGE 39

3. Interval p-Neighborhood Graphs 3.1 Introduction In this chapter we consider the following question: given a graph G, what con ditions are necessary and sufficient for the p-neighborhood graph of G to be an interval graph? This question generalizes one posed by Raychaudhuri and Roberts [28] and explored by Lundgren, Rasmussen, and Maybee [24], who explored the case p = 1. We focus on the case p = 2. We consider the 2-open instance in Section 3.2, giving a sufficient condition for a chordal graph to have an inter val (2)-neighborhood graph. In Section 3.3, the 2-closed instance is examined, and we prove that the [2]-neighborhood graph of an interval graph is interval. The definition that follows is of use in both of those sections. A family of sets S = S1 S2 Sr of vertices of G is called a (p)-neighborhood cover of G if the following condition is satisfied: Vertices i, j E Sm for some m if and only if IN(i) n N(j)l 2: p. The definition is similar for the [p]-neighborhood cover of G. Essentially, a (p)-neighborhood cover of G is an edge-clique cover of Np(G), as the example that follows illustrates. 32

PAGE 40

Example 3 For graph G depicted in Figure 3.1, the following sets form a (2)neighborhood cover: { v, x }, {a, w }, {b, w }, {a, x }, {a, b }, and {x, y, z }. We see from the figure that this family of sets also forms an edge-clique cover of N2(G). G: N2(G): X Ltiry z b X a y w v a z v Figure 3.1: A graph G and its (2)-neighborhood graph. 3.2 Which graphs have interval (2)-neighborhood graphs? We begin by presenting three more examples. Consider the graphs in Figure 3.2; we have G1 a graph which is not interval, whose (2)-neighborhood graph is interval; graph G2 is not interval and N2 ( G2 ) is not interval; lastly we have interval graph G3 whose (2)-neighborhood graph is not interval. We see from these examples that whether or not N2 (G) is interval is not dependent upon G being interval. For this reason we seek to identify which interval graphs have interval (2)-neighborhood graphs. By Fulkerson and Gross [12], we know G is an interval graph if and only if the maximal cliques of G can be consecutively ranked. Hence, N2 ( G) is an interval 33

PAGE 41

NOT INTERVAL INTERVAL G, : NOT INTERVAL NOT INTERVAL INTERVAL NOT INTERVAL Figure 3.2: Three graphs and their (2}-neighborhood graphs. graph if and only if its maximal cliques can be consecutively ranked. That is, there exists an ordering of the maximal cliques C; of N2 (G) such that if vertex X is in cliques Ck and Ci then X is in every clique between Ck and Cj in the ranking. Proposition 3 Np(G) is interval if and only if there exists a (p)-neighborhood cover of G with a consecutive ranking. Proof: If Np( G) is an interval graph, then there is a consecutive ranking of 34

PAGE 42

its maximal cliques. These maximal cliques form a (p)-neighborhood cover of G. Conversely, let S1o ... Sr be a consecutively ranked (p)-neighborhood cover of G. Suppose vertex x E S;, ... Sj and x rf. Sk, for k < i, or for k > j. Let Ix be the interval [i, j] on the real line. We show that Nv( G) is the intersection graph of these intervals Ix. For two vertices x andy in Np(G), we know Ix n Iy is nonempty if and only if there exists a set Sq such that x, y E Sq if and only if [x,y] E E(Np(G)). Hence Np(G) is an interval graph. The difficulty lies in actually finding a (p)-neighborhood cover of a graph G with a consecutive ranking. If we can find one that corresponds to the maximal cliques of Np(G), that is even better. In studying the case p = 1, the authors of [20] identified a family of sets that not only formed a (I)-neighborhood cover of a given interval graph G, but actually corresponded to the maximal cliques of N1 (G). They concluded that if G is interval, then N1 (G) is interval if and only if the family has a consecutive ranking. In that case, the nonsimplicial vertices of G, i.e., those vertices whose neighborhoods are not Cliques, played a crucial role in identifying the collection of sets. Similarly in the case p = 2, we seek a (2)-neighborhood cover of G that has a consecutive ranking. In fact, we hope to find one that consists of the maximal cliques of N2(G). If such a cover has a consecutive ranking, we can conclude that N2 ( G) is an interval graph. In this 35

PAGE 43

case we believe that the nonsimplicial edges of G, i.e., those edges in G that are contained in more than one maximal clique of G will be very useful in finding such a cover of G. This notion is the natural generalization of work done in the case p = 1 [20], where nonsimplicial vertices were used. We can partition the nonsimplicial edges of any graph G into three types: Type 1: nonsimplicial edge ei is contained only in cliques of size 2': 4, Type 2: nonsirnplicial edge ei is contained only in cliques of size 3, and Type 3: nonsirnplicial edge ei is contained in both cliques of size 3 and cliques of size 2': 4. We use the nonsirnplicial edges of a chordal graph G to construct a (2) neighborhood cover T of G. Let e1 e2 ... ek be the nonsirnplicial edges of G. For each nonsimplicial ei, construct the set(s) as follows: If ei is Type 1, then Ti = N[ei] (call this a Type 1 set), If ei is Type 2, then Ti, = N(ei) (call this a Type 2a set) and Si, = {ei} (a Type 2b set), and If ei is Type 3, then Ti, = U{Cj I ei E cj, ICjl 2': 4} (a Type 3a set), and Ti, = N(ei) (a Type 3b set). We must add one last type of set, one that is not related to nonsimplicial edges. 36

PAGE 44

For every maximal clique Cj in G where ICjl 2: 4 and Cj has no nonsimplicial edges, let Cj E T; call Cj a Type 4 set. Theorem 11 Let G be a connected chordal graph. The family of sets T just described forms a (2)-neighborhood cover of G. Proof: We must show: p, q E n for some k if and only if p and q have at least 2 common neighbors in G. ( =>) Let p, q E Tk for some k. If Tk is a clique of size at least four with no nonsimplicial edges, then p and q have at least two common neighbors in G in that clique. Otherwise, Tk is associated with some nonsimplicial edge ek. Case i: Edge ek is Type 1. Then ek is contained only in cliques of size at least 4, Tk = N[ek], and p and q have at least two common neighbors in G. Case ii: Edge ek is Type 2. Then ek is only contained in cliques of size 3. It is possible that [p, q] = ek. If this is the case, then [p, q] is contained in more than one maximal clique (since ek is nonsimplicial), which implies p and q have at least 2 common neighbors. Otherwise p, q E Tk = N(ek), so two common neighbors of p and q are the endpoints of edge ek. Case iii: Edge ek is Type 3. Then ek is contained both in cliques of size at least 4 and in cliques of size 3. Then either (1) Tk = u{Cj I ekE cj, ICjl 2: 4}, or 37

PAGE 45

(2) Tk = N(ek)-If (1) is true, then p or q (perhaps both) could be an endpoint of ek; whether or not this happens, p and q have at least two common neighbors. If (2) is true, then the endpoints of edge ek are two common neighbors of p and q. We conclude that p, q E Tk for some k implies p and q have at least two common neighbors in G. ( {=) Assume p and q have at least two common neighbors a and bin G. Then paqb is a 4-cycle in G. G chordal implies [a, b] E E(G) or [p, q] E E(G), perhaps both. (1) [a, b] E E(G) and [a, b] nonsimplicial implies p, q E Tk for Tk associated with edge [a, b], no matter what type of nonsimplicial edge [a, b] is. (2) [a, b] E E( G) and [a, b] simplicial implies [a, b] is in exactly one maximal clique in G, which implies [p, q] E E(G). Then abpq is contained in some maximal clique in G (just one, since [a, b] is simplicial). The maximal clique containing abpq either has a nonsimplicial edge or it doesn't. If doesn't, then p and q appear together in a Type 4 set, Tk Assume the maximal clique containing abpq has a nonsimplicial edge ek. Edge [a, b] simplicial implies [a, b] =f. ek. Edge ek is of either Type 1 or Type 3, and in either case p and q are both in a set Tk associated with edge ek. 38

PAGE 46

(3) Suppose [a, b] E(G). Then certainly [p, q] E E(G). In fact, [p, q] is nonsimplicial, since [a, b] E(G). Then p and q appear together in some set Tk associated with edge [p, q]: Tk is of Type 1 if [p, q] is Type 1, Tk is of Type 2b if [p, q] is Type 2, and Tk is of Type 3a if [p, q] is Type 3. We conclude that p, q E Tk for some k jf and only if p and q have at least two common neighbors in G. The graph G of Figure 3.3 convinces us that chordality is required in the theorem. We have G, a non-chordal graph with no nonsimplicial edges and no cliques of size at least 4, hence T = 0. However, N2(G) is not an empty graph; thus Tis not a (2)-neighborhood cover of G. G: N2(G): X Figure 3.3: G is not chordal, and T = 0 does not form a (2)-neighborhood cover of G. Corollary 1 If G is chordal and T has a consecutive ranking, then N2 ( G) is an interval graph. 39

PAGE 47

Example 4 In the figure below, we have a chordal graph, G, with nonsimplicial edges [b, h] (Type 1), [e, g] (Type 2), and [a, i] (Type 3). Because of edge [b, h], we have {a, b, c, g, h, i} E T. Due to edge [e, g], we have {d, !}, { e, g} E T, and edge [a, i] causes {a, b, h, i}, {b,j, h} E T. Hence T = {{d,f},{e,g},{a,b,c,g,h,i},{a,b,h,i},{b,j,h}}. The listing given for Tis consecutively ranked, thus N2 ( G) is an interval graph. I Graph G of Figure 3.1 (see Example 3) serves as a counterexample to the converse of Corollary 1. We see this by examining Example 3; the (2)-neighborhood cover of chordal graph G listed is precisely the family of sets T which come from the nonsimplicial edges of G. We see that these sets have no consecutive ranking (check {a, b}, {b, w }, {a, w} ). However N2(G) is an interval graph. The problem is that the sets T do not correspond in this case to the maximal cliques of G. In the case p = 1, the analogous collection of sets (based on nonsimplicial vertices) worked for both necessity and sufficiency when G was an interval graph. However, for the case p = 2, Example 2 (where G is interval) convinces us that our collection T needs to be altered to get a necessary and sufficient condition. We 40

PAGE 48

will find in Chapter 4 that it is useful to restrict G to being an interval graph, so that we may make use of the consecutive ranking of G's maximal cliques. The exact altered family of sets is discussed in Chapter 4. 3.3 Interval graphs have interval [2]-neighborhood graphs. We now consider the closed case. The instance p = 1 was explored in [27], where the author proved that the square (or closed neighborhood graph) of an interval graph is interval. In this section, we show that the [2]-neighborhood graph of an interval graph is interval by proving that every interval graph has a [2]-neighborhood cover with a consecutive ranking. If G is an interval graph with consecutively ranked distinct maximal cliques c1, c2, ... ck, define sij, where i::; j, to be the set ci u ci+1 u ... u cj-1 u cj. Lemma 5 Suppose G is an interval graph with consecutively ranked maximal cliques Cr, C 2 ... Ck, then Sij is a clique in N2[G] if and only if Ci n Ci+1 n n Cj 2': 2. Proof: Clearly Ci n Ci+l n n Cj 2': 2 implies Sij is a clique in N2[G], so assume Sij is a clique in N2[G]. Let x E Ci Ci+1 and let z E Cj-Cj-1 Observe x f:. Cj and z f:. Ci since the cliques Ci are consecutively ranked. Since Sij is a clique in N2[G], [x, z] E E(N2[G]). Thus, there exist vertices a and b such that 41

PAGE 49

x, z .E N[a] n N[b]. Then x Ci+1 implies a E Cp for some p ::; i and z c1 _1 implies a E Cq for some q;::: j. Then since C1 C2 ... Ck is a consecutive ranking, we have a E C1 for all p :S l :S q. Similarly, we have b E Cm for all u ::; m ::; v, for some integers u and v, where u :S i, v ;::: j. Hence a, bE C; n C;+J n n C1 If we take all sets S;1 that are cliques in N2[G], we have a [2]-neighborhood cover of G, as the next lemma shows. Lemma 6 For an interval graph G, lets = {Sij 3 IC; n ... n Cjl ;::: 2}. The collectionS is a [2]-neighborhood cover of G. Proof: We must show x andy are in some set S;1 of S if and only if IN[x]nN[y]l ;::: 2 in G. (=?)Let x,y E 8;1 Since S;1 is a clique of N2[G], we know [x,y] E E(N2[G]) (by Lemma 1), and IN[x] n N[y]l 2: 2. IN[x] n N[y]l ;::: 2 in G. If [x,y] E E(G), then x,y E cj for some maximal clique C1 of G and x, y E Sjj. If [x, y] E(G), then x andy have (at least) two common neighbors in G, a and b. Since [x,y] E(G) and G is interval, we have [a, b] E E( G). Thus there exist distinct integers p and q such that x, a, bE Cp andy, a, bE Cq Assume p < q. Then a, bE Cr for all p :S r :S q, so ICP n ... n Cql ;::: 2, and x, y E Spq 42

PAGE 50

Let S' contain only those sets of S which are contained in no other set of S. Then certainly S' is also a [2]-neighborhood cover of G. With the next theorem we see that if G is an interval graph, then these sets have a consecutive ranking. Theorem 12 If G is an interval graph, then the relation on S' determined by Sac < S9 ; if and only if a < g is a consecutive ranking of S'. Proof: Clearly, the ranking orders all the sets in S'. Let X E Sac and X E Sgi for a < g and c < i. Consider sdf E S' for a < d < g and c < I < i. We claim X E sdf Observe that X E cb for some a ::; b::; c and that x E Ch for some g ::; h ::; i. We must show that x E Ce for some d ::; e ::; f. Case i: b ::; h. Since the cliques C; are consecutively ranked we have x E cb n cb+l n n ch. Note that d::; hand b ::; f. These inequalities combined with b::; hand d ::; f imply the existence of an integer e between b and h such that Ce <;;; Sdf. This implies X E Sdf and we are done. Case ii: h < b. Since the cliques C; are consecutively ranked we have Since d < h < b < f and x E Ce for all e between h and b, we have x E Sdf, completing the proof. 43

PAGE 51

Corollary 2 If G is an interval graph, then N2 [ G] is interval. Note that graph G1 of Figure 3.2 is not an interval graph. However, its [2]neighborhood graph (two K4 's sharing exactly one edge not depicted in the figure) is interval. An interesting problem would be to determine what other classes of graphs have interval [2]-neighborhood graphs, as did Lundgren, Merz, and Rasmussen [22] for the case p = 1. 44

PAGE 52

4. Interval Graphs with Interval (p)-Neighborhood Graphs 4.1 Introduction In this chapter, we answer the following question: given an interval graph G, what conditions are necessary and sufficient for the (p)-neighborhood graph of G to be an interval graph? This question arose from one mentioned in [17]: which digraphs have interval p-competition graphs? In Section 3.2 we identified a collection T of sets which corresponded to the nonsimplicial edges of G and proved to be a (2)-neighborhood cover of any chordal graph G. We concluded that if this family of sets has a consecutive ranking, then N2 (G) is an interval graph. It is not true, however, that the identified family of sets is consecutively rankable whenever N2 (G) is interval, as we saw from Example 2. In this chapter, we consider only interval graphs G, so that we may make use of the consecutive ranking of G's maximal cliques. In Section 4.2, we identify a (2)-neighborhood cover denoted S of G, which is an extension of the family T constructed in Section 3.2 and present some examples. We let S' be the set of 45

PAGE 53

elements of S that are contained in no other element of S. We prove that S' actually corresponds to maximal cliques of N2(G) in Section 4.3. This provides us with a necessary and sufficient condition for the (2)-neighborhood graph of interval graph G to be an interval graph. 46

PAGE 54

4.2 Categorization of Nonsimplicial Edges, and Definitions of Sets We now define an extension S of the collection of sets T from Section 3.2 that also serves as a (2)-neighborhood cover of any chordal graph. We categorize the nonsimplicial edges of the chordal graph G into five types (see chart), and note the maximal cliques of size at least 4 of G that have nothing but simplicial edges. Note: we use the term "size" to mean the number of vertices in the set. The difference between S defined in the chart and T defined earlier is the added consideration of a structure we call a 4-fan. We define this structure carefully here to suit our needs. We talk about a "4-fan about nonsimplicial edge [a, b]" only when [a, b] is contained in at least one maximal clique of size 3, {a, b, c}. Since [a, b] is nonsimplicial, we know there exists a vertex d such that dE N([a, b]) and [c, d]
PAGE 55

In summary, a subgraph of interval graph G induced on vertices a, b, c, d, e, and f is a 4-fan about nonsimplicial edge [a, b] hinged at a if {a, b, c} is a maximal clique of G, [e, c], [e, a], [f, d], [f, a] E E(G), possibly [b, f] E E(G), and no other edges are present. The figure below shows two such 4-fans. CLSI8r e a f To construct our collection S of sets, we use the chart that follows. For every nonsimplicial edge of G, we determine its type, and add set(s) to the collection S. For example, if [a, b] is a Type 2 nonsimplicial edge, we add two sets to S, as described in the chart. Note that we also add sets based on maximal cliques of size at least 4 in G which contain only simplicial edges (see section 6 of chart). 48

PAGE 56

Sets of S Type of Nonsimplicial Edge Set Definition Set Type [a, b] contained only in S, N[[a,b]] (1) cliques of size at least 4 (2) [a, b] contained only s" N([a, b]) (2a) in cliques of size 3, and there are no induced 4-fans about [a,b] s" '{a,b} (2b) (3) [a, b] contained only in S" -N([a, b]) (3a) cliques of size 3, and there is at least one 4-fan about [a,b] s" {a, b} (3b) s,, one such (3c) set for each 4-fan about [a, b] hinged at a Sei : \b,p,?},onesuchset (3d) for each 4-fan about [a, b] hinged at b (4) {a, b] is contained in s" the union of all (4a) both cliques of size at least cliques of size at least 4 4 and of size 3, and there containing [a, b] are no 4-fans about [a, b] (induced or otherwise) S" -N([a, bJ) (4b) (5) [a, b] is contained in s., the union of all (5a) both cliques of size at least cliques of size at least 4 4 and of size 3, and there containing [a, b] is at least one 4-fan about [a, b] (perhaps not induced) S" -N(la, b]) (5b) --= {a, c, d}U{ cliques (5cJ of size at least 4 containing [a, b]}-{b},one such set for each 4-fan about [a, b] hinged at a S,, {b,p, q}U{all cliques (5d) of size at least 4 containing [a, b]}-{ a },one such set for each 4-fan about [a, b] hinged at b Se Cm, where Cm is a (6) cliquB""of size at least 4 with no nonsimplicial edges 49 'i

PAGE 57

Theorem 13 If G is a chordal graph, then S forms a (2)-neighborhood cover of G. Proof: This follows from the fact that S is an extension of the family 7 of Section 3.2, which was proved to form a (2)-neighborhood cover of G. It is easy to see from the definitions given in the chart that those sets in S which are not in 7 do form cliques in N2 (G). Corollary 3 LetS'= {SeE SISe is maximal}, and suppose G is chordal. Then S' is a (2)-neighborhood cover of G. 4.3 Main Result In this section, we prove five lemmas, each relating to a different type of non simplicial edge of interval graph G, and a sixth lemma which relates to those maximal cliques of size at least 4 in G which have no nonsimplicial edges. The lemmas convince us that each set of S' defined in SectiGn 4.2 corresponds to a maximal clique of N2(G). We then use the lemmas to show that the family S' forms a (2)-neighborhood cover of G which consists of maximal cliques of N2( G). We conclude with a necessary and sufficient condition for an interval graph G to have an interval (2)-neighborhood graph. 50

PAGE 58

In each of the following lemmas, we will assume the following facts, unless stated otherwise: The graph G is an interval graph. We let the (distinct) consecutively ranked maximal cliques of G be C1 ... Cr, and edge [a, b] is contained in precisely Ci, ... Ci+k-1 Notice that the closed neighborhood of edge [a, b], N[[ bll Uj=i+k-1c a, = J=i J Lemma 7 If edge [a, b] is a Type 1 nonsimplicial edge of G, then the set s. m S' associated with it is a maximal clique in N2 (G). Proof: Suppose s. E S' and s. is associated with nonsimplicial Type 1 edge [a, b]. To show that Se is a maximal clique in N2(G), assume there are two paths of length 2 from vertex x to every vertex inS.; we will show x E s . Assume not. If x It S., then x It N[[a, b]] = u;:::l+k-1Cj. Suppose without loss of generality that x E Cm implies m < i. Consider clique Ci+k-1> the last clique in the consecutive ranking to contain both a and b. Clique Ci+k-1 contains a vertex d such that Ci+k-1 is the first clique in the ranking in which d appears. We know d exists by the maximality of the cliques in the ranking. Case 1: Vertex xis adjacent to neither a nor b. Since there are two paths oflength 2 from x to d, there exist two vertices f and g in V (G) such that [f, d], [f, x], [g, d], and [g, x] E E(G). Note that f oJ a, band g oJ a, b. Then, by the consecutive ranking, f and g appear together in cliques Ci-1> ... Ci+k-1 and possibly more. 51

PAGE 59

Hence [f,g] E E(G), and in fact [f,g] is a nonsimplicial edge of G. Edge [f,g] is not a Type 1 nonsimplicial edge, since N[[f, g]J properly contains N[[a, b]J (we see this from the consecutive ranking of the maximal cliques of G), so [!, g] is Type 4 or Type 5. In either case, the only cliques of size at least 4 containing [j, g] are precisely C;, ... Ci+k-l (by maximality of Se in S'). Thus { x, j, g} is a maximal clique Cp of G, and p < i. Vertex x is not adjacent to any vertex in ur::::+k-1Ci other than j and g. This is because if it were adjacent to some vertex v E u;;:::;+k-ICj, v f. j, g, then { v, j, g, x} would be a clique of G of size :::: 4 containing f and g but not in { ci, ... 'ci+k-1} Every clique in { Ci, ... C;+k-1 } contains a, b, j, and g. Since k 2: 2, there exist vertices p and q in u;;:::;+k-ICj such that p and q are each adjacent to all of X q a, b, j, and g but (p, q] E( G). Thus in G we have g b Recall that there are two paths of length 2 from x to every vertex in N[[a, b]J. This includes f and g; thus there exist j', g' E V(G) such that [x, j'], [f', j], [x,g'], and [g',g] E E(G). Note that [!', g], [g', j], [x, q] E( G), since the addition of any of these edges creates a clique of size at least 4 containing x, j, and g. This also convinces us 52

PAGE 60

that f' # g'. Then the subgraph of G induced on vertices x, j, g, J', g', and q convinces us that G is not an interval graph, a contradiction. !' g' g q Case 2: Vertex x is adjacent to one of a and b. Without loss of generality, suppose [x,a] E E(G). Then there exists g E V(G) such that [x,g],[g,d] E E(G). Recall that Ci+k-1 is the first clique in the ranking in which d appears. Then g and a appear together in at least C;_1 .. Ci+k-1 Hence [g, a] is a nonsimplicial edge, either of Type 4 or 5 (not Type 1, because N[[a, b]] is properly contained in N[[ a, g]]). Thus {a, g, x} is a maximal clique of G. There are two paths of length 2 from x to every vertex in N[[a, b]], including a and g, thus there exist vertices r, s E V(G) such that [x, r], [r, a], [x, s], and [s, g] E E(C). Note that r # s, since this would create clique {a, g, x, r = s }, contradicting the maximality of clique {a,g,x}. For the same reason, [a,s],[r,g] rf. E(G). This leads to the following subgraph in C: We conclude that G is not an interval graph, a contradiction. 53

PAGE 61

d s X r The two cases convince us that x E N[[a, b]J = Se, and hence Se is a maximal clique of N2(G). Lemma 8 If edge [a, b] is a Type 2 nonsimplicial edge of G, then the setB inS' associated with it are maximal cliques in N2 ( G). Proof: Suppose Se E S' and Se is associated with nonsimplicial Type 2 edge [a, b]. To show that Se is a maximal clique in N2(G), assume there are two paths of length 2 from vertex x to every vertex in Se; we will show x E Se Assume not. Case 1: The set Se is a Type (2a) set. Then x if. Se = N([a, b]). Subcase a: Assume x E N[[a, b]J. Recall that x if. N([a, b]); thus without loss of generality, assume x = a. Certainly there is one path of length 2 (through b) from x = a to each vertex in N([a, b]). Suppose vertex c belongs to Ci and no later cliques in the ranking, and let vertex d belong to Ci+k-1 and no prior cliques in the ranking. Note, then, that Ci = {a, b, c}, and Ci+k-1 = {a, b, d}. Since no two vertices in N([a,b]) are adjacent, there exists u E V(G) such that 54

PAGE 62

u E Cm implies m < i and [x, u], [u, c] E E(G), and there exists v E V(G) such b d that v E Cj implies j > i + k-1 and [x, v], [v, c] E E(G). U x:::: a v Vertices v,u '/. N([a,b]), so [v,b], [u,b] '/. E(G). Also, by the consecutive ranking of the maximal cliques of G and the fact that ICql = 3 if a, b E Cq, we know [v, c], [u, d], [u, v] '/. E(G). So we have the following induced subgraph in G: b d 2 u x v This is an induced 4-fan about [a, b], a contradiction. Subcase b: x '/. N[[a, b]]. Let vertex d be in Ci + k-1 and no prior cliques in the ranking. Since there are two paths of length 2 from x to d, d and x have two common neighbors. Any neighbor of d can be adjacent to at most one of a and b (otherwise a and b are contained in a clique of size greater than 3), so at least one of these two common neighbors is neither a nor b; let v be such a common neighbor. Since [d,v] E E(G) and [x,v] E E(G), we have v in each maximal clique C;_1 ... Ci+k-1 and perhaps more. But this contradicts the fact that ICjl = 3, i :S j :S i + k-1, when we consider maximality of the cliques in the ranking. Hence x E N([a, b]) = Se or x E N[[a, b]]. 55

PAGE 63

We conclude that if Se is a Type (2a) set, then x E Se. Case 2: The set Se is a Type (2b) set. Then x rf_ Se ={a, b}. Subcase a: x E N[[a, b]J. Since there are two paths of length 2 from x to a, there exists y E V(G) such that [x, y], [y, a] E E(G), [y, b] rf_ E(G). There are also two paths of length 2 from x to b, so there exists z E V (G) such that [x, z], z, b] E E(G), [z, a] rf_ E(G). Then we have the subgraph shown below, and G is not an interval graph, a contradiction. y z b d Subcase b: x rf_ N[[a, b]J. Without loss of generality, suppose x E Cm implies m < i. Vertex x is adjacent to at most one common neighbor of a and b, c, where c E C;. Suppose without loss of generality [x, b] rf_ E(G). Then, since there are two paths of length 2 from x to a, there exists y E V( G) such that [x,y], [y,a] E E(G). Also, because [a,b] is nonsimplicial, there exists d "I= c E N[[a, b]J, dE Ci+k-l, and [c, d] rf_ E(G). We must add a chord to 4-cycle xyac. Chord [a, x], with or without chord 56

PAGE 64

[y, c] creates a 4-fan about nonsimplicial edge [a, c], causing {a, b, x} to be a set in S', contradicting the maxirnality of the set {a, b} = Se in S'. Thus chord [y,c] E E(G), and chord [a,x] E(G). Thus far, we know of one path oflength 2 from x to b, the path through c, and since [y, b] E(G), we know there exists z E V(G) such that [x, z], [z, b] E E(G). By reasoning similar to above, we have chord [c, z] for 4-cycle xcbz, since [b, x] creates a 4-fan about nonsirnplicial edge [b, c], putting {x, a, b} inS'. Then the subgraph induced on vertices a, b, c, d, y, and z indicates that G is not an interval graph, a contradiction. y z b d If x is not adjacent to any common neighbors of a and b, then a has a neighbor y such that [y, b] E( G) and [x, y], [y, a] E E( G), and b has a neighbor z such that [z,a] E(G) and [x,z], [z,b] E E(G). Then G has a chordless 4-cycle of size 4 or greater (either yabz or yabzx), a contradiction. We conclude that x E Se = {a, b}, and hence Se is a maximal clique in Nz( G) 57

PAGE 65

Lemma 9 If edge [a, b] is a Type 3 nonsimplicial edge of G, then the sets in S' associated with it are maximal cliques in N2 (G). Proof: Suppose Se E S' and Se is associated with nonsimplicial Type 3 edge [a, b]. To show that Se is a maximal clique in N2(G), assume there are two paths of length 2 from vertex x to each vertex in Se; we will show x E Be. Assume not. Case 1: The set Se is a Type (3a) set. Then x tf. Se = N([a, b]). Without loss of a d @ generality, assume there is a 4-fan about edge [a, b] hinged at b. f b g Subcase a: x E N[[a, b]]. Suppose x = b. Then there are two paths of length 2 from x = b to c and two paths of length 2 from x = b to d (via a and f and via a and g, respectively). If c and dare the only neighbors of [a, b], then { c, d, b} is a Type (3d) set, contradicting the maximality of Se = N([a,b]) = {c,d} E S'. Thus a and b have another common neighbor h. Since [h, g] would create the chordless 4-cycle hgda and [h, f] would create the chordless 4-cycle hfca, we know [h, g], [h, f] tf. E(G). Thus there exists y E V(G) such that [b,y],[y,h] E E(G). Edge [a,y] tf. E(G), since if it were, we would have {a, b, h, y} contained in some clique of G, contradicting the fact that [a, b] is a Type 3 nonsimplicial edge. Then we have NC7 as an 58

PAGE 66

induced subgraph of G (on vertices a,c,d,h,f,g, andy), contradicting the fact that G is an interval graph. _j_ g d a h y Now suppose x = a. Since there are two paths of length 2 from x to d and two paths of length 2 from x to c, we know there exists y E V (G) such that [c, y], [y, a] E E(G). The addition of edge [b, y] forces [a, b] into a clique of size greater than 3, so [b, y] rf. E(G). Then we have the following subgraph induced on vertices a, b, c, d, J, and y, convincing us that G is not interval. y f b d Subca,e b: x rf. N[[a, b]J. Suppose without loss of generality that x E Cm implies m < i. Let {a, b, c} = Ci, and {a, b, d} = Ci+t Since there are two paths of length 2 from x to d, d and x have two common neighbors, one of which, call it y, is neither a nor b. Thus [x, y], [y, d] E E(G). By the consecutive ranking of the cliques of G, y =c. However, this contradicts the fact that [a, b] is contained only in cliques of size 3, as {a, b, c, d} becomes a clique of G. 59

PAGE 67

We conclude from Case 1 that Se is not a Type (3a) set. Case 2: The set Se is a Type (3b) set. Since the reasoning used in Case 2 of the proof of Lemma 2 did not rely upon the fact that there were no 4-fans about [a, b], we may use the same arguments here. We conclude that Se cannot possibly be a Type (3b) set. Case 3: The set Se is a Type (3c) set. Suppose Se corresponds to the 4-fan about b d [a, b] hinged at a showll.. below. Then x rf. Se = {a, c, d}. f a g Subcase a: x E N[[a,b]]. Then [x,c],[x,d] rf. E(G). Thus there exists y E V(G) such that y rf. N[[a, b]], [x, y], [y, a] E E(G), and thus [y, b] rf. E(G). Then we have NC7 as an induced subgraph of G (on vertices b, c, d, x, f, g, and y), contradicting the fact that G is an interval graph. Subcase b: x rf. N[[a, b]]. Suppose that x E Cm implies m < i, and let Cp be the last clique in the ranking in which vertex x appears. Suppose also that cj = {a,b,c} and ck = {a,b,d}, with j < k. Since X and d have two common neighbors, those neighbors both appear in cliques Cp, ... Ck, and perhaps others. 60

PAGE 68

This includes Cj, so those two common neighbors must be a and b, contradicting x !/:. N[[a, bjj. We conclude that Se is not a Type (3c) set. Case 4: The set Se is a Type (3d) set. Precisely those arguments used in Case 3 of this proof (with a's and b's interchanged) convince us that Se is not a Type (3d) set. The four cases presented convince us that x E Se, and therefore Se IS a maximal clique in N2 (G). \ Lemma 10 If edge [a, b] is a Type 4 nonsimplicial edge of G, then the sets inS' associated with it are maximal cliques in N2 (G). Proof: Suppose Se E S' and Se is associated with nonsimplicial Type 4 edge [a, b]. To show that Se is a maximal clique in N2(G), assume there are two paths of length 2 from x to every vertex in Se; we will show x E Se. Assume not. Case 1: The set Se is a Type ( 4a) set. Then xis not in Se, the union of all cliques of size at least 4 containing [a, b]. Subcase a: x E N[[a, b]]. Note x =f a, b, since a, b E Se. Then {x, a, b} is a maximal clique of G, and hence x has no neighbors in N([a, b]). We see that there are two paths of length 2 from x to every vertex in Se -{a, b} (one path through 61

PAGE 69

a and one path through b). Thus x must have two paths of length 2 to each of a and b. We have one path of length 2 from vertex x to b through vertex a, and we need another. Hence there exists v
PAGE 70

If n 2: 2, then the arguments used for a Type (1) set (see proof of Lemma 1) convince us that G is not interval, a contradiction. We conclude that Se is not a Type (4a) set. We must consider the instance where n = 1. Suppose {a, b, g, h} <;; C;, and cliques C;+l, ... Ci+k-l are of size 3. Note that n = 1 implies Se = C;. Since x f/c N[[a, b]], without loss of generality suppose [x, b] f/c E(G). If xis adjacent to 3 or more members of C;{b}, then we contradict the I maximality of C; = S e as a set in S', as { x} U C; is contained in some set of S' associated with a different nonsimplicial edge of G. If x is adjacent to exactly two members p and q of C; { b}, then there exist p' and q' E V(G) such that [x,p'], [p',p], [x, q'], [q', q] E E(G). Note that [p', q], [q', p] rt E( G), since this would create a set inS' associated with nonsimplicial edge [p, q] that contains both x and C;, a contradiction. This also explains why p' # q'. Then the subgraph induced on x,p,q,p',q', and b, shown here contradicts the fact that G is an interval graph. Suppose xis adjacent to exactly one member of C;. If xis adjacent to a, we know of one path of length 2 from x to b (through a), and we know there exists b' E V(G) such that [x, b'], [b', b] E E(G). Since [x, b] f/c E(G), we know [b', a] E E(G), otherwise we have a chordless 4-cycle xabb'. Because 63

PAGE 71

!' g' g q the maximal clique containing {a, b', x} occurs before Ci in the consecutive ranking of G's maximal cliques, we know {a, b, b'} <;; Ci, but this contradicts the fact that xis adjacent to only one member of Ci (recall [x, b'J E E(G)). We conclude that [x,a] E(G). It remains to consider the case that x's one neighbor in Ci, g, is neither a nor b. Note that a and b have no common neighbors that are neighbors of x other than g, by consecutive ranking and the fact that C; is the first clique in the ranking to contain both a and b. Then there exists b' E V (G) such that [x,b'], [b',b] E E(G). We know [b',g] E E(G), otherwise we have chordless 4-cycle xb'bg. Also, there exists a' E V(G) such th11t [x,a'], [a',a] E E(G), and we know [a',g] E E(G), otherwise we have chordless 4-cycle xa'ag. From the above, we know [a', b], [b', a] E( G). Let Ci+1 = {a, b, c }. Then the graph induced on vertices a', a, c, b, b', and g indicates that G is not an interval graph, a contradiction. 64

PAGE 72

a' b' b c If x is adjacent to no members of Ci, then there exist a', b' E V(G) such that [x, a'], [a', a], [x, b'J, [b', b] E E(G). Notice that a and b have no common neighbor that is adjacent to X, since Ci is the first clique in the ranking to contain both a and b. Hence [a'b], [b', a] ji! E(G). When we consider the graph induced on vertices x, a', a, b, and b', we see that we have chordless 4-cycle a'abb' if [a', b'J E E(G) and chordless 5-cycle xa'abb' otherwise. Both possibilities contradict the fact that G is an interval graph. Subcases a and b convince us that x E Se or Se is not a Type ( 4a) set. Case 2: The set Se is a Type (4b) set. Then x ji! Se = N([a,b]). Subcase a: x E N[[a, b]J. Without loss of generality suppose x = a. It is clear that there are at least two paths of length 2 from x = a to any vertex in a clique of size at least 4 containing a and b. Let { d, a, b} be a maximal clique of G. There is a path of length 2 from x to d through b, but there has to be another such path. Hence there exists v E V(G) such that [x,v], [v,d] E E(G). This 65

PAGE 73

creates a 4-fan about edge [a, b], a contradiction. We conclude that x rt N[[a, b]J or x E S, = N([a, b]). Subcase b: x rt N[[a, b]]. Again, suppose x E Cm implies m < i. Suppose [a, b] is contained in exactly n maximal cliques of size at least 4. By the same argument as in Case 1, Subcase b of this proof, we know these n maximal cliques occur consecutively and at the beginning of the list Ci, ... Ci+k-l Thus Ci+n is the first maximal clique in the ranking that contains both a and b and is of size 3. Let Ci+n = {a, b, c}. Since x and c have two common neighbors, and since Ci+n is the first clique in the ranking in which c appears (by maximality of cliques in the ranking), those two common neighbors must be in Ci+n, and therefore must be a and b. This contradicts the fact that x rt S, = N([a, b]). We conclude from the two subcases that x E Se or S, is not a Type (4b) set. Cases 1 and 2 convince us that x E S" and thus S, is a maximal clique in Lemma 11 If edge [a, b] is a Type 5 nonsimplicial edge of G, then the sets inS' associated with it are maximal cliques in N2 (G). Proof: Suppose S, E S' and S, is associated with nonsimplicial Type 5 edge [a, b]. To show that S, is a maximal clique in N2(G), assume there are two paths of length 2 from vertex x to every vertex in S,; we will show x E S,. Assume not. 66

PAGE 74

Case 1: The set Se is a Type (5a) set. Then Se is the union of all cliques of size at least 4 containing edge [a, b], and x f:. Se. Subcase a: x E N[[a, b]J. Then {a, b, x} is a maximal clique of G, and x has no neighbors in N([a, b]). We can easily identify two paths of length 2 from x to every vertex in Se -{a, b}, one through a and one through b. We consider the fact that there are two paths of length 2 from x to b. We find one such path through a, and conclude that there exists v E V(G) such that [x, v], [v, b] E E(G). Similarly, there are two paths of length 2 from x to a, and since [v, a] if: E(G), there exists y E V(G) such that [x,y], [y,a] E E(G), and [y,b] if: E(G). Let q be some neighbor of [a, b] other than x. Then [q, x] if: E(G), and the subgraph of G induced on vertices a, b, x, y, v, and q indicates that G is not an interval graph, a contradiction. y q b v Subcase b: x if: N[[a, b]]. Again suppose x E Cm implies m < i. As in Lemma 4, Case 1, Subcase b and Lemma 4, Case 2, Subcase b, the cliques of size at least 67

PAGE 75

4 containing [a, b] occur consecutively and at the top of the list Ci, ... Ci+k1 Again, if [a, b] is contained in at least two cliques of size at least 4, then the argument in the proof of Lemma 1 convinces us that G is not interval. It remains to consider the case that [a, b] is contained in exactly one maximal clique of size at least 4 in G. Then Se = Ci 2 {a, b, p, q }. The same argument as was used in the proof for set Type (4a) (Lemma 4, Case 1, Subcase b, n = 1) is appropriate here, and convinces us that G is not interval. The subcases convince us that Se is not a Type (5a) set. Case 2: The set Se is a Type (5b) set. Then x Se = N([a,b]). Subcase a: x E N[[a, b]J, without loss of generality x = a. We claim [a, b] is in at most two maximal cliques of size 3. Suppose not. Suppose Cu = {a, b, c}, Cv = {a,b,d}, and Cw = {a,b,J} are maximal cliques of G. Notice that i :'0 u, v, w :'0 i + k 1. Suppose without loss of generality that i :'0 u < v < w :'0 i + k 1. Since there are two paths of length 2 from x = a to c, there exists y E V(G) such that y N[[a, b]] and [a, y], [y, c] E E(G). As a result we see that [y, b] tf_ E(G). By maximality of cliques in the ranking, and because y N[[a, b)], one of the following must be true: c E Ci or c E Ci+k-1 (1). Note that [y, d] and [y, f] are not edges of G, since these two edges create 68

PAGE 76

chordless 4-cycles ycbd and ycb f respectively. Thus we can use precisely the same argument as above to conclude that one of the following must be true: dE Ci or dE Ci+k-1 (2), and one of the following must be true: f E Ci or f E Ci+k-1 (3). Clearly it is not possible for (1), (2), and (3) to all hold, so [a, b] is in at most two maximal cliques of size 3 in G. Suppose [a, b] is in exactly one maximal clique of size 3 in G, say {a, b, c}. Again, vertex y exists such that [y, b] E(G), and [y, a], [y, c] E E(G). Then we have a 4-fan about [a, b] hinged at a, and N([a, b]) is properly contained in a set Sq E S', where Sq is a Type (5c) set associated with edge [a, b], contradicting the maximality of Se inS'. Suppose [a, b] is in exactly two maximal cliques of size 3, {a, b, c}, and {a, b, d}. Statements (1) and (2) must hold, so without loss of generality, let Ci = {a,b,c}, and Ci+k1 = {a,b,d}. The arguments just used convince us thatyand z exist such that [a,y], [y,c], [a,z], [z,d] E E(G) and [y,b], [z,b] E(G). We know [y,z] E(G), since y E Cm implies m < i, and z E Cn 69

PAGE 77

implies n > i + k -1. Then we have an (induced) 4-fan about [a, b] on vertices a, b, c, d, y, and z. y x=a z Then the Type (5c) set associated with this 4-fan and edge [a, b] properly contains N([a, b]), a contradiction to the maximality of Se inS'. We conclude that x !/. N[[a, b]J. Subcase b: x !/. N[[a, b]J. Since the argument in the proof of Lemma 4, Case 2, Subcase b does not involve a 4-fan about [a, bJ, we may use the same argument to arrive at a contradiction in this case. We conclude from the two subcases that x E Se or Se is not a Type (5b) set. Case 3: The set Se is a Type (5c) set. Set Se is associated with a 4-fan about [a, b] hinged at a. Suppose the 4-fan is on vertices a, b, c, d, f ,and g, as depicted b d 616 in the figure. f a g Then x !/. Se = {a, c, d} U {all cliques of size at least 4 containing [a, b]}-{b }. At least one of [b,j], [b,g) !/. E(G), say [b,g] !/. E(G). 70

PAGE 78

We claim [d, f] if. E(G). This is because [d,J] E E(G) implies [b, f] E E(G) (otherwise we have chordless 4-cycle bdfc). However, if [d, JJ, [b, JJ E E(G), then Se is properly contained in UCp, where a, b E Cp and ICPI 2: 4, contradicting the maximality of Se inS'. Hence [d, f] if. E(G). Then [c, g] if. E(G), since existence b d of [c, g] would create the chordless 4-cycle bdgc. f a g Subcase a: x E N[[a, b]J. Suppose x = b. Certainly there are two paths of length 2 from x = b to a and two from x = b to any vertex in UCP, where a, b E Cp and ICPI 2: 4. We know of one path of length 2 from x = b to d and one from x to c. There is another path of length 2 from x = b to d, so there exists y E V (G) such that [b, y], [y, d] E E(G). f a g Since G is interval, [a, y] E E(G), otherwise we have the following subgraph in G. 71

PAGE 79

y c a g Thus we have the following subgraph in G. f a g If [b, f] or [y, c] E E( G), then Se is properly contained in UCp, where a, b E Cv and ICvl 4, so [b,J], [y,c] E(G). (Depicted above.) There is another path of length 2 from x = b to c, so there exists z E V (G) such that [b, z], [z, c] E E(G). Consider the subgraph of G induced on vertices a, b, c, d, J, and z. z f a d We know [a, z] E E(G), or else G is not interval. However, [a, z] E E(G) 72

PAGE 80

implies Se is properly contained in UCp, where a, b E Cp and ICPI 4. We conclude that x # b. Suppose x = v, where {a, b, v} is a maximal clique of G, v # c, d. Then [v, d], [v, c] !f. E(G). It is clear that there are two paths of length 2 from x = v to every vertex in Se except a. We know of only one path of length 2 from x = v to a at this point, and that path is through b. Notice that [ v, f], [ v, g] if_ E (G), since existence of these edges would create chordless 4-cycles v fad and vbdg respectively. f a g Then there exists b c d / y E V(G)-{b, c, d,f, g} such that [v, y], [y, a] E E(G). f a g We see that [y,b] !f. E(G), since this would create clique {a,b,v,y}, contradieting the maximality of clique {a, b, v }. Then [b, f] E E( G), since lack of this edge would create induced subgraph NC7 on vertices b, c, d, J, g, v, and y. f a g 73

PAGE 81

But then the set in S associated with the 4-fan about [a, b] hinged at a induced on vertices a, b, d, g, v, and y is { v, d, a} U {UCP, where a, b E Cp and ICPI :::>: 4}, which properly contains S., a contradiction. We conclude that x rf N[[a, b]]. Sub case b: x rf N[[a, b]J. By the definition of a 4-fan, {a, b, d} is a maximal b d @ clique of G; let Cj = {a, b, d}. f a g Suppose without loss of generality that x E Cm implies m < i. By the same reasoning as in the proof of Lemma 4, Case 1, Subcase b, the maximal cliques of G of size :::>: 4 that contain [a, b] occur consecutively and at the beginning of the list Ci, ... Ci+k-t Thus Ci is the first clique in the ranking in which vertex d appears, and i < j i + k 1. Vertices x and d have two common neighbors, since d E Se By the consecutive ranking, those neighbors are a and b. However x rf N[[a, b]], so x can't possibly be adjacent to both a and b. Hence we have a contradiction and conclude that Se is not a Type (5c) set. Case 4: The set Se is a Type (5d) set. Precisely those arguments used in Case 3 of this proof (with a's and b's interchanged) convince us that Se is not a Type (5d) set. 74

PAGE 82

We conclude from Cases 1, 2, 3, and 4 that x E Se and Se is a maximal clique in N2(G). Lemma 12 If a set in S' corre.sponds to a maximal clique of size at least 4 in G that has no nonsimplicial edges, then the set is a maximal clique in N2 (G). Proof: Suppose Cj = Se E S' and Cj is a maximal clique of G of size at least 4 with no nonsimplicial edges. To show that Se is a maximal clique in N2 (G), assume there are two paths of length 2 from vertex x to every vertex in Se; we will show x E Se. Assume not. Also suppose { t, u, v, w} <;; Se. Since Se has no nonsimplicial edges, any vertex not in Se (in particular x) is adjacent to at most one vertex in Se Subcase a: Vertex x is adjacent to one vertex v in Se. There is another path of length 2 from x to u, so there exists a vertex y rf; Se such that [x, y], [y, u] E E(G). But chords [u, x] and/or [y, v] cause edge [u, v] to be nonsimplicial, so we have chordless 4-cycle uyxv in G, contradicting the fact that G is an interval graph. Subcase b: Vertex x is adjacent to no vertex in Se There are two paths of length 2 from x to u, so there exist vertices Y1, Y2 E V (G) such that Y1, Y2 rf; Se and [x,yl],[y 1 ,u],[x,y 2 ],[y 2 ,u] E E(G). Note that [ybv],[y 2,v] rf; E(G), since [u,v] is not nonsimplicial. Hence there exist z 1 z2 E V (G) such that Z1, z2 rf; Se and [x, z1], [z1 v], [x, z 2 ], [z2 v] E E(G). Note, as before that [zb u], [z2 u] rf; E(G), 75

PAGE 83

since [u, v] is not nonsimplicial. Consider the subgraph of G induced on vertices uy2xz1v. We know [y2,zJ] <'/ E(G), since this would create chordless 4-cycle uy2z1 v. But the 5-cycle uy2xz1 v is not chordless, since G is an interval graph. In fact, G interval implies that [x,u], [x,v] E E(G). Then {x,u,v} is a clique ofG, contradicting the fact that [u, v] is not nonsimplicial. Hence x E Se and Se is a maximal clique in N2(G). Theorem 14 The collection of sets S' for a given interval graph G zs a (2 )neighborhood cover of G consisting of maximal cliques of N2 (G). Proof: This theorem follows directly from Lemmas 7 through 12. Corollary 4 An interval gmph G has an interval (2)-neighborhood graph if and only if S' has a consecutive ranking. We can use Corollary 4 to identify a class of interval graphs whose (2)-neighborhood graphs are interval. Corollary 5 If G is an interval graph and the nonsimplicial edges of G are contained only in maximal cliques of size at least 4, then N2(G) is an interval graph. 76

PAGE 84

Proof: Suppose G is an interval graph in which all nonsimplicial edges occur in maximal cliques of size at least 4. Let C1 ... Cr be a consecutive ranking of the maximal cliques of G. If G contains no nonsimplicial edges, then the only elements of S' are those maximal cliques of size at least 4. Certainly S' has a consecutive ranking, and thus (by Corollary 4) N2(G) is an interval graph. Assume G has at least one nonsimplicial edge. Define C ([a, b]) to be the union of those cliques of G which contain nonsimplicial edge [a, b]; then C([a, b]) = N[[a, b]] and this set is the union of some consecutive cliques in the ranking C1, ... Cr. The set S consists of cliques of size at least 4 with no nonsimplicial edges, and the sets C([a, b]) (one such set for every nonsimplicial edge [a, b]). In S', we have only the maximal sets of S; S' is essentially a "collapsed" version of the consecutive ranking C1 ... Ceo so S' certainly has a conseeutive ranking, and N2 (G) is an interval graph. 77

PAGE 85

5. The (2)-Neighborhood Graphs of Interval Graphs Are Weakly Chordal. 5.1 Introduction The necessary and sufficient condition given in Chapter 4 for an interval graph to have an interval (2)-neighborhood graph is a bit unwieldy. We concentrate in this chapter on the properties of interval graphs whose (2)-neighborhood graphs are not interval. We will need the definition that follows. Definition: A graph G is weakly chordal if G contains no chordless cycles of length 5 or greater. Notice that weakly chordal graphs are perfect graphs. 5.2 If G is interval, then N2 ( G) is weakly chordal. Theorem 15 If G is an interval graph, then N2 ( G) is a weakly chordal graph. Proof: Suppose G is an interval graph and N2 ( G) contains the chordless cycle Suppose every pair of consecutive vertices on the cycle v1 v2 ... vk-! vk is adja cent in G. Since G is interval, some of the chords of the cycle are also in E(G). 78

PAGE 86

However, no matter which chords of the cycle are in E(G), some pair of noncon secutive vertices of the cycle ends up diagonally opposed on some 4-cycle of G. This creates a chord in the chordless k-cycle in N2 (G), a contradiction. Hence, there exists some consecutive pair of vertices on the k-cycle, say v1 and v2 that is not adjacent in G. Suppose without loss of generality that C1 C2 ... Cr is a consecutive ranking of the maximal cliques of G in which the maximal cliques containing v1 appear strictly before those containing v2 (recall [ v1 v2 ] r;t E( G)). Since v1 and v 2 are adjacent in N2(G), IN(v1 ) n N(v2)1 ?: 2 in G. Suppose x1 and x2 are both adjacent to v1 and v2 in G. Edge [x1,x2 ] E E(G), since G is interval. Since [v1 vk] E E(N2(G)), IN(vk) n N(v1)1 ?: 2 in G. Notice that vk is not adjacent to both x1 and x2 in G, since if it were, edge [vk, v2 ] would be in N2(G). Thus the maximal cliques containing vertex vk appear either before or after those containing both vertices x1 and x2 in the consecutive ranking. If the maximal cliques of G containing vertex vk appear after those containing both x1 and X2 in the consecutive ranking, then the common neighbors of vertices v1 and Vk (of which v 2 is not one, since [v1 v 2 ] r;t E(G)) are also adjacent to v2. This forces [vk, v2 ] E E(N2(G)), a contradiction. Hence the maximal cliques of G containing 79

PAGE 87

vk all appear before those containing both x1 and x2 in the consecutive ranking. Similar reasoning convinces us that the maximal cliques of G containing v3 all appear after those containing both x1 and x2 in the ranking. Extending the argument, we find that the maximal cliques containing vk-l through Vrkl 2 respectively, appear before those containing both x1 and x2 in '2 T the ranking. Case 1: k is odd. In this case, we find that the maximal cliques containing v3 ... appear after those containing both x1 and x2 However, the maximal cliques of G containing vertex must appear both before and after those containing x1 and x2 in the ranking, a contradiction. We conclude that N2 (G) contains no induced odd cycle of length 5 or greater. Case 2: k is even. Here we find that the maximal cliques of G containing v3 ... v k 2 appear after those containing both x1 and x2 in the ranking. Since the maximal cliques of G containing v k+z appear before those containing x1 and Xz in the rank ing and those containing appear after, we know that" two common neighbors of Vk+z and Vk+l are adjacent to x1 x2 and all of the common neighbors of x1 2 2 and x2 in G. However, this creates unwanted chords (for example [v1, VkH]) in 2 N2(G), a contradiction. We conclude that N2(G) contains no induced even cycle of length 6 or greater. 80

PAGE 88

Hence, if G is an interval graph, N2 (G) is weakly chordal. 5.3 What if N2(G) contains a chordless 4-cycle? Conjecture 1 If G is an interval graph and N2 (G) contains a chord less 4 -cycle, then G contains one of the following as an induced subgraph. Figure 5.1: If N2(G) has a chordless 4-cycle as a generated subgraph, then G has one of the graphs above as a generated subgraph. Beginning of Proof: Suppose abed is a chordless 4-cycle in N2(G). Then a and bare diagonally opposed on some 4-cycle of G. Case I. A 4-cycle in G on which a and b are diagonally opposed is contained in a complete subgraph. Suppose the subgraph of G induced on vertices a, b, x, and 81

PAGE 89

y in G is complete. Since [c, d] is an edge of N2(G), c and d have (at least) two common neighbors in G. The possibilities (without loss of generality) are: (1) c and dare both adjacent in G to a and b, (2) c and d are both adjacent in G to a and x, (3) c and dare both adjacent in G to x and y, ( 4) c and d do not have two common neighbors in the set {a, b, x, y }. Suppose (1) holds. Then [c, d], [c, x], [c, y], [d, x], [d, y] '/:. E( G). This is because any one of these edges would create chord [a,c] or chord [b,d] in N2(G). Since c and a are both adjacent to b in G c and a have no other neighbors in common in G. Similarly, b and d have only one common neighbor in G, vertex a. Thus there exist two other vertices, say v and w, so that [a,v],[d,v],[c,w],[b,w] E E(G). Hence we c a v d X have the following graph as an induced subgraph of G. y Suppose (2) holds. Then we have the graph shown in the figure below as a subgraph of G, and as a result in N2 ( G) we have edge [b, d], a contradiction. 82

PAGE 90

b a c y X d Suppose (3) holds. Then we have the graph shown in the figure below as a subgraph of G, and as a result [a, c], [b, d] E E(N2(G)), a contradiction. a X c b y d Suppose (4) holds. Without loss of generality, there are 3 subcases to consider. (4)[1] c and dare both adjacent to a in G, (4)[2] c and dare both adjacent toxin G, (4)[3] c and d have no common neighbors in the set {a,b,x,y}. We first consider the case (4)[1]. y d X b Let another common neighbor of c and d be labelled v (see the figure above). Note v
PAGE 91

or [c, d] is an edge of G, but not both, since the presence of both in G would produce [a, c] in N2(G). Suppose [a, v] E E(G) and [c, d] .ft E(G). Because band d have a as a common neighborinG, there must be no other vertices to which both band dare adjacent. The same is true for a and c, which are both adjacent to v in G. These two facts force the following nonedges in G: [d, y], [d, x], [b, v], [c, b], [c, x], and [c, y]. The forced nonedges of G are indicated in the figure below with dotted lines. The only remaining possible edges between the vertices mentioned thus far are [y, v], [x, v], and [b, d]. If [b, d] E E(G), then [x, v], [y, v] ft E(G), since these edges would create chordless 4-cycles bdvx and bdvy respectively in G. This would contradict the fact that G is an interval graph. Thus if [b, d] E E( G), we have the following induced subgraph in G. y X b d Because band c have a as a common neighbor, and no other vertices in the set {a, b, c, d, v, x, y} are adjacent to both band c, there exists a vertex q, not in the set 84

PAGE 92

{a, b, c, d, v, x, y} such that [b, q], [c, q] E E( G). There is only one way to consecu tively rank the four maximal cliques of G containing {a, b, x, y}, {a, b, d}, {a, d, v}, and {a, v, c}. In fact, the listing given is the only way to consecutively rank them. Since the ranking is consecutive and [b, q], [c, q] E E(G), q is adjacent to a, d, and v (see the figure below). This forces edges [a, c] and [b, d] in N2(G), a contradiction. We conclude that [b, d] rf. E(G). Thus we have in G the subgraph shown in the figure below, possibly with edge [v, x] or [v, y] (perhaps both). y a d X b If [v, x] is an edge of G and [v, y] is not (see the figure below), then there exists a vertex q that is adjacent to both b and c in G (otherwise they only have a as a common neighbor). b v y X 85

PAGE 93

By consecutive ranking of the maximal cliques of G, q is in a maximal clique of G containing a,x, and v, forcing [a,c] into the edge set of N2(G), a contradiction (see the figure below). y X The same reasoning as above convinces us that it is not possible for [ v, y J to be in the edge set of G if v, x] is not. Can both [v, y] and [v, x] be edges in G? The answer is no. If they both were, then we would have the graph shown in the figure below as an induced subgraph of G. y X Again, the consecutive ranking of the maximal cliques of G is forced to have a maximal clique containing {a, x, y, v} between a maximal clique containing b and one containing c. Vertices b and c must have a common neighbor q that is not in the set {a,b,c,d,v,x,y}. Then the consecutive ranking just mentioned forces 86

PAGE 94

q to be adjacent to a, x, y, and v. Then a and c are both adjacent q and v, a contradiction. The only possibility that remains to be considered in this subcase of (4)[1] in which [a, v] E E(G) and [c, d] E(G) is the one in which neither [v, y] nor [v, x] is in E( G). Thus we have the subgraph shown below induced in G. y X b Let q be adjacent to both a and d, with q {a, b, c, d, v, x, y }. Edges [b, q] and [q,c] in G would force edges [b,d] and [a,c] in N2(G), so neither [b,q] nor [q,c] is an edge in G. Thus there exists another vertex p not in {a, b, c, d, v, x, y, q} that is adjacent to both band c. We must consider the 4-cycle acpb in G. Since G is interval, this 4-cycle must have at least one chord. However, both chords [a, p] and [b, c] force a and c to be diagonally opposed on 4-cycles of G, thus forcing edge [a, c] into N2(G), a contradiction. We conclude that in case (4)[1], it is not the case that [a,v] E E(G) and [c, d] E(G). Recall that it is not possible to have both edges [a, v] and [c, d] in E(G). Thus it remains to consider the case where [c, d] E E(G) and [a, v] r/. E(G). Because a and c are both adjacent to d, the following nonedges are forced: [c, b], [c, x], 87

PAGE 95

and [c, y]. Since band dare both adjacent to a, [b, v], [d, y], and [d, x] are forced nonedges in G (see the figure below). c v X b The edges that we can possibly add are: [v, y], [v, x], and [b, d]. Suppose [b,d] E E(G). Then [v,y], [v,x] E(G), since they create chordless 4-cycles in G. Thus [b, d] E E( G) implies the graph below is an induced subgraph of G. y a c X b d V Now suppose [b, d] E(G). We must explore the possibilities for [v, y] and [v, x]. If we consider the graph below, and the consecutive ranking of the cliques of G, we see that neither [v, y] nor [v, x] is in E( G), since neither c nor d is adjacent to x or y in G. c v 88

PAGE 96

Vertices a and d are both adjacent to vertex c. Let q be another neighbor of a and d, q !f. {a, b, c, d, v, x, y }. The following nonedges are forced: [q, v], [q;c], [q, b]. the only possible edges to consider at this point are [q, x] and [q, y] (see the figure below). c q Suppose [q, x] E E( G) and [q, y] !f. E( G)? Then we are locked into one choice for the consecutive ranking of the maximal cliques of G that contain {a, b, x, y }, {a,x,q}, {a,q,d}, {a,d,c}, and {d,c,v} respectively, as the figure below indi cates. c v q Thus far, We are aware of one common neighbor of b and c, vertex a. No other vertex in the set {a, b, c, d, v, x, y, q} is adjacent to both band c. Let p be a vertex adjacent to both b abd c. Then by the consecutive ranking, p is in a 89

PAGE 97

maximal clique with a, x, and q and in another one with a, q, and d. Then a and c are both adjacent to p and to d, a contradiction. We conclude that it is not the case that [q, x] E E( G) and [q, y] rJ E( G). Suppose we have [q, y] E E(G) and [q, x] rJ E(G). the same argument as directly above leads to a contradiction. It remains to consider the case that both [q,x] and [q,y] E E(G). A look at the figure below convinces us that the only possible ranking of the maximal cliques of G containing {a,b,x,y}, {a,x,y,q}, {a,q,d}, {a,d,c}, and {d,c,v} respectively is in precisely the given order. c v X q Vertices band c have some common neighbor prJ {a, b, c, d, v, x, y, q}. Thus, by consecutive ranking, p is adjacent to a, q, d, x, and y. However, p adjacent to both b and d implies [b, d] E E(N2(G)), a contradiction. We conclude that neither [q, y] nor [q, x] is an edge of G. 90

PAGE 98

c v q Thus the graph shown above is an induced subgraph of G. There must exist a vertex, m {a,b,c,d,v,x,y,q}, that is adjacent to both band c. However, this creates 4-cycle acmb, and both chords [a, m] and [b, c] force [a, c] into the edge set of N2 (G), a contradiction. We conclude that it is not possible to have [b, d] E(G). This concludes subcase (4)[1]. Hence, if the two common neighbors of c and dare a and v, where v {a,b,x,y}, then G has the graph depicted below as an induced subgraph. y a c X b d V This concludes the proof for most of Case I; it remains to consider subcases ( 4)[2] and ( 4)[3], as outlined on page 83 Once these subcases and Case II (no 4-cycle in G on which a and b are diagonally opposed is contained in a complete subgraph) are verified, the conjecture will be proved true. 91

PAGE 99

6. Conclusion There are many directions in which the research discussed here can be taken for future study. We conclude by listing some of those possibilities. As mentioned at the end of Chapter 2, it remains an open problem to fully classify those (triangle-free) graphs which are (2)-neighborhood graphs, and the question for [2]-neighborhood graphs is yet to be considered. The necessary and sufficient condition for an interval graph to have an interval (2)-neighborhood graph given in Chapter 4 can certainly be further explored. It would be nice to find more classes of interval graphs which satisfy the necessary and sufficient condition. To this end, the work begun in Chapter 5 will most likely be helpful. Completion of the proof of Conjecture 1 is an obvious starting point. Future work should also include attempts to generalize other results on neigh borhood graphs to (p)-neighborhood graphs. Some questions to consider are "when is a graph isomorphic to its (p)-neighborhood graph?' and "when is the complement of G isomorphic to Np(G)?" There are many other results for the case p = 1 whose generalizations to larger p would make an interesting study. 92

PAGE 100

References [1] B. D. Acharya and M. N. Vartak. Open neighborhood graphs. Research Report 7, Indian Institute of Technology Dept. of Mathematics, 1973. Bombay400 076, India. [2] C. A. Anderson, L. Langley, J. R. Lundgren, and S. K McKenna, P. A. and Merz. New classes of p-competition graphs and -tolerance competition graphs. Congressus Numerantium, 100:97-107, 1994. [3] J. W. Boland, R. C. Brigham, and R. D. Dutton. The difference between a neighborhood graph and a wheel. Congressus Numerantium, 58:151-156, 1987. [4] J. W. Boland, R. C. Brigham, and R. D. Dutton. Embedding arbitrary graphs in neighborhood graphs. Journal of Combinatorics, Information, and System Sciences, 12:101-112, 1987. [5] R. C. Brigham and R. D. Dutton. A characterization of competition graphs. Discrete Applied Mathematics, 6:315-317, 1983. 93

PAGE 101

[6] R. C. Brigham and R. D. Dutton. On neighborhood graphs. Journal of Combinatorics, Information, and System Sciences, 12:75-85, 1987. [7] R. C. Brigham, F. R. McMorris, and R. P. Vitray. Tolerance competition graphs. Linear Algebra and Its Applications, 217:41, 1995. [8] R. C. Brigham, F. R. McMorris, and R. P. Vitray. Two--tolerance compe tition graphs. Discrete Applied Mathematics, 66(2):101, 1996. [9] J. E. Cohen. Interval graphs and food webs: A finding and a problem. Document 17696-PR, RAND Corporation, 1968. [10] D. C. Fisher, J. R. Lundgren, S. K. Merz, and K. B. Reid. Domination and competition graphs of tournaments. To appear in Journal of Graph Theory, 1996. [11] K. F. Fraughnaugh, J. R. Lundgren, J. S. Maybee, S. K. Merz, and N. J. Pullman. Competition graphs of strongly connected and Hamiltonian di graphs. SIAM Journal on Discrete Mathematics, 8(2):179--185, 1994. [12] D. R. Fulkerson and 0. A. Gross. Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15:835-855, 1965. [13] F. Harary and T. McKee. The square of a chordal graph. Discrete Mathe matics, 128:165-172, 1994. 94

PAGE 102

[14] G. Isaak, S. R. Kim, T. A. McKee, F. R. McMorris, and F. S. Roberts. 2-competition graphs. SIAM Journal on Discrete Mathematics, 5:524-538, 1992. [15] S. Kim. Competition graphs and scientific laws for food webs and other systems. PhD thesis, Rutgers University, 1988. [16] S. R. Kim, T. A. McKee, F. R. McMorris, and F. S. Roberts. p-competition numbers. Discrete Applied Mathematics, 46:87-92, 1993. [17] S. R. Kim, T. A. McKee, F. R. McMorris, and F. S. Roberts. p-competition graphs. Linear Algebra and Its Applications, 217:167-178, 1995. [18] L. Langley, J. R. Lundgren, P. A. McKenna, S. K. Merz, and C. W. Ras mussen. The p-competition graphs of strongly connected and Hamiltonian digraphs. Submitted to Ars Combinatoria, 1995. [19] L. Langley, J. R. Lundgren, and S. K. Merz. The competition graphs of interval digraphs. Congressus Numemntium, 107:37-40, 1995. [20] J. R. Lundgren, J. S. Maybee, and C. W. Rasmussen. An application of gen eralized competition graphs to the channel assignment problem. Congressus Numerantium, 71:217-224, 1990. 95

PAGE 103

[21] .J. R. Lundgren, S. K. Merz, J. S. Maybee, and C. W. Rasmussen. A char acterization of graphs with interval two-step graphs. Linear Algebra and Its Applications, 217:203-223, 1995. [22] J. R. Lundgren, S. K. Merz, and C. W. Rasmussen. A characterization of graphs with interval squares. Congressus Numerantium, 98:132-142, 1993. [23] J. R. Lundgren and C. W. Rasmussen. Two-step graphs of trees. Discrete Mathematics, 119:123--140, 1993. [24] J.R. Lundgren, J.S. Maybee, and C.W. Rasmussen. Interval competition graphs of symmetric digraphs. Discrete Mathematics, 119:113-122, 1993. [25] G. E. Major. p-edge clique coverings of graphs. Masters Thesis, University of Louisville, Louisville, KY, 1990. [26] G. E. Major and F. R. McMorris. p-edge clique coverings of graphs. Con gressus Numerantium, 79:143-145, 1990. [27] A. Raychaudhuri. Intersection assignments, t-colorings, and powers of graphs. PhD thesis, Rutgers University, 1985. [28] A. Raychaudhuri and F. S. Roberts. Generalized competition graphs and their applications. Methods of Operations Research, 49:295-311, 1985. 96

PAGE 104

[29] F. R.. Roberts and J. E. Steif. A characterization of competition graphs of arbitrary digraphs. Discrete Applied Mathematics, 6:323-326, 1983. [30] F. S. Roberts. Discrete Mathematical Models, with Applications to Social, Biological, and Environmental Problems. Prentice Hall, Englewood Cliffs, New Jersey, 1976. [31] F. S. Roberts. Applications of edge coverings by cliques. Discrete Applied Mathematics, 10:93-109, 1985. 97