Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs.
We prove that claw-free graphs, containing an induced dominating path, have a Hamiltonian path, and that 2-connected claw-free graphs, containing an induced doubly dominating cycle or a pair of vertices such that there exist two internally disjoint induced dominating paths connecting them, have a Hamiltonian cycle. As a consequence, we obtain linear time algorithms for both problems if the input is  restricted to (claw,net)-free graphs. These graphs enjoy those interesting structural properties.
Introduction
. Hamiltonian properties of claw-free graphs have been studied
extensively in the last couple of years. Di#erent approaches have been made, and a
couple of interesting properties of claw-free graphs have been established (see [1, 2, 3,
5, 6, 13, 14, 15, 16, 19, 22, 23, 25, 26]). The purpose of this work is to consider the
algorithmic problem of finding a Hamiltonian path or a Hamiltonian cycle e#ciently.
It is not hard to show that both the Hamiltonian path problem and the Hamiltonian
cycle problem are NP-complete, even when restricted to line graphs [28]. Hence, it is
quite reasonable to ask whether one can find interesting subclasses of claw-free graphs
for which e#cient algorithms for the above problems exist.
Already in the eighties, Du#us, Jacobson, and Gould [12] defined the class of
(claw,net)-free (CN-free) graphs, i.e., graphs that contain neither an induced claw
nor an induced net (see Figure 1.1). Although this definition seems to be rather
restrictive, the family of CN-free graphs contains a couple of graph families that are
of interest in their own right. Examples of those families are unit interval graphs,
claw-free asteroidal triple-free (AT-free) graphs, and proper circular arc graphs. In
their paper [12], Du#us, Jacobson, and Gould showed that this class of graphs has the
nice property that every connected CN-free graph contains a Hamiltonian path and
every 2-connected CN-free graph contains a Hamiltonian cycle. Later, Shepherd [27]
proved that there is an O(n 6 ) algorithm for finding such a Hamiltonian path/cycle in
CN-free graphs. Note also that CN-free graphs are exactly the Hamiltonian-hereditary
# Received by the editors June 23, 1999; accepted for publication (in revised form) January 13,
2000; published electronically November 28, 2000. An extended abstract of these results has been
presented at the 25th International Workshop on Graph-Theoretic Concepts in Computer Science,
Lecture Notes in Comput. Sci. 1665, Springer-Verlag, New York, 1999, pp. 364-376.
http://www.siam.org/journals/sicomp/30-5/35777.html
Fachbereich Informatik, Universit?t Rostock, A. Einstein Str. 21, D-18051 Rostock, Germany
(ab@informatik.uni-rostock.de).
# Department of Mathematics and Computer Science, Kent State University, Kent, OH 44242
(dragan@mcs.kent.edu). The research of this author was supported by the German National Science
Foundation (DFG).
Fachbereich Mathematik, Technische Universit?t Berlin, Stra-e des 17. Juni 136, D-10623 Berlin,
Germany (ekoehler@math.TU-Berlin.DE). The research of this author was supported by the graduate
program "Algorithmic Discrete Mathematics," grant GRK 219/2-97 of the German National Science
Foundation (DFG).
LINEAR ALGORITHMS FOR HAMILTONIAN PROBLEMS ON. 1663
graphs [10], i.e., the graphs for which every connected induced subgraph contains a
Hamiltonian path.
In this paper we give a constructive existence proof and present linear time algorithms
for the Hamiltonian path and Hamiltonian cycle problems on CN-free graphs.
The important structural property that we exploit for this is the existence of an induced
dominating path in every connected CN-free graph (Theorem 2.3). The concept
of a dominating path was first used by Corneil, Olariu, and Stewart [8] in the context
of AT-free graphs. They also developed a simple linear time algorithm for finding
such a path in every AT-free graph [7]. As we show in Theorem 2.3, for the class of
CN-free graphs, a linear time algorithm for finding an induced dominating path exists
as well. This property is of interest for our considerations since we prove that all
claw-free graphs that contain an induced dominating path have a Hamiltonian path
(Theorem 3.1). The proof implies that, given a dominating path, one can construct
a Hamiltonian path for a claw-free graph in linear time.
For 2-connected claw-free graphs, we show that the existence of a dominating
pair is su#cient for the existence of a Hamiltonian cycle. dominating pair is a
pair of vertices such that every induced path connecting them is a dominating path.)
Again, given a dominating pair, one can construct a Hamiltonian cycle in linear time
(Theorem 5.6). This already implies, for example, a linear time algorithm for finding
a Hamiltonian cycle in claw-free AT-free graphs, since every AT-free graph contains a
dominating pair and it can be found in linear time [9]. Unfortunately, CN-free graphs
do not always have a dominating pair. For example, an induced cycle with more
than six vertices is CN-free but does not have such a pair of vertices. Nevertheless,
2-connected CN-free graphs have another nice property: they have a good pair or an
induced doubly dominating cycle. An induced doubly dominating cycle is an induced
cycle such that every vertex of the graph is adjacent to at least two vertices of the
cycle. A good pair is a pair of vertices, such that there exist two internally disjoint
induced dominating paths connecting these vertices. We prove that the existence of
an induced doubly dominating cycle or a good pair in a claw-free graph is su#cient
for the existence of a Hamiltonian cycle (Theorems 5.1 and 5.5). Moreover, given an
induced doubly dominating cycle or a good pair of a claw-free graph, a Hamiltonian
cycle can be constructed in linear time. In section 4 we present an O(m
algorithm which, for a given 2-connected CN-free graph, finds either a good pair or
an induced doubly dominating cycle.
For terms not defined here, we refer to [11, 17]. In this paper we consider finite
connected undirected graphs E) without loops and multiple edges. The
cardinality of the vertex set is denoted by n, whereas the cardinality of the edge set
is denoted by m.
A path is a sequence of vertices (v 0 , . , v l ) such that all v i are distinct and
its length is l. An induced path is a path where
cycle (k-cycle) is a path
(v 0 , . , its length is k. An induced cycle is a cycle
is an induced cycle
of length k # 5.
The distance dist(v, u) between vertices v and u is the smallest number of edges
in a path joining v and u. The eccentricity ecc(v) of a vertex v is the maximum
distance from v to any vertex in G. The diameter diam(G) of G is the maximum
eccentricity of a vertex in G. A pair v, u of vertices of G with dist(v,
is called a diametral pair.
A. BRANDST -
ADT, F. F. DRAGAN, AND E. K -
OHLER
a
c d
a
c
x
y z
Fig. 1.1. The claw K(a; b, c, d) and the net N(a, b, c; x, y, z).
For every vertex we denote by N(v) the set of all neighbors of v,
1}. The closed neighborhood of v is defined by {v}. For a
vertex v and a set of vertices S # V , the minimum distance between v and vertices
of S is denoted by dist(v, S). The closed neighborhood N[S] of a set S # V is defined
by
We say that a set S # V dominates G if doubly dominates
G if every vertex of G has at least two neighbors in S. An induced path of G
which dominates G is called an induced dominating path. A shortest path of G which
dominates G is called a dominating shortest path. Analogously one can define an
induced dominating cycle of G. A dominating pair of G is a pair of vertices v,
such that every induced path between v and u dominates G. A good pair of G is a pair
of vertices v, u # V , such that there exist two internally disjoint induced dominating
paths connecting v and u.
The claw is the induced complete bipartite graph K 1,3 , and for simplicity, we
refer to it by K(a; b, c, d) (see Figure 1.1). The net is the induced six-vertex graph
y, z) shown in Figure 1.1. A graph is called CN-free or, equivalently, (claw,
net)-free if it contains neither an induced claw nor an induced net. An asteroidal triple
of G is a triple of pairwise nonadjacent vertices, such that for each pair of them there
exists a path in G that does not contain any vertex in the neighborhood of the third
one. A graph is called AT-free if it does not contain an asteroidal triple. Finally, a
Hamiltonian path or Hamiltonian cycle of G is a path or cycle, respectively, containing
all vertices of G.
2. Induced dominating path. In this section we give a constructive proof
for the property that every connected CN-free graph contains an induced dominating
path. In fact, we show that there is an algorithm that finds such a path in linear time.
To prove the main theorem of this section we will need the following two lemmas.
Lemma 2.1 (see [12]). Let be an induced path of a CN-free
graph G, and let v be a vertex of G such that dist(v, P 2. Then any neighbor y of
v with dist(y, P adjacent to x 1 or to x k .
Lemma 2.2. Let P be an induced path connecting vertices v and u of a CN-free
graph G. Let also s be a vertex of G such that s /
Then
1. for every shortest path P # connecting v and s, P #
2. if there is an edge xy of G such that x # P \ {v} and y # P # \ {v}, then both
x and y are neighbors of v.
Proof. Let y be the vertex of P # \ {v} which is closest to s and has a neighbor
x on P \ {v}; clearly, y #= s. Let s # , v # be the neighbors of y on the subpaths of P #
connecting y with s and y with v, respectively. Since s # /
# N[P ], by Lemma 2.1, vertex
LINEAR ALGORITHMS FOR HAMILTONIAN PROBLEMS ON. 1665
y must be adjacent to v or to u. If yu # E, then v # u # E, too (otherwise, we have
a claw K(y; s # , v # , u)). But now dist(v, u) # dist(v,
dist(v, u), and a contradiction arises. Therefore, y is adjacent to v, and since y /
the paths P and P # have only the vertex v in common. Moreover, to avoid a claw
vertex x has to be adjacent to v.
Theorem 2.3. Every connected CN-free graph G has an induced dominating
path, and such a path can be found in O(n +m) time.
Proof. Let G be a connected CN-free graph. One can construct an induced
dominating path in G as follows. Take an arbitrary vertex v of G. Using breadth first
search (BFS), find a vertex u with the largest distance from v and a shortest path P
connecting u with v. Check whether this path P dominates G. If so, we are done.
Now, assume that the set is not empty. Again, using BFS, find a vertex s
in S with largest distance from v and a shortest path P # connecting v with s. Create a
new path P # by joining P and P # in the following way: there
is a chord xy between the paths P and P # (see Lemma 2.2), and P
otherwise. By Lemma 2.2, the path P # is induced. It remains to show that this path
dominates G.
Assume there exists a vertex t # V \ N[P # ]. First, we claim that t is dominated
neither by P nor by P # . Indeed, if t # (N[P necessarily tv # E
and v /
neighbors x # P and y # P # of v are adjacent. Therefore, we get
a net N(v, y, x; t, s # , u # ), where s # and u # are the vertices at distance two from v on
paths P # and P , respectively. Note that vertices s # , u # exist because dist(v, s) # 2.
Thus, t is dominated neither by P nor by P # . Moreover, from the choice of u
and s we have 2 # dist(v, t) # dist(v, s) # dist(v, u). Now let P # be a shortest path,
connecting t with v, and let z be a neighbor of v on this path. Applying Lemma
2.2 twice (to P, P # and to P # , P # ), we obtain a subgraph of G depicted in Figure
2.1. We have three shortest paths P, P # , P # , each of length at least 2 and with only
one common vertex v. These paths can have only chords of type zx, zy, xy. Any
combination of them leads to a forbidden claw or net. This contradiction completes
the proof of the theorem. Evidently, the method described above can be implemented
to run in linear time.
t u
x
z
y
s
Fig. 2.1.
It is not clear whether CN-free graphs can be recognized e#ciently. But, to apply
our method for finding an induced dominating path in these graphs, we do not need
to know in advance that a given graph G is CN-free. Actually, our method can be
A. BRANDST -
ADT, F. F. DRAGAN, AND E. K -
OHLER
applied to any graph G. It either finds an induced dominating path or returns either
a claw or a net of G, showing that G is not CN-free.
Corollary 2.4. There is a linear time algorithm that for a given (arbitrary)
connected graph G either finds an induced dominating path or outputs an induced claw
or an induced net of G.
Proof. Let G be a graph. For an arbitrary vertex v of G, we find a vertex u with
the largest distance from v and a shortest path P connecting u with v. If P dominates
G, then we are done. Else, we find a vertex s # V \ N[P ] with the largest distance
from v and a shortest path P # connecting v with s. If there are vertices in P # \ {v}
which have a neighbor on P \ {v}, we take the vertex y that is closest to s and check
whether y is adjacent to v and u. If it is adjacent neither to u nor to v, then G has a
net or a claw (see the proof of Lemma 2.1). If yu # E or yv # E and a neighbor x of
y on P \ {v} is not adjacent to v, then G has a claw (see Lemma 2.2). Now, if we did
not yet find a forbidden subgraph, then the only possible chord between the paths P
and P # is xy with xv, yv # E, and we can create an induced path P # as described in
the proof of Theorem 2.3. Hence, it remains to check whether P # dominates G. If
there exists a vertex t # V \ N[P # ], then again we will find a net or a claw in G (see
Theorem 2.3). It is easy to see that the total time bound of all these operations is
linear.
3. Hamiltonian path. In what follows we show that for claw-free graphs the
existence of an induced dominating path is a su#cient condition for the existence of
a Hamiltonian path. The proof for this result is constructive, implying that, given an
induced dominating path, one can find a Hamiltonian path e#ciently.
Theorem 3.1. Every connected claw-free graph G containing an induced dominating
path has a Hamiltonian path. Moreover, given an induced dominating path, a
Hamiltonian path of G can be constructed in linear time.
Proof. Let E) be a connected claw-free graph and let
be an induced dominating path of G. If
and, since G is claw-free, there are no three independent vertices in G - {x 1 }. (By
we denote a subgraph of G induced by vertices V \ {x 1 }.) If G - {x 1 } is
not connected, then, again because G is claw-free, it consists of two cliques C 0 , C 1
and a Hamiltonian path of G can easily be constructed. If G - {x 1 } is connected,
we can construct a Hamiltonian path as follows. First, we construct a maximal path
vertices that are not in P 1 are neither connected to y 1 nor
to y l . Let R be the set of all remaining vertices. If #, we are done. If there is
any vertex in R, it follows that y 1 y l # E since otherwise there are three independent
vertices in G- {x 1 }. Furthermore, any two vertices of R are joined by an edge, since
otherwise they would form an independent triple with y 1 (and with y l as well). Hence,
R induces a clique. Since G-{x 1 } is connected, there has to be an edge from a vertex
R # R to some vertex y Now we can construct a Hamiltonian
path P of G:
R), where -
R stands for an
arbitrary permutation of the vertices of R \ {v R }.
For first construct a Hamiltonian path P 2 for G
described above, using x 1 as the dominating vertex. At least one endpoint of P 2 is
adjacent to x 2 since if G # -{x 1 } is not connected, x 2 has to be adjacent to all vertices
of either C 0 or C 1 (otherwise, there is a claw in G), and if G # - {x 1 } is connected, the
construction gives a path ending in x 1 which is, of course, adjacent to x 2 . To construct
a Hamiltonian path for the rest of the graph we define for each vertex x i (i # 2) of P
a set of vertices
Each set C i forms a clique of G since if two
LINEAR ALGORITHMS FOR HAMILTONIAN PROBLEMS ON. 1667
vertices u, v # C i are not adjacent, then the set u, v, x i , x i-1 induces a claw. Hence
we can construct a path P
stands for an arbitrary permutation of the vertices of C i \{x i+1 }. This path P # is
a Hamiltonian path of G because it obviously is a path, and, since P is a dominating
path, each vertex of G has to be either on P , P 2 , or in one of the sets C i .
For the case finding the connected components of G - {x 1 } and
constructing the path P 1 can easily be done in linear time. For k # 2 we just have to
make sure that the construction of the sets C i can be done in O(n+m), and this can
be realized easily within the required time bound.
Theorem 3.2. Every connected CN-free graph G has a Hamiltonian path, and
such a path can be found in O(n +m) time.
Proof. By Theorem 2.3, every connected CN-free graph has an induced dominating
path P , and it can be found in linear time. Using the path P , by Theorem 3.1,
one can construct a Hamiltonian path of G in linear time.
Analogously to Corollary 2.4, we can state the following.
Corollary 3.3. There is a linear time algorithm that for a given (arbitrary)
connected graph G either finds a Hamiltonian path or outputs an induced claw or an
induced net of G.
Proof. The proof follows from Corollary 2.4 and the proof of Theorem 3.1.
4. Induced dominating cycle, dominating shortest path, or good pair.
In this section we show that every 2-connected CN-free graph G has an induced doubly
dominating cycle or a good pair. Moreover, we present an e#cient algorithm that, for
a given 2-connected CN-free graph G, finds either a good pair or an induced doubly
dominating cycle.
Lemma 4.1. Every hole of a connected CN-free graph G dominates G.
Corollary 4.2. Let H be a hole of a connected CN-free graph G. Every vertex
of V \ H is adjacent to at least two vertices of H.
A subgraph G # of G (doubly) dominates G if the vertex set of G # (doubly) dominates
G.
Lemma 4.3. Every induced subgraph of a connected CN-free graph G which is
isomorphic to S 3 or S - 3 (see Figure 4.1) dominates G.
a d c
f
e
a d c
f
e
Fig. 4.1.
Proof. Let G contain an induced subgraph isomorphic to S - 3 , and assume that it
does not dominate G. Then, there must be a vertex s such that dist(s, S -
2. Let
x be a neighbor of s from N[S - 3 ]. If x is adjacent neither to a, nor to b, nor to c (see

Figure

4.1), then G contains a claw (e.g., if xf # E, then a claw K(f
Thus, without loss of generality, x has to be adjacent to a or b.
1668 A. BRANDST -
ADT, F. F. DRAGAN, AND E. K -
OHLER
If xa # E, then x is adjacent neither to b nor to c, since otherwise we will get a
claw (K(x; a, b, s) or K(x; a, c, s)). To avoid a net N(a, e, d; x, b, c) vertex x must be
adjacent to e or d. But, if ex # E, then xd # E too. (Otherwise, we will have a claw
Analogously, if xd # E, then also xe # E. Hence, x is adjacent to both
e and d, and a net N(x, e, d; s, b, c) arises.
Now, we may assume that x is adjacent to b and not to a, c. To avoid a claw
K(b; x, e, f ), x must be adjacent to e or f . But again, xe # E if and only if xf # E.
(Otherwise, we get a net N(x, b, e; s, f, a) or N(x, b, f ; s, e, c).) Hence x is adjacent to
both e and f and a claw K(x; s, e, f) arises.
Consequently, S - 3 dominates G. Similarly, every induced S 3 (if it exists) dominates
G.
Lemma 4.4. Let P be an induced path connecting vertices v and u of a connected
CN-free graph G. Let s be a vertex of G such that s /
has an induced doubly dominating cycle, and such a
cycle can be found in linear time.
Proof. Let P v and P u be shortest paths connecting vertex s with v and u, re-
spectively. Both these paths as well as the path P have lengths at least 2. Since
and there is a chord between P and P v , then it is unique
and both its endvertices are adjacent to v. The same holds for P and P
endvertices of the chord (if it exists) are adjacent to u.
Now, without loss of generality, we suppose that dist(s, u) # dist(s, v). Then,
from u /
2.2 we deduce that P u # P
and P u at most one chord is possible, namely, the one with both endvertices adjacent
to s. Consequently, we have constructed an induced subgraph of G shown in Figure
4.2 (only chords s # s # , v # v # and u # u # are possible).
s
Fig. 4.2.
If the lengths of all three paths P, P v , P u are at least 3, then it is easy to see
that G has a hole H k (k # 6). Furthermore, if at least one of these paths has length
greater than or equal to 4, or two of them have lengths 3, then G must contain a hole
It remains to consider two cases: lengths of both P v and P u are 2 and
LINEAR ALGORITHMS FOR HAMILTONIAN PROBLEMS ON. 1669
the length of P is 3 or 2. Clearly, in both of these cases the graph G contains either a
hole or an induced subgraph isomorphic to S -
3 or S 3 . By Corollary
4.2, every hole of G doubly dominates G.
Let G contain an S - 3 with vertex labeling shown in Figure 4.1. We claim that the
induced cycle (e, b, f, d, e) dominates G or G contains a hole H 6 . Indeed, if a vertex
s of G does not belong to S -
3 , then, by Lemma 4.3, it is adjacent to a vertex of S -
3 .
Suppose that s is adjacent to none of e, b, f, d. Then, without loss of generality, sa # E,
and we obtain an induced subgraph of G isomorphic either to a net N(e, a, d; b, s, c) or
to H depending on whether vertices s and c are adjacent. Hence,
we may assume that (e, b, f, d, e) dominates G, and since G is claw-free, this cycle is
doubly dominating.
Now let G contain an S 3 with vertex labeling shown in Figure 4.1. We will show
that every vertex of G is adjacent to at least two vertices of the cycle (e, f, d, e) or G
contains a hole H 5 . Suppose vertex s of G is adjacent to none of e, d. Then, by Lemma
4.3, s is adjacent to at least one of a, b, c, f . Let sf # E. To avoid a claw, vertex s
is adjacent to both b and c. But then a hole H arises. Assume that
loss of generality, sa # E. To avoid a net N(a, e, d; s, b, c), s
must be adjacent to b or c. In both cases a hole H 5 occurs.
Clearly, the construction of an induced doubly dominating cycle of G given above
takes linear time.
Theorem 4.5. There is a linear time algorithm that, for a given connected CN-
finds an induced doubly dominating cycle or gives a dominating
shortest path of G.
Proof. Let G be a connected CN-free graph. One can construct an induced doubly
dominating cycle or a dominating shortest path of G as follows (compare with the
proof of Theorem 2.3). Take an arbitrary vertex v of G. Find a vertex u with the
largest distance from v and a shortest path P connecting u with v. Check whether
dominates G. If so, we are done; P is a dominating shortest path of G. Assume
now that the set is not empty. Find a vertex s in S with the largest
distance from v and a shortest path P v connecting v with s. Create again a new path
shortest paths P and P v as in the proof of Theorem 2.3. We have
proven there that P # dominates G. Now let P u be a shortest path between s and u.
If dist(s, u) # dist(v, u) or both dist(s, u) > dist(v, u) and v /
4.4 can be applied to get an induced doubly dominating cycle of G in linear time.
Therefore, we may assume that dist(s, u) > dist(v, u) # dist(v, s) and v # N[P u ].
Now we show that the shortest path P u dominates G. If v lies on the path P u , then
and we are done. Otherwise, let x be a neighbor of v in P u . Note that
dist(v, s) > 1 and so x #= s, u. Since G is claw-free, v is adjacent to a neighbor
x. Assume, without loss of generality, that x is closer to s than y. If
we show that dist(v,
by the proof of Theorem 2.3, the path P u will dominate G (as a path obtained by
"joining" two shortest paths that connect v with u and v with s, respectively). By the
triangle condition, we have dist(u, s) < dist(v, u)+dist(v, s) (strict inequality because
Consequently,
Since all our proofs were constructive, we can conclude the following.
A. BRANDST -
ADT, F. F. DRAGAN, AND E. K -
OHLER
Corollary 4.6. There is a linear time algorithm that, for a given (arbitrary)
connected graph G, either finds an induced doubly dominating cycle, or gives a dominating
shortest path, or outputs an induced claw or an induced net of G.
Lemma 4.7. Let be a dominating shortest path of a graph
G. Then max{ecc(v), ecc(u)} # diam(G) - 1.
Proof. Let x, y be a diametral pair of vertices of G; that is,
If both x and y are on P , then necessarily {x,
and holds or, without loss of generality,
and Finally, if both x and y are in N[P
dist(x, y), then we may assume that at least one of x, y belongs to N(v), say, x.
Hence, dist(x, y)
A pair of vertices u, v of G with dist(u, called a pair of
mutually furthest vertices.
Corollary 4.8. For a graph G with a given dominating shortest path, a pair of
mutually furthest vertices can be found in linear time.
Proof. Let be a dominating shortest path of G with
holds. Denote by x a
vertex of G such that dist(v, ecc(v). Note that both the eccentricity of v and a
vertex furthest from v can be found in linear time by BFS. Now, if
then v, x are mutually furthest vertices of G. Else, ecc(x) > ecc(v) # diam(G) - 1
must hold and vertices x and y, where y is a vertex with dist(x,
diametral pair of G; dist(x,
In what follows we will use the fact that in a 2-connected graph every pair of
vertices is joined by two internally disjoint paths. In order to actually find such a
pair of paths, one can use Tarjan's linear time depth first search- (DFS)-algorithm
for finding the blocks of a given graph. For the proof of Lemma 4.9, we refer to [21].
Lemma 4.9. Let G be a 2-connected graph, and let x, y be two di#erent nonadjacent
vertices of G. Then one can construct in linear time two induced, internally
disjoint paths, both joining x and y.
Theorem 4.10. There is a linear time algorithm that, for a given 2-connected
CN-free graph G, either finds an induced doubly dominating cycle or gives a good pair
of G.
Proof. By Theorem 4.5, we get either an induced doubly dominating cycle or a
dominating shortest path of G in linear time. We show that, having a dominating
shortest path of a 2-connected graph G, one can find in linear time a good pair or
an induced doubly dominating cycle. By Corollary 4.8, we may assume that a pair
x, y of mutually furthest vertices of G is given. Let also be two induced internally
disjoint paths connecting x and y in G. They exist and can be found in
linear time by Lemma 4.9 (clearly, we may assume that xy /
# E, because otherwise
together with a vertex z # V \ {x, y} will form a doubly
dominating triangle). If one of these paths, say, P 1 , is not dominating, then there
must be a vertex s # V \ N[P 1 ] . Since x, y are mutually furthest vertices of G,
we have dist(s, x) # dist(x, y), dist(s, y) # dist(x, y). Hence, we are in the conditions
of Lemma 4.4 and can find an induced doubly dominating cycle of G in linear
time.
Corollary 4.11. There is a linear time algorithm that, for a given (arbitrary)
2-connected graph G, either finds an induced doubly dominating cycle, or gives a good
or outputs an induced claw or an induced net of G.
LINEAR ALGORITHMS FOR HAMILTONIAN PROBLEMS ON. 1671
5. Hamiltonian cycle. In this section we prove that, for claw-free graphs, the
existence of an induced doubly dominating cycle or a good pair is su#cient for the
existence of a Hamiltonian cycle. The proofs are also constructive and imply linear
time algorithms for finding a Hamiltonian cycle.
Theorem 5.1. Every claw-free graph G that contains an induced doubly dominating
cycle has a Hamiltonian cycle. Moreover, given an induced doubly dominating
cycle, a Hamiltonian cycle of G can be constructed in linear time.
Proof. Let be an induced doubly dominating cycle
of G. As before, we define C
k). Each set C i forms
a clique of G; otherwise, we would have a claw. Furthermore, C
the sets N[x 1 ], C 2 , . , C k-1 form a partition of the vertex set of G. Note that any
vertex adjacent to x k and not to x j (1 < j < belongs to N[x 1 ], since the cycle DC
is doubly dominating. Let G }) be the subgraph of G induced
by If we show that there is a Hamiltonian path P in G # starting
at a neighbor of x k and ending at a neighbor of x 2 , then we are done; the cycle
Hamiltonian cycle of G (recall that
stands for an arbitrary permutation of the vertices of C i \ {x i+1 }).
G # is a connected graph, by Theorem 3.1, there exists a Hamiltonian path
. Assume that x k s, x k t /
# E. Then, to avoid a claw
vertices s and t have to be adjacent, giving a new Hamiltonian path
P # of G # starting at x 1 and ending at a vertex y. If y is adjacent neither to x k nor
to x 2 , then a claw K(x 1 occurs. (Note that in case
is adjacent to at least one of x k , x 2 because the cycle doubly
dominating.) Without loss of generality, yx 2 # E and the path P # is a desired path
of G # .
So, we may assume that x k is adjacent to t or s. Analogously, x 2 is adjacent to
one of t, s. If x k , x 2 are adjacent to di#erent vertices, then we are done; the path P #
starts at a neighbor of x k and ends at a neighbor of x 2 . Otherwise, let both x k and
x 2 be adjacent to t and not to s. Then a claw K(x 1
or we get a contradiction with the property of to be a doubly
dominating cycle.
Corollary 5.2. Every claw-free graph, containing an induced dominating cycle
of length at least 4, has a Hamiltonian cycle, and, given that induced dominating
cycle, one can construct a Hamiltonian cycle in linear time.
E) be a graph, and let be an induced dominating
path of G. P is called an enlargeable path if there is some vertex v in V \P that is either
adjacent to x 1 or to x k but not to both of them and, additionally, to no other vertex
in P . Consequently, an induced dominating path P is called nonenlargeable if such
a vertex does not exist. Obviously, every graph G that has an induced dominating
path has a nonenlargeable induced dominating path as well. Furthermore, given an
induced dominating path P , one can find in linear time a nonenlargeable induced
dominating path P # by simply scanning the neighborhood of both x 1 and x k . For the
next theorem we will need an auxiliary result.
Lemma 5.3. Let G be a claw-free graph, and let
an induced nonenlargeable dominating path of G such that there is no vertex y in G
with there is a Hamiltonian path in G that starts in x 1
1672 A. BRANDST -
ADT, F. F. DRAGAN, AND E. K -
OHLER
Proof. Let
is empty. Using the method described in the proof of Theorem 3.1, we can easily
construct a path, starting in x 1 and ending in x k , that contains all vertices of C 2 , . ,
C k-1 . This implies that we have to worry only about how to insert the vertices of the
neighborhood of x 1 into this path. We have to consider two cases.
Case 1. consists of two connected components C 0 , C 1 .
Since G is claw-free, both C 0 and C 1 induce cliques in G. Furthermore, x 2 is
adjacent to all vertices of at least one of C 0 and C 1 , say, C 1 , because otherwise we
have a claw in G.
Let y be an arbitrary vertex of C 0 . Since P is nonenlargeable, y has at least one
neighbor on P \{x 1 }, and let x j be the one with smallest index. By the preconditions
of our lemma, j #= k. If j > 2, then y has to be adjacent to x j+1 as well, since
y, x j-1 , x j+1 ) is a claw. Furthermore, y is adjacent to all vertices
y, x j-1 , c j ) is a claw. Hence, when constructing the
Hamiltonian path, we can simply add y to C j .
Now we consider the set Y of all vertices y of C 0 with yx 2 # E. Suppose there is a
vertex c 2 in C 2 with c 2 #= x 3 . If there is a vertex c 1 # C 1 that is nonadjacent to vertex
there is an edge from every vertex c 0 # Y to c 2 ; otherwise, K(x
a claw of G. This implies that we can construct a Hamiltonian path with the required
properties. If, on the other hand, all vertices of C 1 are adjacent to all vertices of C 2 ,
we can construct such a path by starting in x 1 , traversing through Y , x
proceeding as before. Now suppose that there is no vertex In
this case either all vertices c 0 # Y or all vertices c 1 # C 1 have to be adjacent to x 3 ,
because otherwise K(x claw. Suppose, without loss of generality, that
all vertices of Y are adjacent to x 3 . Then we construct the path by starting in x 1 ,
traversing through C 1 , x 2 , Y , x 3 , and proceeding as before.
Case 2. induces a connected graph.
If x 2 is not adjacent to any of the vertices in H, then H has to be a clique and
we can apply the method described in case 1.
Suppose now that x 2 is adjacent to some vertex in H. First, we construct a
Hamiltonian path which is done as in the proof of Theorem
3.1, since there is no independent triple in H. Now we claim that either x 2 is adjacent
to one of y 1 or y l , or P # does in fact induce a Hamiltonian cycle of H implying again
the existence of a path with an end-vertex adjacent to x 2 . Indeed, suppose x 2 is not
adjacent to any of the endvertices of P # . Then, since G is claw-free, y 1 has to be
adjacent to y l , because otherwise K(x would induce a claw in G. Hence
induces a Hamiltonian cycle in H.
Using P # , we can easily construct a Hamiltonian path in N[x 1 ] starting in x 1
and ending in x 2 . The rest of the Hamiltonian path of G can be constructed as
before.
In fact, we can prove a slightly stronger result. Let
Each of these
sets forms a clique of G.
Lemma 5.4. Let G be a claw-free graph, and let
an induced dominating path of G such that there is no vertex y in G with N(y)
also P be enlargeable but only to one end, e.g.,
assume that there exists an edge zb with z # C k-1 \ {x k } and b # B. Then there is
LINEAR ALGORITHMS FOR HAMILTONIAN PROBLEMS ON. 1673
Proof. First, we can easily construct a path, starting in x 1 and ending in x k-1 ,
that contains all vertices of C 2 , . , C k-2 . Then we attach to this path a path which
starts at x k-1 , goes through C k-1 , B using all their vertices, and ends in x k . Finally,
we insert the vertices of the neighborhood of x 1 into the obtained path as we have
done in the proof of Lemma 5.3.
Theorem 5.5. Let G be a 2-connected claw-free graph with a good pair u, v.
Then G has a Hamiltonian cycle and, given the corresponding induced dominating
paths, one can construct a Hamiltonian cycle in linear time.
Proof. Let be the induced
dominating paths, corresponding to the good pair u, v. By the definition of a good
both k and l are greater than 2. We may also assume that, for any induced
dominating path exists such
that together with y would form an induced
dominating cycle of length at least 4, and we can apply Corollary 5.2 to construct a
Hamiltonian cycle of G in linear time.
Let A 1 be the set of vertices a 1 that are adjacent to x 1 but to no other vertex of
be the set of vertices b 1 that are adjacent to x k but to no other vertex of
are defined accordingly for P 2 . Of course, each of the sets A 1 , A 2 ,
forms a clique of G.
First we assume that one of these paths, say, P 1 , is nonenlargeable, i.e., A
In this case we do the following. We remove the inner vertices of P 2 from G
and get the graph G- (P 2 ), where denotes the inner vertices of P 2 . Then, using
we create a Hamiltonian path in G- (P 2 ) that starts at u and ends at v (Lemma
5.3), and we add (P 2 ) to this path to create a Hamiltonian cycle of G.
We can use this method for creating a Hamiltonian cycle of G whenever we have
two internally disjoint paths P, P # of G both connecting u with v such that one of
them is an induced dominating and nonenlargeable path of the graph obtained from
G by removing the inner vertices of the other path.
Now we suppose that both paths P 1 , P 2 are enlargeable. Because of symmetry
we have to consider the following three cases.
Case 1. There exist a vertex a 1 # A 1 \ A 2 and a vertex
In this case there must be edges from a 1 , b 1 to inner vertices y i , y j of P 2 . Con-
sequently, we can form a new path P #
2 by starting in u and traversing through A 1 ,
is the subpath of P 2 between y i and y j . Evi-
dently,
contains all vertices of B 1 , A 1 and is internally disjoint from P 1 , which is
nonenlargeable in G- (P #
Case 2. there exists a vertex a 1 # A 1 \ A 2 .
In this case none of the vertices of B #) has a neighbor in
v. As G is 2-connected, for some vertex b # B there has to be a
vertex dominates G and z /
# B, vertex
z must be adjacent to a vertex y # P 2 \ {v}. If z is only adjacent to y but to no
other vertex of P 2 , then z necessarily belongs to A 2 and we can form a new path P #by starting in u, using all vertices of A 2 , B and ending in v. Again, P #
1 is internally
disjoint from P 2 and P 2 is nonenlargeable in G- (P #
then we
can apply Corollary 5.2.
Therefore, we may assume that z is adjacent to an inner vertex y of P 2 . Now, if
there exists a vertex a 1 # A 1 \ A 2 , then a 1 is adjacent to some vertex y # of
we can construct a new path P #
2 by using u, A 1 , y # , . , y, z, B, v. (If B was empty,
then
2 ends at . , y # , . , y l-1 , v.) This path is internally disjoint from P 1 , which
A. BRANDST -
ADT, F. F. DRAGAN, AND E. K -
OHLER
is nonenlargeable in G - (P #
then from the discussion above we may
assume that either A := A is empty or there is a vertex z # V \
which is adjacent to a vertex of A and has a neighbor y # in (P 2 ). Hence, we can
construct a path P #
2 by using u, A, z # , y # , . , y, z, B, v, which is internally disjoint
from P 1 . (If z
2 is constructed by using u, A, z, B, v.)
Case 3. A 2 is strictly contained in A 1 , and B 1 is strictly contained in B 2 .
Consider vertices cliques C
then we can construct a new path P #
2 by using
This path is internally disjoint from P 1 , which is nonenlargeable in
G-
there must be a neighbor y # (P 2 ) of z # . If vertex b is adjacent to
some vertex in C k-1 \{v}, then we construct a new path P #
2 by using u, A 1 , y # , . , v. It
will be internally disjoint from P 1 , which is enlargeable only to one end (at x
G-(P #
We are now in the conditions of Lemma 5.4 and can construct a Hamiltonian
path of G- (P #
starts in u and ends in v. Adding (P #
2 ) to this path, we obtain
a Hamiltonian cycle of G.
So, we may assume that zz # /
vertex z # A 1 \ A 2 and that vertex b is
not adjacent to any vertex of C k-1 \ {v}. From this we conclude also that z /
But since z /
there must be a neighbor x j # (P 1 ) of z. We choose vertex
with the smallest j. Clearly, 1 < j < k - 1 and z # C j .
First we define a new induced path P #
cliques
We have z # A # 1 , since
otherwise from the construction of P #
would be adjacent to z, and that is impossible

Note that vertex x j+1 is dominated by the path P 2 . If it is adjacent to only
vertex v from P 2 , then arises. Therefore,
x j+1 must be adjacent to an inner vertex y of P 2 . Now we define a new path P #by using u, A # 1 , y # , . , y, x j+1 , C j+1 , x j+2 , . , C k-1 , v. It is internally disjoint from
1 and contains all vertices of A # 1 and C 1). It is clear from the
construction that the path P #
1 dominates the graph G - (P #
(Every vertex which
was not dominated by the path P #
1 in G belongs to some set C i (j
It remains to show that the path P #
1 is nonenlargeable in G - (P #
Assume by
way of contradiction that it is enlargeable. Since A # 1 # (P #
2 ), this is possible only if
be a vertex of B #
1 . Then p does not belong to B 1 , since otherwise it
should be adjacent to z, which is contained in (P #
are cliques,
.) Now, from we conclude that the neighbors
of p in P 1 \ {v} are only vertices from {x j+1 , . , x k-1 }, i.e., p belongs to a set C s for
some s 1. Consequently, a contradiction to C s # (P #
arises.
It is not hard to see that the above method can be implemented to run in linear
time.
Theorem 5.6. Every 2-connected claw-free graph G that contains a dominating
pair has a Hamiltonian cycle, and, given a dominating pair, a Hamiltonian cycle can
be constructed in linear time.
Proof. Let v, u be a dominating pair of a 2-connected graph G. If vu /
by Lemma 4.9, there exist two internally disjoint induced paths connecting v and u.
Both these paths dominate G, and, therefore, u, v is a good pair of G. Thus, the
statement holds by Theorem 5.5.
Now let vu # E. Define sets A := N(u) \ N[v], B := N(v) \ N[u], and S :=
# N(u). Since G is claw-free, the sets A and B are cliques of G. Notice also that
LINEAR ALGORITHMS FOR HAMILTONIAN PROBLEMS ON. 1675
sets A, B, S, and {v, u} form a partition of the vertex set of G.
If there is an edge ab in G such that a # A and b # B, then vertices a, u, v, b induce
a 4-cycle which dominates G. Hence, we can apply Corollary 5.2 to get a Hamiltonian
cycle of G. Therefore, assume that no such edge exists. But since G is 2-connected,
there must be edges ax, by with x, y # S, a # A, and b # B. We distinguish between
two cases. Let G S denote the subgraph of G induced by S.
Case 1. G S is disconnected.
Then, it consists of two cliques S 1 and S 2 . Now, if vertices x, y are in di#er-
ent components of G S , say, x
y, P S2\{y} , u) is a Hamiltonian cycle of G. (P M stands for an arbitrary
permutation of the vertices of a set M .) If x, y are in one component, say, S 1 , then
is a Hamiltonian cycle of G.
Case 2. G S is connected.
Then, by Theorem 3.1, there exists a Hamiltonian path
G S . Assume that as, at /
# E. Then, to avoid a claw K(u; a, s, vertices s and t have
to be adjacent, giving a Hamiltonian cycle HC := (s, y 1 , . , y l , t, s) of G S . Vertices
x and y split this cycle into two paths Hence, a
is a Hamiltonian cycle of G.
Now, we may assume that a is adjacent to s or t. Analogously, b is adjacent
to one of t, s. If a, b are adjacent to di#erent vertices, say, as, bt # E, then
is a Hamiltonian cycle of G. Finally, if a, b are adjacent
only to s (similarly, to t), then (u, P \ {s}, v, P B\{b} , b, s, a, P A\{a} , u) is a
Hamiltonian cycle of G.
Theorem 5.7. Every 2-connected CN-free graph G has a Hamiltonian cycle, and
such a cycle can be found in O(n +m) time.
Proof. The proof follows from Theorems 4.10, 5.1, and 5.5.
Corollary 5.8. There is a linear time algorithm that for a given (arbitrary)
2-connected graph G either finds a Hamiltonian cycle or outputs an induced claw or
an induced net of G.
Corollary 5.9. A Hamiltonian cycle of a 2-connected (claw,AT)-free graph can
be found in O(n +m) time.
Remark. Corollary 5.8 implies that every 2-connected unit interval graph has
a Hamiltonian cycle, which is, of course, well known (see [24, 20]). The interesting
di#erence of the above algorithm compared to the existing algorithms for this problem
on unit interval graphs is that it does not require the creation of an interval model.
It also follows from Corollaries 3.3 and 5.8 that both the Hamiltonian path problem
and the Hamiltonian cycle problem are linear time solvable on proper circular arc
graphs. Note that previously known algorithms for these problems had time bounds
Fig. 5.1. Claw-free graph, containing a dominating pair and a net.
1676 A. BRANDST -
ADT, F. F. DRAGAN, AND E. K -
OHLER
It should also be mentioned that Theorems 3.1 and 5.5 do cover a class of graphs
that is not contained in the class of CN-free graphs. Figure 5.1 shows a graph that
is claw-free, does contain a dominating/good pair and, consequently, a dominating
path, but, obviously, it is neither AT-free nor net-free.



--R

Every 3-connected



Minimal 2-connected non-hamiltonian claw-free graphs

A linear time algorithm to compute a dominating path in an AT-free graph
Discrete Math.
time algorithms for dominating pairs in asteroidal triple-free graphs

Graph Theory
Forbidden subgraphs and the Hamiltonian theme

Characterizing forbidden pairs for hamiltonian properties

On Hamiltonian claw-free graphs
Algorithmic Graph Theory and Perfect Graphs
Local tournaments and proper circular arc graphs

Finding hamiltonian circuits in interval graphs


Hamiltonian cycles in 3-connected claw-free graphs
An optimum

Hamiltonicity in claw-free graphs

Introduction to Graph Theory
--TR

--CTR
Jou-Ming Chang, Induced matchings in asteroidal triple-free graphs, Discrete Applied Mathematics, v.132 n.1-3, p.67-78, 15 October
Andreas Brandstdt , Feodor F. Dragan, On linear and circular structure of (claw, net)-free graphs, Discrete Applied Mathematics, v.129 n.2-3, p.285-303, 01 August
Sun-Yuan Hsieh, An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs, Journal of Parallel and Distributed Computing, v.64 n.5, p.662-685, May 2004
hamiltonian path;hamiltonian cycle;linear time algorithms;dominating pair;claw-free graphs;net-free graphs;dominating path