Citation
Characterizing chordal graphs with chordal two-step graphs

Material Information

Title:
Characterizing chordal graphs with chordal two-step graphs
Creator:
Phelps, Eric Bruce
Publication Date:
Language:
English
Physical Description:
v, 39 leaves : illustrations ; 29 cm

Thesis/Dissertation Information

Degree:
Doctorate ( Master of science)
Degree Grantor:
University of Colorado Denver
Degree Divisions:
Department of Mathematical and Statistical Sciences, CU Denver
Degree Disciplines:
Applied mathematics

Subjects

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

Notes

Bibliography:
Includes bibliographical references.
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, [Department of] Applied Mathematics.
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Eric Bruce Phelps.

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:
26891588 ( OCLC )
ocm26891588
Classification:
LD1190.L622 1992m .P43 ( lcc )

Full Text
CHARACTERIZING CHORDAL GRAPHS WITH
CHORDAL TWO-STEP GRAPHS
by
Eric Bruce Phelps
A. S., Arapahoe Community College, 1989
B. A,, University of Colorado at Denver, 1991
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
1992


This thesis for the Master of Science degree by
Eric Bruce Phelps
has been approved for the
Applied
Mathematics
by
i
I
i


Phelps, Eric Brace (M.S., Applied Mathematics)
Characterizing Chordal Graphs with Chordal Two-Step Graphs
Thesis directed by Professor J. Richard Lundgren
ABSTRACT
Definitions of the 2-Step graph characterization problems are stated,
and a survey of known results is given. Necessary and sufficient conditions for
a chordal graph G to have a chordal 2-Step graph are developed. Some of the
consequences of these conditions are explored.
This abstract accurately represents the content of the candidates
thesis. I recommend its publication.
Signed
J. Richard Lundgren
m


CONTENTS
CHAPTER
1 INTRODUCTION ......................... 1
1.1 Terminology and Notation ................. 1
1.2 The Characterization Problems ............... 4
1.3 Definitions of Graph Classes ................ 6
1.4 Some Known Characterization Results ........... 8
1.4.1 Trees .............................................. 9
1.4.2 Complete and Triangle-Free Graphs .................. 11
1.4.3 A-trees ........................................... 12
1.4.4 Interval Graphs .................................. 13
1.4.5 Unit Interval.................................... 17
2 RESULTS .................................... 19
2.1 Sufficient Conditions ................. 19
2.1.1 Simple Chordal Graphs with Non-chordal 2-Step Graphs 19
2.1.2 R-induced Subgraphs ................... 23
2.1.3 Sufficient Conditions Theorem .............. 26
2.2 Necessary Conditions .................... 27
2.2.1 Basics........................................... 27
2.2.2 Necessary Conditions Theorem .............. 29
2.3 Consequences ......................... 35
BIBLIOGRAPHY ..................................... 38


FIGURES
FIGURE
1 Example of a Graph, and Its 2-Step Graph. .......... 3
2 Some Graphs Which Are Not 2-Step Graphs. ......... 3
3 Example of the Difference Between the Square and the 2-Step. 5
4 Construction of an Induced Graph in a 2-Step Graph. .... 9
5 Graph for Theorem 8 . .................... 10
6 Example of the Three Types of Nonsimplidal Vertices. .... 13
7 Example of the Construction of S'(G). ............. 14
8 Graphs for Lemma 3 . ................................... 17
9 Examples of n-suns. ...................................... 20
10 Examples of Bowties. .................................... 21
11 Examples of Bowties and Their 2-Step Graphs................ 22
12 Graph with Induced Bowtie That Is Not jR-induced. ..... 23
13 Example of the 2-Step graph of an Induced Subgraph......... 24
14 Graph with an R-induced Bowtie............................ 26
15 Graph for P{k).......................................... 29
16 Graph for P(l). .......................................... 30
17 Graph Showing (a2, an) g E(G), ......................... 31
18 Graph Showing (xt,Xi) $ E(G). ................ 32
19 Graph for Case 2. ........................ 34
20 Graph for Case 3............................ 34
V


CHAPTER 1
INTRODUCTION
Chapter 1 reviews the background information used in the charac-
terization theorem given in Chapter 2. In Section 1.1 basic terminology and
usage are defined. Section 1.2 gives the characterization problems. Section 1.3
defines the classes of interest. Section 1.4 is a survey of known results about
the characterization of 2-Step graphs for various classes of graphs.
1.1 Terminology and Notation
A graph G (V,E) is a set V of vertices and a set E of edges
connecting vertices in V. If there is an edge connecting a vertex u to a vertex
u, it is denoted by (u,v) or equivalently (t?,). However,jno multiple edges are
allowed, so each pair of vertices can appear only once in E. A vertex may not
be connected to itself. Two vertices are called adjacent if there is an edge
connecting them. The vertex set of a graph G is denoted V(G), and its edge
set is denoted E(G). An induced subgraph H = (W,F) of the graph G is a
graph where W C F, and the edges in F are the edges in E connecting vertices
in W. A directed graph or digraph D = (F, A) is a set F of vertices and a
set A of arcs connecting vertices in F. If there is an arc starting at a vertex u
and ending at a vertex v, it is denoted (u,v).
A path in a graph is a sequence of Ux, ei,v2)e2,... }ek-i>vk,
where for all 1 < i < k, e; is an edge from v; to u;+x. Only one edge is
possible between two vertices, so all paths in this paper will be represented by



j a sequence tq, v2,,.. ,Vk- A simple path is a path along which no vertex is
i repeated. A cycle is a path that begins and ends at the same vertex, and a
I simple cycle is a cycle that repeats no other vertices. The number of ver-
i : i
\ u
I I j tices in a path or cycle is called the length of the path or cycle. A tree is a
j i j connected graph that contains no cycle.
In
j A graph is connected if there is a path between every pair of vertices,
j A subgraph is a component if it is a maximal connected subgraph. A graph
j S is complete whenever there is an edge between every pair of vertices. The
! |
| 5 complete graph on n vertices is denoted by K; such a graph is also called a
clique of size n. A vertex v is simplicial if the set of vertices adjacent to x
form a clique.
I I
| ' Given any graph, it is possible to define any number of methods for
i !
j deriving new graphs from it. The graphs of particular interest here are 2-Step
graphs.
I Definition 1 The 2-Step graph if of a graph G is a graph on the
same vertex set as G, and with an edge (x,y) E(H) if and only if there exists
j a vertex z V(G) such that (*,2) and (y, z) E(G). The 2-Step graph of G
will be denoted by 82(G).
Figure 1 gives an example of a graph and its 2-Step graph. Not all
j graphs are 2-Step graphs. Determine if a graph is, or is not, a 2-Step graph
is very difficult. Each of the graphs in Figure 2 is an example of a graph
which is not 2-Step graphs. The 2-Step graph is also sometimes called the
neighborhood graph in the literature.
I
II
I



m

2


(a) A Graph.
(b) Its 2-Step Graph
Figure 1: Example of a Graph and Its 2-Step Graph.
V M
Figure 2: Some Graphs Which Are Not 2-Step Graphs.
3


1.2 The Characterization Problems
For any definition of a class of graphs, it is common to try to find
equivalent definitions in order to learn more about the nature of the class. This
is particularly true when the original definition is difficult to apply. A useful
characterization of 2-Step graphs has sparked interest in the literature, but
still proves elusive. Acharya and Vartak completely solved the characterization
problem in [1].
Theorem 1 (Acharya and Vartak) A graph H having vi,v2,... ,vp
is a 2-Step graph of a graph G if and only if the edges of H can he included
in p complete subgraphs C\y C2,..., Cp where the subgraphs can be indexed so
that
(1) V{ £ Ci, and
(2) Vj Ci Vi Cj.
An edge clique covering of a graph G is a collection of cliques such
that every edge in G is contained in their union. In [IT], Roberts states a result
attributed to Kou, Stockmeyer, and Wong, and also to Orlin: The problem of
deciding if the edges of G can be covered by k cliques is NP-complete. So, the
application of Theorem 1 to the most general setting requires solving an NP~
complete subproblem. Because this theorem is difficult to apply in practice, it
is natural to consider special cases. The following two related characterization
problems have attracted significant attention. For a class of graphs, F:
(1) Given a graph GgF, characterize its 2-Step graph, and
(2) Characterize all graphs G with r.
Before attacking the characterization problems, similar problems can
be studied. There are problems which overlap the 2-Step characterization
4


problems under the appropriate assumptions. One of these is actually a much
broader problem where 2-Step graphs are a special case. For loopless symmetric
digraphs, the competition graph is equivalent to the 2-Step graph.
Definition 2 The competition graph IF of a digraph D is a graph
on the same vertex set as D, and with an edge (x,y) 6 E(H) if and only if
there exists a vertex z £ V(D) such that (x,z) and (y,z) £ A(D). Such a
graph will be denoted C(D).
Another related problem is connected to the adjacency matrix A as-
sociated with any graph G. For a graph on n vertices, the matrix A is n X n,
and an entry = 1 if (^,u3) £ E{G) and is zero otherwise. When the matrix
A is squared, a new graph results. This new graph can be defined without the
uses of matrix terminology.
Definition 3 The square of a graph G is a graph H on the same
vertex set as G, and with an edge (x,y) £ E{H) if and only if:
(1) there exists z £ V(G) such that (z,z) and (y,z) £ E(G), or
(2) the edge (x,y) £ E(G).
Such a graph will be denoted by G2.
Figure 3: Example of the Difference Between the Square and the 2-Step.
(a) A Graph (b) Its Square (c) Its 2-Step
5


In general the square of a graph is not the same as its 2-Step graph.
Figure 3 demonstrates the difference. A sufficient condition for the problems
to overlap are: If every edge in a graph G is contained in a triangle, then
S2(G) = G2.
1.3 Definitions of Graph Classes
Much of the work done on the characterization problems involves
graphs that are in some sense easy to work with. For each of the classes
defined below, fast algorithms for many classically difficult problems in graph
theory are known. Efficient algorithms exist for coloring and clique problems
in all of these classes (See [5]).
Definition 4 A graph is chordal if every cycle of length greater
than three contains an edge connecting two nonconsecutive vertices on the
cycle. Such an edge is called a chord.
Definition 5 A graph G = (V, E) is interval if there exists a set I
of intervals on the real line such that:
(1) / / 4=^ v £ V, and
(2) (u,n) E E 4=4 Iu fl Iv ^ 0.
Definition 6 A graph G = (VrE) is unit interval if there exists a
set I of unit length closed intervals on the real line such that:
(1) 6 / 4=4 v F, and
(2) (u,v) £ E 4=4 / fl J ^ 0.
Definition 7 A graph G = (VtE) is triangle-free if it does not
v
contain three vertices x, y, and z such that (*,y), (x,z), and (y,z) E. Any
three such vertices are called a triangle.
6


Definition 8 A fc-tree is a graph defined recursively as follows: A
fc-tree on fc vertices consists of a clique on k vertices (fc-clique); given any fc-tree
Tn on n vertices, construct a fc-tree onn + 1 vertices by adjoining a new vertex
to Tn, which is made adjacent to each vertex of some fc-cfique of Tn and
nonadjacent to the remaining n fe vertices.
Definition 9 A graph G is bipartite if V(G) can be partitioned
into two non-empty sets X and Y such that the subgraphs induced by X and
Y both contain no edges. A complete bipartite graph is a bipartite graph
with the largest possible |2jJ(G?)|. Such a graph will be denoted by where
n = |X[ and m jY|.
Some useful relationships exist among these graph classes. Trees are
a subclass of bipartite graphs and fc-trees, and are triangle-free. Every edge
in a fc-tree for fc > 2 is in a triangle. Every fc-tree is chordal. Unit interval
graphs are a subclass of interval graphs. The next three theorems show that
unit interval graphs and interval graphs are also a subclass of chordal graphs.
These theorems also provide alternative characterizations of chordal, interval,
and unit interval graphs that are sometimes more convenient than the original
definitions.
Theorem 2 (Lekkerkerker and Boland) A graph G is an interval
graph if and only if:
(1) G is a chordal graph, and
(2) G does not contains an astroidal triple.
An astroidal triple in a graph G is a triple of vertices {x,y, z} such that they
are pairwise nonadjacent, and a path connecting any two of them is nonadjacent
to the third.
7


Theorem 3 (Fulkerson and Gross) A graph G is interval if and only
if the maximal cliques of G can be ordered such that, for every vertex x of G,
the maximal cliques containing x occur consecutively.
Theorem 4 (Roberts) A graph G is unit interval if and only if:
(1) G is an interval graph, and
(2) G does not contain a K\t$ as an induced subgraph.
1.4 Some Known Characterization Results
This section summarizes known results for the classes previously de-
fined as well as some more general results. There are few results concerning
the characterization problem in its most general from. In [6], Greenburg et
al. give a matrix theoretic theorem similar in content to Acharya and Varteks
characterization (Theorem 1). They also consider when a graph with more
than one component is a 2-Step graph.
Theorem 5 If G is a bipartite graph, S2(G) has exactly two compo-
nents. And, if H is a 2-Step graph with exactly two components then any graph
G such that S2(G) = H is bipartite and the bipartition of G is determined by
the components of if.
Theorem 6 If G contains more than two components, G is not a
2-Step graph.
Theorem 5 and Theorem 6 suggest the characterization problems can
be divided into two cases. The first case: 2-Step graphs with exactly two
components. And, the second case: 2-Step graphs with only one component.
Most published work concentrates on the one component problem.
It is also interesting to note that for any graph if, a graph G can
be constructed so that if is an induced subgraph of S2(G). This result was
8


Figure 4: Construction of an Induced Graph in a 2-Step Graph.
first stated by Acharya and Vartak in [1]. The construction requires no more
than n3 steps for a graph of size n. Let F(G) = V{H) U E(H). For each
edge ek = (vi,Vj) E E(H), put the edges (efe,U|) and (ek,Vj) in E(G). The
new graph G will be bipartite since no two vertices from E(H) C V(G) are
ever connected, and no two vertices from V(H) C V(G) are ever connected.
Therefore, one component of S2(G) will be isomorphic to H. An example of
the construction is given in Figure 4.
1.4.1 Trees
Trees are a class of graphs that are particularly easy to work with
because they contain no cycles. The results given for trees apply to the two
component characterization problem. Trees are an example of bipartite graphs,
so the Corollary 1 follows immediately.
Corollary 1 For any tree T on at least two vertices, St{T) has ex-
actly two components.
Because trees have special structure not common to all bipartite
graphs, it might be expected that more could be said about their 2-Step graphs.
This is indeed the case. Lundgren and Rasmussen prove the following in [12].
9


Theorem 7 If T is a tree, then 52 (T) is diamond-free and chordal,
where a diamond is a K less one edge.
It is also possible to find special types of trees with interval 2-Step
graphs. The same paper gives necessary and sufficient conditions for the 2-Step
graph of a tree to be interval.
t
*


*-------*
-----
Figure 5: Graph for Theorem 8.
Theorem 8 For any tree T, 52(T) is interval if and only if T does
not contain an induced H, where H is the graph in Figure 5-
Since it is known that trees generate two component 2-Step graphs, a
next logical step is to find which two component graphs are the 2-Step graphs
of trees. Lundgren and Rasmussen partially solve this problem by finding a
class of connected chordal graphs for which it is possible to construct a second
component so that the resulting graph is the 2-Step graph of a tree. For a
graph G, let K(G) be defined as follows; V{K{G)) is the set {Ci,..., Ck} of
maximal cliques of G and (Ci, Cj) is an edge, if and only if Ci and Cj share a
vertex. The graph K(G) is called the clique graph of G.
Theorem 9 For any connected chordal diamond-free graph G, G U
K(G) is the 2-Step graph of a tree.
There is an algorithm given in [12] to construct the required tree. This
theorem may also be used to test a specific two component graph. However,
10


the conditions given are only sufficient. So, there are graphs which are 2-Step
graphs of trees that do not satisfy the conditions of the theorem.
1.4.2 Complete and Triangle-Free Graphs
It is a trivial observation that the 2-Step graph of any complete graph
not on two vertices is complete. A more interesting question is, which graphs
have complete 2-Step graphs?
In [3], Brigham and Dutton give necessary and sufficient conditions
for a graph G to have a complete 2-Step graph. Let G be the complement
of G, i.e., the graph on the same set of vertices but with (x,y) £ E(G) if and
only if (x,y) £ E(G). Let d(G) be the diameter of G (the maximum distance
between any two vertices), and 7(6?) be the domination number of G, i.e.,
the size of the smallest vertex set D such that every vertex of G is either in D
or is adjacent to a vertex in D.
Theorem 10 For any graphs G with more than two vertices, the
following conditions are equivalent:
(1) *$2(GQ is complete,
(2) d(G) < 2 and every edge of G is in a triangle, and
(3) 7(G) > 3.
The first two conditions follow directly from the definition. If G is
connected, then 7((5) 1. The last condition state that if the domination
number of G is two, then there must be two vertices in G that together are
adjacent to all other vertices of G and are therefore not connected by a path of
length two in G. In the same paper, Brigham and Dutton also consider when a
graph is isomorphic to its 2-Step graph, and when the complement of a graph
is isomorphic to its 2-Step graph.
11


In [2], Boland, Brigham and Dutton consider the problem of finding
a graph G with the smallest number of vertices such that for a given graph H,
H is an induced subgraph of G, An interesting theorem from their work is the
following:
Theorem 11 A triangle-free graph E is a 2-Step graph if and only
if H is the union of vertex disjoint subgraphs of the following types:
(1) C2n. U C2n for n > 2,
(2) C2n+i for n> 2,
(3) Pn U Pn for n> 2,
(4) U ^ ^ 1) or
(5) Px.
Where, Gk is a cycle of length k, and Pk is a path of length k.
1.4.3 fe-trees
In [16], Arundhati Raychaudhuri proves that for interval graphs the
square is also interval. The 2-Step characterization problems overlap the square
characterization problems when every edge of a graph is contained in a triangle.
The class of fc-trees has this property. So, the next two corollaries are an
immediate result.
Corollary 2 If every edge in an interval graph G is contained in a
triangle, then S2(G) is interval.
Corollary 3 If a graph G is both interval and a fc-tree, then &(G>
is interval.
These same corollaries may also be proven as a result of the charac-
terization theorem in Chapter 2. Raychaudhuri also proves the same results
for unit interval graphs.
12


1.4.4 Interval Graphs
In [11], Lundgren and Rasmussen give both necessary and sufficient
conditions for an interval graph to have an interval 2-Step graph. Some ma-
chinery is necessary for the theorem to be stated succinctly. Let N(k) be the
set of all vertices adjacent to a vertex k. This set is called the open neigh-
borhood of k. The closed neighborhood of k, denoted jV[fc], is N(k)U{k}.
Let H be an incomplete interval graph. A family of sets S = {Si,..., ST} of
vertices of H is called a competition cover of H if the following conditions
are satisfied:
(1) If i,j 6 Sm for some m, then i,j 6 N(k) for some vertex k, and
(2) Ifi.i N(k) for some vertex k, then i,j & Sm for some m.
A ranking Si,... ,Sr of a competition cover of H is consecutive if whenever
a vertex x is in Si and Sj for i < j, then for all i < k < j, x £ S*.
Theorem 12 For any incomplete graph H, S2(S) is an interval
graph if and only if H has a competition cover S that has a consecutive ranking.
Type II Type III A^yPeV\
, S 7YA
Figure 6: Example of the Three Types of Nonsimplidal Vertices.
Lundgren and Rasmussen also give a method of constructing a specific
competition cover based on the nonsimplidal vertices of H. Let Ct,..., Cm be
the maximal cliques of H. A nonsimplidal vertex v V{G) can be one of
three types (See Figure 6). If v is contained only in maximal cliques (7, where
\Ci\ > 3, then v is a Type I vertex. If v is contained only in maximal cliques of
13


size [(7*1 = 2, then v is a Type II vertex. If v is contained in maximal cliques
of both sizes, then v is a Type III vertex.
A competition cover may now be constructed. For each Vi construct
the set(s) Si according to the rules:
(1) If V{ is Type I then, Si = iV[t/;].
(2) If Vi is Type II then, Si = N(Vi).
(3) If Vi is Type III then, Su = (J{Cj : t>f Gh \CS | > 3} and S2. = Nfa).
Corresponding
Sets
{1,4,3} {2,3,4}
{2,3,4,5}
{2,3,4,5}
{4,3,6} {3,4,5}
Maximal Nonsimplidal Competition Cover:
{1,3,4} {2,3,4,5} {3,4,6}
Nonsimplidal
Vertices:
2: Type III
3; Type II
4: Type II
5: Type III
Figure 7: Example of the Construction of S'(G).
Now let S' = {Si : Si is maximal}. The next theorem is much stronger
than Theorem 12, since S refers to any competition cover and S' refers to
a specific one. An example of the construction of a maximal nonsimplidal
competition cover is given in Figure 7.
Theorem 13 For any incomplete interval graph H, ^(if) is an in-
terval graph if and only if S' has a consecutive ranking.
This work has very recently been extended by Lundgren and Merz
and is as yet unpublished. Let G = (V, E) and N C V. Then N is called
an extended neighborhood if \N\ > 2 and the following two conditions are
satisfied:
14


(1) *,y G N => there exists z V such that (*, z) and (y, z) G E, and
(2) w 0 N => there exists x N such that (x,z) and (w,z) 0 J5,Vz G V.
The first condition states that there must be a path of length two
between any two vertices in an extended neighborhood. This means that the
2-Step graph of any extended neighborhood is a clique. The second condition
states that an extended neighborhood is maximal, since any vertex that is not
in the set is excluded by some vertex in the set. Let Af denote the collection
of all extended neighborhoods of G. The next two lemmas are given in [10].
Lemma 1 The family Af of extended neighborhoods is a competition
cover.
Lemma 2 The family Af of extended neighborhoods of G correspond
to the set of maximal cliques in 82(G) with at least two vertices.
These lemmas may be combined to prove the next theorem. The
key to the proof is the Fulkerson and Gross characterization of interval graphs
(Theorem 3).
Theorem 14 82(G) is an interval graph if and only if the family Af
of extended neighborhoods of G has a consecutive ranking.
The new result by Lundgren and Merz gives conditions under which
S'(G) ~ A/((7). Combining this result with Theorem 14 gives a corollary
providing sufficient conditions for 82(G) to be interval.
Theorem 15 Let G be a connected incomplete graph with no cycle
of length six as a (not necessarily induced) subgraph. Let S'(G) be the maximal
nonsimplicial competition cover of G. Let Af(G) be the union of the extended
neighborhood sets of G. Then S'(G) Af(G).
15


Corollary 4 For any incomplete, six cycle free, graph G, S3(G) is
interval if and only if S'(G) has a consecutive ordering.
Determining when S' ( family of extended neighborhoods is more difficult than constructing the maxi-
mal nonsimplicial competition cover. This statement is justified by a corollary
of the next theorem.
Theorem 16 For any graph Gt the problem of deciding if there is
an extended neighborhood with k vertices containing only vertices from any
subset R of V(G) is JVT-Complete.
Proof: Given a candidate set N in a graph G of size n, it can be
decided if N is an extended neighborhood in polynomial time. This can be
done by testing N against the definition. For each vertex x,y N, no more
than n2 vertices need be checked to be sure that there exists z £ V{G) such
that (*, z) and (y, z) £ E(G). So, at most n.3 steps are needed to check the first
condition of the definition. For each' vertex to ^ i\T, no more than n2 vertices
need to be checked to be sure that there exists x & N and there does not exist
z £ such that ^2, z^ and ^to, £ B(G). It is trivial to test for |fVj = k and
for N C R. So, the whole process of checking the candidate requires at most
713 steps. Therefore, the decision is in NP.
To show that it is also NP-Complete, it is sufficient to show that an-
other NjP-Complete problem can be reduced to it in polynomial time. Deciding
if there exists a clique of size k for an arbitrary graph II is IVP-Complete. It
v
is possible, in polynomial time, to construct a graph G from any graph H so
that S2(G) contains H as an induced subgraph. By Lemma 2, if there exists
an extended neighborhood of size k containing only vertices from V(H) then
16


there is a clique of size k in H. Therefore, the decision is also NP-Complete.
Corollary 5 Finding the family of extended neighborhood graphs
for an arbitrarily graph G of size n is .ATjP-Complete.
Proof: Since the number of elements in a candidate family is bounded
by to, testing a candidate family requires at most to4 steps. So the problem is
in NP. Suppose the family of extended neighborhoods could be found in poly-
nomial time. Then deciding if there is one of size k for any subset R of V(G)
would require at most n2 steps. This is because at most extended neighbor-
hoods must be checked, and it requires at most n operations to determine if
an extended neighborhood contains a vertex not in R.
1.4.5 Unit Interval
In [14] Lundgren and Rasmussen give necessary and sufficient condi-
tions for a graph to be unit interval. The important lemma is given below.
Figure 8: Graphs for Lemma 3.
Lemma 3 Let G be any graph. Then 82(G) has an induced Ki>3 if
and only if any of the families of graphs given in Figure 8 are contained in G as
an induced subgraph. The heavy lines indicate edges required in each family,
and the light lines indicate optional edges.
It is then possible to use this lemma combined with any of the interval
characterization theorems from Section 1.4.4 to give necessary and sufficient
conditions for a 2-Step graph to he unit interval. As an example:
17


Corollary 6 For any incomplete interval graph G that does not con-
tain one of the graphs in Figure 8 as an induced subgraph, S2(G) is unit interval
if and only if S'(G) has a consecutive ordering.


CHAPTER 2
RESULTS
In this chapter it is shown that there are only two types of chordal
graphs with non-chordal 2-step graphs. However, no forbidden subgraph the-
orem is possible because the nature of these graphs are not always preserved
when they are part of larger graphs. Sufficient conditions under which the
required aspects are preserved are developed. These conditions are shown to
be necessary. Finally some consequences of these conditions are explored.
2.1 Sufficient Conditions
In this section, two simple types of chordal graphs with non-chordal
2-Step graphs are shown to exist. Next, the conditions necessary for embedding
these graphs in larger graphs are developed. Then these results are collected
into a sufficient conditions theorem.
2.1.1 Simple Chordal Graphs with Non-chordal 2-Step Graphs
From the definition of chordal graphs, it is necessary to find a graph G
that generates a 2-Step graph with a chordless cycle with length four or greater.
Consider a chordless simple cycle C yi,V2, ,yn of length n > 4 in S2(G),
Since this cycle is generated by G, there must exist D yifZi,y2jZ2,,.. ,yn,zn,
a (not necessarily simple) cycle of length 2n in G. The most direct way of
constructing an appropriate G is to assume D is a simple cycle and add edges
to make G chordal without adding any chords to C. It is possible to do ibis,


and a structure satisfying these conditions is now defined.
Definition 10 An n-sun is a chordal graph G = (V, E) whose vertex
set V can he partitioned into Y = {yi,y2, ,3/n} and Z {z1,z2,...,zn},
satisfying the following conditions:
(1) Y is a stable set in G,
(2) Zi, z2,..., zn is a chordal cycle in G, and
(3) {yhzi) e E(G) 4=>- i = j or i j + 1 (cyclic addition).
Figure 9: Examples of n-suns.
Two examples of n-suns are given in Figure 9. It is easy to see that
each vertex along G is connected to its neighbors by a path of length exactly
two. The cycle is also chordless. This will now be stated formally and proven.
Lemma 4 For any n-sun F, with n > 3, S2{F) contains a chordless
cycle of length n.
Proof: The graph S2(F) contains the cycle C = yity2, -. ,yn since
for every 1 < i < n the edges (^,2,) and (2;,t/i+i) are in F. Now suppose G
contained a chord (yuyj). Then there exists x V(F) such that (y,-,x) and
(x,yj) . E(F), where \j 1| > 1, By the definition of n-sun, is only adjacent
to Zi-1 and 2,*, and yj is only adjacent to zj-i and zy. The vertex x must be
20
!


equal to one vertex from each adjacency set. But then \j t| < 1, and this is
a contradiction.
Another solution to the problem of constructing G from D is to make
G out of the fewest possible number of vertices. Then D collapses on itself,
and there is no need to add extra edges to make G chordal. One such structure
is defined below.
Definition 11 A bowtie is a graph constructed by adding a triangle
to each end of a path of length two or greater. For a bowtie B, let TX(B) and
T2(J5) be the sets of vertices of the two triangles.
a e a e
(a) Smallest Bowtie
a
(b) Length Two Bowtie
(c) General Bowtie
Figure 10: Examples of Bowties.
Some examples of bowties are given in Figure 10. It is not as easy to
pick out the cycle C. The path between the triangles is used twice, once for
one half of the cycle, and once for the other half. To see how this is possible
consider Figure 11. Lemma 5 states and proves the existence of a chbrdless
cycle in the 2-Step graph.
Lemma 5 For any bowtie B with \V{B)\ n-j-2, 83(B) contains a
chordless cycle of length n.
21


(a) Smallest Bowtie (b) Length Two Bowtie
and Its 2-Step Graph. and Its 2-Step Graph.
a e
a e
Figure 11: Examples of Bowties and Their 2-Step Graphs.
22


Proof: Let P = c,mi,m2)... ,m_4, d be the path in the bowtie B.
Let a and b be the vertices adjacent to e, and e and / be the vertices adjacent to
d. Then if n is odd, C c,m2,ro4,..., rf, e,mn_4,mn_e,... ,m1}a,c is a cycle
in S2(B). If ra is even, (7 = c,m2,7TO4,... ,mn_4, e, d, mnfi,7nn_rt ...,roi,a,c
is a cycle in S2(B). There are only six edges in S2(B) that are not used in
C. They are (m\, b), (b, c), (b, a), (mn_4, /), (/, d), and (/, e). None of them are
chords of C.
2.1.2 jR-induced Subgraphs
c
Figure 12: Graph with Induced Bowtie That Is Not JLinduced.
In order to motivate the next definition, suppose for a chordal graph
ff, S2 (B) is non-chordaL Now construct G from H by adding one new vertex
3, and an edge from s to every vertex in B. The new graph is also chordal
and clearly contains B as an induced subgraph. But because any two vertices
in H are both connected to a, S2(G) contains a clique on the vertices of B.
Therefore, S2(B) is not necessarily an induced subgraph of S2(G) for any B an
induced subgraph of G. There are other ways this can happen. Consider the
graph in Figure 12. It contains a bowtie induced by {a, 6, f, d,e,g}, but the
2-Step graph contains no chordless cycle. So no forbidden subgraph theorem
is possible.
It is not quite necessary for S2(B) to be an induced subgraph of
S2(G). There exist graphs B and G such that B Is a subgraph of G, B and
23


(a) The Subgraph H (6-sun) (b) The 2-Step Graph of H
(c) The Graph G (d) The 2-Step Graph of G
Figure 13: Example of the 2-Step graph of an Induced Subgraph.
24


G are chordal, S2(B) is non-chordal and not an induced subgraph of S% (G),
and S'2(G) is non-chordal. Consider the graph in Figure 13. Unfortunately,
this is the smallest such example. Here, H is a 6-sun and G contains H plus
one additional vertex adjacent to every vertex on the internal cycle of if. This
extra vertex forces the vertices of the internal cycle to form a complete graph
in S2(G), but this does not happen in S2(H). In both cases, a chordless cycle of
length six exists in the 2-Step graph. So it is only necessary to assure that if is
contained in G in such a way that the non-chordality of the induced subgraph
is not lost in the 2-Step process. This can be done by restricting the edges
that can be added to a subgraph from paths outside of it during the process.
The following definition allows these restrictions to be made explicit for any
instance of a subgraph.
Definition 12 An induced subgraph H = (W, F) of a graph G
(V., E) is an iZ-induced subgraph of G on iZ C p{W) whenever, for every
x £ V W and every y,z £ W such that {,y) and (*, z) £ E, there exists
S £ R such that y,z £ S. The set R is called the restriction.
The graph from Figure 12 contains an induced bowtie, but the vertex
c is connected in such a way that a chord is introduced into the cycle generated
by the bowtie. The restriction for bowties B in general is iZ = {Ti(B),Ta(B)}.
This will he proven in the next section, but is used here as an example of a
restriction.
The graph in Figure 12 does not contain an iZ-induced bowtie.^ There
is only one possible bowtie in the graph, so the only possible restriction is
R {{a,6, e,p}}. Now, since c £ V(G) V(B) and 6,d £ V(B) such
that (c, b) and (c, d) £ E(G), but there is no set S in R such that b,d £ S, the
25


bowtie in not i2-induced for this restriction.
Figure 14: Graph with an JR-induced Bowtie.
The graph in Figure 14 does contain an jR-induced bowtie. Consider
B induced by {a, 6, e, d, e, /}. Then the restriction is R = {{a, b, c}, {d, e, /}}.
From the definition of jR-induced, it is only necessary to consider the vertices
of the graph that are adjacent to a vertex in B. The vertex g V{G) V(B)
is adjacent to a, b and c. The set {a,b,c} 6 R allows these adjacencies. The
vertex k £ V{G) V(B) is adjacent to d and f. The set {d, e, /} £ R allows
these adjacencies. The vertices h and i are only adjacent to one vertex in B
so they do not need to be considered further. Therefore, B is an JR-induced
subgraph for this restriction.
2.1.3 Sufficient Conditions Theorem
The results from the previous two sections are collected here. The
restrictions necessary for the two simple types of chordal graphs with non-
chordal 2-Step graphs are stated and proven. This allows for the development
of a large class of graphs with this property.
Theorem IT For any chordal graph (?, 52((7) is not chordal if
(1) G contains an R-induced bowtie B, where R = {Ti{B),T2(B)}i or
(2) G contains an jR-induced n-sun F, with n > 3, where R yf=1{Z U yi\.
26


Proof: Suppose G contains an -R-induced bowtie B. Then G contains
an induced bowtie B. By Lemma 5, the 2-Step graph of B contains a chordless
cycle C of length four or greater. Suppose (#{, yj) is a chord in this cycle in
S2(G). Then there exists a vertex £ V(G) adjacent to yi and y, for some
|j i| > 1. Due to the restriction R, yi,yj Ti(B) or yi,yj £ T2(B). Since
these sets are symmetric, suppose yi,yj £ Ti(B). There are only three vertices
in Tt(B), two are already adjacent along C and one is not a vertex of C. Any
pair from these three vertices does not generate a chord in S2(G). This is a
contradiction. Now suppose G contains an fi-induced n-sun F, with n > 3.
Then G contains an induced n-sun F, with n > 3. By Lemma 4 the 2-Step
graph of F contains a chordless cycle C of length four or greater. Suppose
(jliiVj) is a chord in this cycle in S2(G). Then there exists x £ V(G) adjacent
to yi and yj for some \j ~~ i\ > 1. Due to the restriction, and yj must both
belong to the same subset of R. By definition, there is no such subset, so there
is no chord. This is a contradiction.
2.2 Necessary Conditions
In this section the conditions given in Section 2.1.3 will also be shown
to be necessary. The combination of these two main results is a partial solution
to the chordal characterization problems.
2.2.1 Basics
The following assignments and lemmas will be used in the proof of
the Theorem. Let G be a chordal graph such that S2(G) is not chordal. Let
C ai,a2,...,an be a chordless simple cycle of length n in S2(G). Let D
i > *i, 02? *2i tt5 be the (not necessarily simple) cycle of length 2n in G
27


that induces G. Let A = {at : 1 < i < n} and X = {x^ : 1 < % < n}. All
additions of indices of vertices from A or X are assumed to he cyclic.
Lemma 6 For all 1 < i < j < n, aj ^ ay and xy.
Proof: For all a A, a is distinct since C is a simple cycle. Suppose
there exist i ^ j such that = xy, then a^, xy,ay induces (a^, ay) £ S^G).
This is a chord of G unless j i A 1, but in this case ay, xy, (tj+i induces the
chord (a., in C. This contradicts C being a chordless cycle.
Lemma 7 For all z £ X, (a,-,z) £ 2£(G) 4=>- z = x,_i or z = xy.
Proof: The only iP direction is trivial. Suppose there exists j
i 1 i such that (ay,xy) 6 E(G). Then ay,xy,ay induces (ay, ay) £ £2(G).
This is a chord of C unless j i + 1, but in this case oy,xy, ay+i induces the
chord (ay,ay+1) in G. This contradicts G being a chordless cycle.
Lemma 8 For all z £ A} (xy,z) £ V(G) 4=4> z = ay or z = ay+i.
Proof: The only iP direction is trivial. Suppose there exists j
r 7^ i + 1 such that (xy, ay) £ E(G). Then ay,xy,ay induces (a,-, ay) £ 52(G).
This is a chord of C unless j i 1, but in this case ay+i,xy,ay induces the
chord (ay+1,ay) in C. This contradicts C being a chordless cycle.
Lemma 9 For any (not necessarily simple) cycle D on more than
three vertices in a chordal graph G, if there exist z%, z2, z3 £ P(D) with (zi,z2)
and (z2, z3) £ P(G), Zi ^ z3, and z2 not adjacent to any other vertex on a path
in D from z\ to z3, then (zi,z3 ) e Z(<3).
Proof: Suppose there exists a path P = z3, z4,,.., zn, Zj along D to
which z2 is not adjacent, and that (zj, z3) 0 2?(G). Since zi z3, P must
contain simple subpaths of length two or greater from z\ to z3. Let Z be the
shortest of these. So, Z, z%,zx is a chordless cycle of length four or greater.
28


This contradicts G being chordal.
Lemma 10 If D generates C, then D contains no vertices of degree
one.
Proof: Let z be a vertex of degree one on D. If z £ A then by
Lemma T, z must be adjacent to two distinct vertices in X. If z £ X then
by Lemma 8, z must be adjacent to two distinct vertices in A. Therefore, the
degree of z is at least two. This is a contradiction.
2.2.2 Necessary Conditions Theorem
Theorem 18 For any chordal graph G, S2(G) is chordal if
(1) G contains no iZ-induced bowtie B, where R = {Ti{B),T2(B)}, and
(2) G contains no iZ-induced n-sun F1 with n > 3, where R = U?=i{^ U y;}.
Proof: Suppose S2(G) is not chordal. Then G is a graph that satisfies
the above assignment and lemmas. The remainder of the proof is broken into
three cases. The first case shows that if D contains a sub cycle of length three,
then D is an induced bowtie. The second case shows that D can contain no
other sub cycles. The third case shows that if D is a simple cycle, then G
contains an induced n-sun.
Case 1: D contains a subcycle of length three.
In this case D is forced to contain a bowtie. The proof will proceed by
induction. Let Hk be the graph in Figure 15.
Figure 15: Graph for P(k).
29


Let Lk = V{Hk) {4}, and Mk = X U A V{Hk). The vertex dk is
in neither set.
Let P(k) he the proposition:
(i) The graph Hk is an induced subgraph of G, and
(ii) For all u E Lk and v E Mk-, (u,u) g E(G), and
(iii) dk E A and dk E X.
Without loss of generality, suppose a1,2i,a2,ai is the triangle along
D. To prove P(l), it will be shown that the graph in Figure 16 satisfies
each of the conditions.
Let H be the graph in Figure 16. The edges of H are in G by definition
of D. If = a-3, then a3,a2,ai induces the chord (03,01) in C. If
(2=1, *3) E E(G), then 01,2:1,03 induces the chord (a3,01) in G, If
(2, %) E E(G), then 01,02,03 induces the chord (03,01) in C. So all
that remains to prove that S is induced is to show that o3 = xn. First,
some other relationships will be shown.
For P(l), Li = {a1}xi,a2} and Mi = X U A {oi,i,o2, o3}. The
sets L\ and Mt are both subsets of X U A. But since a vertex may
have two labels, one from X and one from A, it is not clear that D
does not wrap back into L% again. Lemma 6 implies neither 01 nor o2
is equal to any Oj 6 Mt 0 A. Lemma 6 also implies neither xt nor x2
is equal to any Xj M\ ft X. Since Oi = x2 it follows that &i / z, for
all 2 6 Mi. Lemma 7 implies a2 ^ for all xj E Mi D X. Lemma 8
Figure 16: Graph for P(l).
30


implies x1 ^ aj, for all aj £ Mi (1 A. So, D does not go through any
vertex in L\ again.
Now, it will be shown a3 = xn. Suppose this is not true. By Lemma 7
and Lemma 8, the vertex a* = x2 cannot be adjacent to anything else
in D except xi,xn,a2, and o3. There is a path in D from xn to a3 that
does not go through a* since D is a cycle and does not wrap back into
L\. Then Lemma 9 with a3,ai,xn as the three consecutive vertices
implies that (a3,xn) £ E(G). But then, a3,xn,ai induces the chord
(a3,ai) in C. This is a contradiction, so a3 = Condition (1) is now
satisfied, and by the assignment d\ as = xn Condition (3) is also
satisfied.
Now it is necessary to show that there are no edges in G connecting
Li and Mt. It has already been shown that the vertex at = x2 is not
adjacent to any vertex of M\. Lemma 7 implies (x^a,) ^ E(G) for
any a,* £ Mi fl A, and (a2,x;) $ E(G) for any Xj Mi fll.
Figure 17: Graph Showing (a2ian) £ E(G).
If there exists a* £ Mx fl A {a} such that (02,0,) £ E{G), then
ai,a2,ai induces the chord in C. Since a3 = xn, a2 ^ x and
(a2,xn) £ E(G). So, if (a2,an) £ E(G), then ai,a2lan,xmai is a
chordless 4-cycle in G {See Figure 17).
31


Figure 18: Graph Showing (*i, Xi) E(G).
If there exists i; e MiflX such that (xi, Xi) E E(G), then let k be the
highest such index. The vertices at, i, as* are consecutive along D, and
P = xfe,Ofc+1,...,xn,ax is a path not adjacent to so Lemma 9 im-
plies (ax,*) E J5(G), a contradiction (See Figure 18). There is no such
smallest k and no such Xi and therefore, L\ and Mi are disconnected.
Now that the P(l) is established, the proof of the first case will be
completed by proving the following: If P(k) is true, then either P(k+1)
is true or D contains a bowtie. Since there are only a finite number of
vertices in the graph the series of propositions is bounded. Lemma 10
implies that a bowtie must be found along the way. By the inductive
hypothesis, <4_i,c4 E A D X. So by Lemma 7 and Lemma 8, <4 can
be adjacent to at most two vertices of Mk, one from X and one from
A.
dk is only adjacent to z Mk
The uniqueness of the adjacency of z to dk and condition (2) of
P(k) satisfies condition (1) of P(k + 1) by defining c4+i = z.
Now Ljk+i and Mk+i are well defined. Since z is uniquq in M*.
and dk A and only dk-1 X is also adjacent to <4, Lemma 7
implies z E X. Similarly, since z is unique in Mk and dk X and
only dk-i A is also adjacent to dk, Lemma 7 implies z & A. So,
32


condition (3) is satisfied. Condition (2) is satisfied for all vertices
in Lk ~ Lk+i {dk}} and by the assumption of this case d*. is not
adjacent to any vertex other than z in Af*.
dk is adjacent to zai zx £ Mk
By Lemma 7, za and zx cannot both be in A, or both be in X.
Without loss of generality assume za £ A and zx £ X. If |Mk\ > 2
then D continues through Mk, and by Lemma 9 with za,dk,zx as
the three consecutive vertices, (za,zx) 6 E(G). If \Mk\ = 2 then
since Lk and Mk are disconnected, Lemma 7 applied to za requires
(ztt, zx) £ E(G). Therefore D contains a bowtie.
Case 2: D contains a subcycle of length greater than three.
This cannot happen. Let Z = ai,Xi, a2,x2,..., Ofe,ai be the shortest
cycle of length greater than three and less than 2n (see Figure 19).
Here, = xk. If (xi,a*.) £ E(G), then induces the chord
(i,-Ofe) in. C since k > 3. If (x k,o-i) £ E(G) for some £ Af)V(Z) ~
{xt} {a,k} then Lemma 8 is contradicted since (x&, a-k) and (xk, Ofe+i)
are already in E(G). If (a1}Xj) £ E(G) for some Xi £ X ft V(Z)
{xx} {a*} then Lemma 7 is contradicted since and
are already in E(G) and by Lemma 6 ^ Therefore since a% x*?
(ai,z) £ E(G) for all z £ V(Z) {i} {afc}. But then, Lemma 9
with xi,alsafe as the consecutive vertices implies (x1}afc) £ E(G). This
is a contradiction, so there is no shortest subcyde.
Case 3: D contains no subcycle.
Then D is a simple cycle. It will now be shown that V(D) induces
an n-sun. Suppose (a^aj+i) $ E{G) (see Figure 20). Then since G
33


Figure 19: Graph for Case 2.
is chordal and D is a cycle of length greater than four, there exists
zi G V(D) such that z^a^zx is a triangle, and z2 G V(D) such that
*sja+i!^2 is a triangle. If zx ^ then z% ^ A since Lemma 8 would
be violated by as,*, and zx ^ X since Lemma 7 would be violated by ax.
If z2 / asj+i then z2 ft A since Lemma 8 would be violated by as,*, and
z2 $ X since Lemma 7 would be violated by ai+i. So, (as^i,^) and
(asj,asf4.i) are both in V(G).
Figure 20: Graph for Case 3.
Suppose (a,*,ai+i) G E(G). Then (ai^a,) £ E(G) since
would induce a chord (aj_x,ai+1) in C. Similarly (ai+1,a,-+2) ^ E(G).
Since these two edges must flank the existing edge, by the^ above
argument (a5a_i,) and (*i,a5i+i) are also both in V(G). Therefore
Z = xx, *2) , is a cycle in G. Any vertex a; is not adjacent to
a vertex Zj with i j ^ j + 1, by Lemma 7. The set A is stable in
34


G since, if there exists 1 < i < j < n such that (a*, aj) £ E(G) then
XifXi+i,... ctj, a,i contains a chordless cycle. The set A
is equivalent to the set Y, and the set X is equivalent to the set Z in
the definition of a n-sun. So, V(D) is a n-sun.
2.3 Consequences
Corollary 7 For any interval graph G, 82(G) is chordal if and only
if G contains no JZ-induced bowties.
Proof: Every n-sun with n > 4 contains an astroidal triple. Consider
the three vertices 3/1,3/25 and 3/3. They are pairwise nonadjacent since Y is a
stable set. The path 3/1,21,3/2 is not adjacent to y3. The path 3/2,22,3/3 is not
adjacent to 3/1, and the path 3/3,23, z4,..., zn, 3/1 is not adjacent to 3/2. If G is
interval, it contains no astroidal triples and therefore no n-suns.
Corollary 8 For any chordal graph G with every edge contained in
a triangle, 82(G) is chordal if and only if G contains no fZ-induced n-sun.
Proof: Every edge in a bowtie is not contained in a triangle. There-
fore, G contains no bowties.
Corollary 9 For any k-tree G with k > 2, S*(G) is chordal if and
only if G contains no JR-induced n-sun.
Proof: Every edge in a fc-tree with k > 2 is contained in a triangle.
Corollary 10 If a chordal graph G contains no P4 as an induced
subgraph, then S2(G) is chordal.
Proof: A bowtie contains an induced path of length at least three.
A bowtie is formed from a path of length at lease two, the triangle on each end
extends this path by one vertex on each end. An n-sun with n > 4 contains
a path of length three. Consider the path 3/1, Zi, 3/3. The vertices 3/1 and 3/3
35


are not adjacent to each other since Y is a stable set. The vertex yi can only
be adjacent to zn and Zi, so it cannot be adjacent to z%. The vertex 3/3 can
only be adjacent to z2 and z3, so it cannot be adjacent to z\. Therefore, if G
contains no path of length three as an induced subgraph, it contains no bowtie
and no n-sun.
Corollary 11 If an interval graph G contains no P4 as an induced
subgraph, then S2{G) is unit interval.
Proof: By Corollary 10, S2(G) is chordal. Every graph in Figure 8
contains a path of length three as an induced subgraph. So, S2(G) contains
no ifii3. Suppose there exists a triple {u,v,w} of vertices in S2(G) that is
astroidal. Let P = 11,%,..., dk,v be the shortest path not adjacent to w
in S2 (G). Then there must be a (not necessarily simple) path Q = u =
Uq, 2J|, , ^
Case 1: w is not adjacent to Q.
Then, since u,v, and w were chosen in no particular order G must
contain an astroidal triple. This contradicts G being interval.
Case 2: (uj, a;) £ E(G) for some 1 < i < fc.
Suppose w 1+l. Then, (a;,a,+x) ^ E(G) since ai,a*+i,sci+i would
induce the edge (a;,tu) in S2(G). This contradicts w not adjacent to P.
Similarly, (xi,xi+1) £ E(G) since a^x^Xi+i would also induce (a^w)
in S2(G). The edge (i,Oj+i) does not exist because P is the shortest
path, so 35;,ai,*i+1,al+i is an induced path of length four. This is a
contradiction. Now suppose w is not equal to any vertex in Q. Then,
(w, cq+i) is not an edge because w would be equivalent to x in the
previous argument. The edge (ai,a{+i) ^ E(G), since then a,-+1,o,-,u;
36


induces (aj+i,w in S2{G). The edge (a^i-fijw) ^ £J(G), since then
ai5i+i,tu induces (a;,to) in S2{G). So, w,ai,a5^i,ai+1 is an induced
path of length four. This is a contradiction.
Case 3: (wfXj) E(G) for some 1 < j < k + 1.
Then, aj,Xjfw induces the edge (aj,w) in S2(G). This contradicts w
not adjacent to P, So, this case cannot occur.


BIBLIOGRAPHY
[1] B.D. Acharya and M.N. Vartak. Open neighborhood graphs. Technical
report, Research Report of the Indian Institute of Technology, Bombay,
1973.
[2] James W. Boland, Robert C. Brigham, and Ronald D. Dutton. Embed-
ding arbitrary graphs in neighborhood graphs. Journal of Combina-
torics, Information & System Sciences, 12(3-4):110112, 1987.
[3] Robert C. Brigham and Ronald D. Dutton. On neighborhood graphs.
Journal of Combinatorics, Information & System Sciences, 12(1-
2):75-85, 1987.
[4] D. R. Fulkerson and 0. A. Gross. Incidence matrices and interval graphs.
Pacific Journal of Mathematics, 15:835-855, 1965.
[5] Martin C. Golumbic. Algorithmic Graph Theory and Perfect
Graphs. Academic Press, New York, 1980.
[6] Harvey J. Greenbergs J. Richard Lundgren, and John S. Maybee. The
inversion of 2-step graphs. Journal of Combinatorics, Information
& System Science, 8:33-43, 1985.
[7] Kathryn F. Jones, J. Richard Lundgren, John S. Maybee, and Norman J.
Pullman. Competition graphs of strongly connected and hamiltonian di-
graphs. To appear in Siam Journal on Discrete Mathematics.
[8] L. T. Kou, L. J. Stockmeyer, and C. K. Wong. Covering edges by cliques
with regard to keyword conflicts and intersection graphs. Communica-
tions of the ACM, 21:135-139, 1978.
[9] C. B. Lekkerkerker and J. C. Boland. Representation of a finite graph by a
set of intervals on the real line. Fundamenta Mathematicae, 51:45-64,
1962.
[10] J. Richard Lundgren, John S. Maybee, Sara Merz, and Craig Rasmussen.
Interval 2-step graphs. CU-Denver Research Report, 1992.


[11] J. Richard Lundgren and Craig Rasmussen. Interval graphs with non-
interval competition graphs. Congressus Numerantium, 82:105-116,
1991.
[12] J. Richard Lundgren and Craig Rasmussen. Two-step graphs of trees. To
appear in Discrete Math.
[13] J.Richard Lundgren and John S. Maybee. Food webs with interval com-
petition graphs. Appears in Graphs and Applications Proceedings
of the First Colorado Symposium on Graph Theory. John Wiley
and Sons Inc., 1984.
[14] J.Richard Lundgren, Craig W. Rasmussen, and John S. Maybee. Interval
competition graphs of symmetric digraphs. To appear in Applied Math.
[15] J. Orlin. Contentment in graph theory: Covering graphs with cliques.
Proc. of the Koninklijke Nederlander Academic von Weten-
schappen, Amsterdam, Series A, 80:406-424, 1977.
[16] Arundhati Raychaudhuri. On powers of interval and unit interval graphs,
Congressus Numerantium, 59:75-85, 1987.
[17] Fred S. Roberts. Applications of edge coverings by cliques. Discrete
Applied Mathematics, 10:93-105, 1985.