Convexity and HHD-Free Graphs.
It is well known that chordal graphs can be characterized via m-convexity. In this paper we introduce the notion of m3-convexity (a relaxation of m-convexity) which is closely related to semisimplicial ordering of graphs. We present new characterizations of HHD-free graphs via m3-convexity and obtain some results known from [B. Jamison and S. Olariu, Adv. Appl. Math., 9 (1988), pp. 364--376] as corollaries. Moreover, we characterize weak bipolarizable graphs as the graphs for which the family of all m3-convex sets is a convex geometry. As an application of our results we present a simple efficient criterion for deciding whether a HHD-free graph contains a r-dominating clique with respect to a given vertex radius function r.
Introduction
. This paper was inspired by the results of Farber and Jamison
[16] on convexity in chordal graphs and by the results of Jamison and Olariu [19] on
semisimplicial orderings of graphs produced by "lexicographic breadth first search"
(LexBFS) [25] and "maximum cardinality search" (MCS) [28].
Throughout this paper all graphs E) are finite, undirected, and simple
(i.e., loop-free and without multiple edges). The complement of a graph G is the
graph G with the same vertex set V , where two vertices are adjacent in G i# they are
nonadjacent in G.
A path is a sequence of vertices v 0 , . , v l such that v i v
its length is l. An induced path is a path, where v i
An induced cycle is a sequence of vertices v 0 , . , v k such that v
k). The length |C| of a cycle C is its number of vertices. Let
also |P | be the number of vertices of a path P . A hole is an induced cycle of length
at least five, whereas an antihole is the complement of a hole. By P k we denote an
induced path on k vertices. A graph G is connected i# for any pair of vertices of G
there is a path in G joining these vertices. A set S # V is connected in G i# the
subgraph G(S) induced by S is connected.
The distance dG (u, v) between two vertices u, v is the minimum number of edges
on a path connecting these vertices, and is infinite if u and v lie in distinct connected
components of the graph G. If no confusion can arise we will omit the index G. For
# Received by the editors June 14, 1995; accepted for publication (in revised form) February 24,
1998; published electronically January 29, 1999. Results of this paper were presented at the 5th
Internat. Colloq. on "Graphs and Combinatories," Marseille Luminy, September 3-8, 1995.
http://www.siam.org/journals/sidma/12-1/32171.html
Fachbereich Informatik, Universitat Rostock, Lehrstuhl fur Theoretische Informatik, D 18051
Rostock, Germany (dragan@informatik.uni-rostok.de, ab@informatik.uni-rostock.de). The research
of the first author was supported by DAAD
# Gerhard-Mercator-Universitat, GH Duisburg, FB Mathematik, FG Informatik, D 47048 Duis-
burg, Germany (nicolai@informatik.uni-duisburg.de). The research of this author was supported by
DFG.
This author is on leave from the Universitatea de stat din Moldova, Chisinau.
ADT
a vertex v # V and a set S # V we denote by d(v, S) the minimum over all distances
subgraph H of a graph G is isometric i# the distance between any
pair of vertices in H is the same as that in G.
The kth neighborhood N k (v) of a vertex v of G is the set of all vertices of distance
k to v, i.e.,
whereas the disk of radius k centered at v is the set of all vertices of distance at most
k to v:
DG (v,
Again, if no confusion arises we will omit the index G. We also write N(v) instead of
The eccentricity e(v) of a vertex v # V is the maximum value of d(v, x) taken
over all vertices x # V . The radius rad(G) of G is the minimum eccentricity of a
vertex of G, whereas the diameter diam(G) of G is the maximum eccentricity of a
vertex of G.
Now we will give a short introduction to the theory of convex geometry related
to graph theory following [16] (for more information on abstract convexity and
antimatroids the interested reader can consult [21]). Let V be a finite set and M be
a family of subsets of V . M is called alignment of V i# the family M is closed under
intersection and contains both V and the empty set. Elements of M will be considered
as convex sets. An aligned space is a pair (V, M), where M is an alignment of V .
The smallest member of M containing a given set S # V is the hull of S, denoted
by M(S). An element x of a set X # M is an extreme point of X i# X # {x} # M.
The Caratheodory number of an aligned space (V, M) is the minimum integer k
such that for all X # V , M(X) is the union of the hulls of all subsets Y of X such
that |Y | # k.
A convex geometry (antimatroid) on a finite set is an aligned space satisfying the
following additional property.
Minkowski-Krein-Milman property. Every convex set is the hull of its extreme
points.
Equivalently, a convex geometry is an aligned space satisfying the following property

Antiexchange property. For any convex set S and two distinct points x, y /
For any convex geometry the following fundamental result holds.
Theorem 1.1 (see [16]). If (V, M) is a convex geometry, then S # M i# is an
ordering #S such that x i is an extreme point of S # {x i , . , x k } for
each
For a given ordering (v 1 , . , v n ) of the vertex set of a graph E) let G i :=
}) be the subgraph of G induced by the set {v i , . , v n },
Numerous classes of graphs can be characterized in the following way. G is a
member of class G i# there is an ordering (v 1 , . , v n ) of V (G) such that v i satisfies a
certain property P in the subgraph G i ,
Theorem 1.1 suggests that such classes of graphs might be related to convex
geometries, and so it is natural to ask for a graph theoretical description of convex
sets of this aligned space. On the other hand, given a collection M of subsets of V (G),
one can ask when (V (G), M) is a convex geometry.
CONVEXITY AND HHD-FREE GRAPHS 121
For example, if property P means "is simplicial" then G is the class of chordal
graphs, i.e., the graphs without induced cycles of length at least four [7, 24]. A
vertex v of G is called simplicial i# D(v, 1) induces a complete subgraph of G, and
nonsimplicial otherwise. It is well known that a graph is chordal i# it has a perfect
elimination ordering, i.e., an ordering (v 1 , . , v n ) of V such that v i is simplicial in
G i for each 24]). Moreover, there are two linear time algorithms
for computing perfect elimination orderings of chordal graphs: LexBFS [25] and MCS
[28].
Two types of convexity in graphs have been studied most extensively, namely,
monophonic (m-) convexity and geodesic (g-) convexity (see, e.g., [4, 12, 13, 14, 15,
contains every
vertex on every induced (shortest) path between vertices in S. Both types of convexity
have a relation to simplicial vertices; a vertex v is an extreme point of a m-convex
(g-convex) set S i# v is simplicial in G(S). In [16] it is shown that G is a chordal
graph i# the monophonic alignment of G is a convex geometry, while the geodesic
alignment of G is a convex geometry i# G is a chordal graph without induced 3-fan
(i.e., a P 4 with an additional vertex adjacent to all vertices of P 4 ). To prove that the
monophonic alignment of a chordal graph is a convex geometry, the authors of [16]
show the following nice result. Every nonsimplicial vertex of a chordal graph lies on
an induced path between simplicial vertices.
For any notion of convexity on the vertex set of G, at least four degrees of local
convexity may be distinguished [17]:
D(v, 1) is convex for every vertex v of G,
is convex for every vertex v of G and every k # 1,
is convex for every convex subset S # V of G,
D(v, is convex for every convex subset S # V of G and every
k # 1.
In [16] it was shown that for m-convexity the conditions (1.1)-(1.4) are equivalent
and hold i# the graph is chordal. For g-convexity conditions (1.1)-(1.3) are not
equivalent (note that (1.3) implies (1.4) for any convexity in graphs [17]). Several
characterizations for graphs with property (1.1), (1.2), or (1.3) are given in [14, 17, 27].
Here we will mention only one result which clearly shows an analogy with chordal
graphs. Namely, a graph G fulfills the condition (1.3) i# G is a bridged graph, i.e., a
graph which contains no isometric cycles of length at least four.
Note that a vertex is simplicial i# it is not midpoint of a P 3 . Jamison and Olariu
relaxed this condition in [19] in the following way: A vertex is semisimplicial i# it is
not a midpoint of a P 4 , and nonsemisimplicial otherwise. An ordering (v 1 , . , v n ) is
a semisimplicial ordering i# v i is semisimplicial in G i for all In [19] the
authors characterized the graphs for which every LexBFS-ordering is a semisimplicial
ordering as the HHD-free graphs, i.e., the graphs which contain no house, hole, or
domino as an induced subgraph (cf. Figure 1). Moreover, the graphs for which every
MCS-ordering of an arbitrary induced subgraph F is a semisimplicial ordering of F
are the HHP-free graphs, i.e., the graphs which contain no house, hole, or "P" as an
induced subgraph (cf. Figure 1).
If a HHD-free graph G does not contain the "A" of Figure 1 as an induced
subgraph then G is called bipolarizable (HHDA-free) [23].
In this paper we introduce the notion of m 3 -convexity (a relaxation of m-convexity),
which is closely related to semisimpliciality. A subset S # V is called
122 FEODOR DRAGAN, FALK NICOLAI, AND ANDREAS BRANDST
ADT
Fig. 1.
for any pair of vertices x, y of S each induced path of length at least 3 connecting
x and y is completely contained in S. Note that a m 3 -convex set is not necessarily
connected, and it is not di#cult to see that the family of m 3 -convex sets is closed
under intersection. Observe also that a vertex v is an extreme point of a m 3 -convex
set S i# v is semisimplicial in G(S).
In this paper we present new characterizations of HHD-free and HHDA-free
graphs via m 3 -convexity. We show that for m 3 -convexity the conditions (1.1)-(1.4)
are again equivalent and hold i# the graph is HHD-free. We characterize weak bipo-
larizable graphs as the graphs for which the m 3 -convex alignment is a convex ge-
ometry, i.e., by Theorem 1.1, for which every m 3 -convex set is reachable via some
semisimplicial ordering. Again, as for chordal graphs, in weak bipolarizable graphs
every nonsemisimplicial vertex lies on an induced path of length at least 3 between
semisimplicial vertices.
Convexity in graphs is a useful tool not only for geometric characterizations of
several graph classes but also for resolving some problems related to distances in
graphs [1, 4, 5, 6, 9, 14, 22]. As an application of our results we present a simple
e#cient criterion for deciding whether a HHD-free graph E) with given
vertex radius function r has an r-dominating clique. Note that this problem
is NP-complete for weakly chordal graphs (i.e., the graphs without holes and antiholes)
[2]. From this criterion we obtain the inequality diam(G) # between the
diameter and radius of a HHD-free graph G. These results extend the known ones for
chordal, distance-hereditary, and house-hole-domino-sun-free graphs [3, 5, 8, 9, 10].
Thus, the results of the paper show strict analogies between these graphs and
chordal graphs. HHD-free, HHDA-free, and HHP-free graphs are three very natural
generalizations of the class of chordal graphs.
2. m 3 -convex sets in HHD-free graphs. In this section we characterize
HHD-free graphs as the graphs with m 3 -convex disks. Using m 3 -convexity we give
new properties of LexBFS-and MCS-orderings in HHD-free graphs and obtain known
results from [19] as corollaries.
Since a vertex v is an extreme point of a m 3 -convex set S i# v is semisimplicial
in G(S), we immediately conclude the following.
Lemma 2.1. An ordering (v 1 , . , v n ) of the vertices of a graph G is semisimplicial
The following lemma will be frequently used in what follows.
Lemma 2.2 (cycle lemma for hole-free graphs). Let C be a cycle of length at
least 5 in a hole-free graph G. Then for each edge xy of C there are vertices
in C such that xw 1 # E, each edge of a cycle is
contained in a triangle or a 4-cycle.
Proof. By induction on the length of the cycle.
CONVEXITY AND HHD-FREE GRAPHS 123
Fig. 2.
To make the paper self-contained we present the rules of the LexBFS and MCS
algorithms.
LexBFS: Order vertices of a graph by assigning numbers from | to 1. Assign
the number k to a vertex v (as yet unnumbered), which has lexically largest
vector is adjacent to the vertex
numbered i, and s
MCS: Order vertices of a graph by assigning numbers from | to 1. As the
next vertex to number pick a vertex adjacent to the most numbered vertices.
Subsequently, we will write x < y whenever in a given ordering of the vertex set
of a graph G vertex x has a smaller number than vertex y.
In what follows we will often use the following properties:
# E, then there exists a vertex d such that
c < d, db # E, and da /
If a < b < c and ac # E and bc /
# E, then there exists a vertex d such that
b < d, db # E, and da /
Evidently, (P 2) is a relaxation of (P 1). It is well known that any LexBFS-ordering
has property (P 1) [18] and any MCS-ordering has property (P 2) [28].
Theorem 2.3.
(1) Let G be a HHD-free graph and (v 1 , . , v n ) be a LexBFS-ordering of G. Then
for each G.
(2) Let G be a HHP-free graph and (v 1 , . , v n ) be a MCS-ordering of G. Then
for each G.
Proof. We prove assertion (1) by induction on i. Assume that V (G i ) is not m 3 -
convex in G but V (G j ) is so for 1. Then there must be a vertex y in G i+1
and an induced path P of length at least 3 connecting v i and y, which contains some
vertices not in G i . Choose y and P such that |P | is minimum and y is rightmost in
the LexBFS-ordering.
Case 1. The neighbor of y in P does not belong to G i .
Let x be this neighbor of y, and let y, l # 1. By
applying (P 1) to x < v i < y, we obtain a vertex v > y adjacent to v i but not to x.
The path both endpoints in G i+1 . By
the induction hypothesis V cannot be induced. Since
P is induced, all possible chords of Q must be incident to v. If v is adjacent only to
y, we obtain a forbidden induced cycle of length at least 5. So let u j be the vertex
of P # {y} closest to y on the path P and adjacent to v. We immediately conclude
l for otherwise we have a hole. Now the m 3 -convexity applied to v - u l - x - y
implies vy # E. Since the house and domino are forbidden subgraphs we conclude
l # 3 (see

Figure

2). Let j < l be the index such that vu j # E, but vu s /
ADT
x
y
Fig. 3.
we have a house; for we obtain a domino;
Case 2. The neighbor of y in P belongs to G i .
By minimality of |P | we immediately conclude y, where w, y #
applied to x < v i < w gives a vertex v > w
adjacent to v i but not to x. We may choose v with maximum number in the LexBFS-
ordering. By considering the path v - v i - x - w the m 3 -convexity implies vw # E.
Note that vy /
we obtain a house. Therefore, we have constructed a
"P" (see

Figure

3).
Case 2.1. y < v.
By applying (P 1) to v i < y < v we obtain a vertex u > v adjacent to y but not
to v i . Note that w < v < u implies u #= w. Suppose ux # E. Then (P 1) applied to
adjacent to v i but not to x, a contradiction to
the maximality of v. Thus ux /
# E. In the path v - w - y - u both endpoints have
greater numbers than y. Let
implies uv # E or uw # E. If we have both edges, then we obtain a house induced
by
we have a domino. Finally, if uw # E
and uv /
then we can replace y by u > y in P , a contradiction to the choice of y.
Case 2.2. y > v.
By applying (P 1) to w < v < y we obtain a vertex u > y adjacent to v but not
to w. If uv implies the edges ux and uy. So {v i , u, x, y, w}
induces a house. Thus uv i /
# E. Moreover, with the same arguments as in Case 2.1
we show ux /
# E. In the path u - v - w - y both endpoints have greater numbers
than v. Let i. Then the m 3 -convexity of G j+1 implies uy # E.
Thus we get a domino. This settles the proof of assertion (1).
Now to get a proof for assertion (2) we can repeat the arguments of the proof
above up to Cases 2.1 and 2.2 using (P 2) instead of (P 1).
Note that any vertex u semisimplicial in G({u, v i , . , v n }) since
G. Thus we can conclude the following.
Corollary 2.4 (see [19]).
(1) For any HHD-free graph G and any LexBFS-ordering (v 1 , . , v n ) of G vertex
v i is semisimplicial in G i ,
(2) For any HHP-free graph G and any MCS-ordering (v 1 , . , v n ) of G vertex v i
is semisimplicial in G i ,
Moreover, since there is a MCS-ordering of the "P," which is not a semisimplicial
ordering and neither holes nor a domino contain a semisimplicial vertex we immediately
conclude the following.
CONVEXITY AND HHD-FREE GRAPHS 125
Fig. 4.
Theorem 2.5 (see [19]). A graph G is HHP-free i# any MCS-ordering of any
induced subgraph F of G is a semisimplicial ordering of F .
Note that in Theorem 2.5 it is necessary to consider all induced subgraphs of a
given graph, since the graph presented in Figure 4 contains a "P" but every MCS-
ordering of this graph is a semisimplicial ordering. For LexBFS it is su#cient to
consider the graph itself, since as we will show the class of graphs where any LexBFS-
ordering gives a semisimplicial ordering is a hereditary class.
A graph is called nontrivial if it has at least two vertices.
Theorem 2.6. The following conditions are equivalent for a graph G:
(1) G is HHD-free.
(2) Any LexBFS-ordering of G is a semisimplicial ordering.
(3) For any LexBFS-ordering (v 1 , . , v n ) of G the set V (G i ) is m 3 -convex in G
for all
Every nontrivial induced subgraph of G has at least two semisimplicial vertices

Proof. It is easy to verify that none of a house, a domino, and holes contains
two semisimplicial vertices. We have to show (2) =# (1) and (2) =# (4). All other
directions are trivial or follow from Theorem 2.3.
(2) =# (1) Let G be a graph such that every LexBFS-ordering is a semisimplicial
ordering. Clearly, G cannot contain a hole or a domino since these graphs do
not have a semisimplicial vertex. Assume that G contains a house induced
by induces a C 4 and a is adjacent to b
and c. We start LexBFS at vertex a. By the rules of LexBFS both vertices
d, e are smaller than the vertices b, c. Let v i be the smaller one of d and e.
Then v i is not semisimplicial in G i . Thus G is HHD-free.
(2) =# (4) Let H be a nontrivial induced subgraph of G. Since H is HHD-free by
# (2) there must be some semisimplicial vertex v of H. Now starting
procedure LexBFS at v gives a second semisimplicial vertex.
Corollary 2.7. Let G be a HHD-free graph and v be a vertex of G. Then there
is a semisimplicial vertex u such that d(u,
Proof. We start procedure LexBFS at v. The first vertex u of the obtained
LexBFS-ordering is semisimplicial by the above theorem and fulfills d(u,
the rules of LexBFS.
We immediately conclude the following.
Corollary 2.8. In any nontrivial HHD-free graph G there is a pair of semisim-
plicial vertices u, v such that d(u,
Theorem 2.9. The following conditions are equivalent for a graph G:
(1) G is HHD-free.
(2) The disk D(v, 1) is m 3 -convex for all vertices
(3) The disks D(v, k), k # 1, are m 3 -convex for all vertices
126 FEODOR DRAGAN, FALK NICOLAI, AND ANDREAS BRANDST
ADT
Fig. 5.
(4) The set D(S, connected sets S # V .
(5) The sets D(S, are m 3 -convex for all connected sets
Proof. In every forbidden subgraph there is a vertex v such that D(v, 1) is not
we have to show only (1) =# (5).
Suppose that there is a connected set S such that D(S, 1) is not m 3 -convex. Then
there are vertices x, y in D(S, 1) and there is an induced path
such that k # 2 and at least one vertex u i is not in D(S, 1). We may choose x, y, and
P such that |P | is minimal.
Case 1.
We immediately conclude x, y /
# S. Moreover no u is adjacent to
some vertex of S. Let Q be a shortest path in G({x, y}#S) connecting x and y. Since
Q# {x, y} is completely contained in S and both P and Q are induced, the cycle C
formed by P and Q is chordless. From |P | # 4 we conclude |C| # 5-a contradiction.
Case 2. |D(S,
By minimality of |P |, we obtain
# D(S, 1), and u 2 # D(S, 1) (see Figure 5). Let
be a shortest path in G({x, y} # S) connecting x and y and define Q # := Q# {x, y}.
First consider the case 2. Note that x, u 2 /
# S, and u 1 is not adjacent to any
vertex of Q # . Since the cycle x - x is of length at least
5 the cycle lemma applied to the edge xu 1 gives z 1
a house. Hence l # 2. If u 2 z 2 # E then we obtain a house. So let u 2 z 2 /
# E. If y is
adjacent to z 2 then we have a domino. Thus l # 3 and we can apply the cycle lemma
to the edge z 1 u 2 in the cycle of length at least 5. So we
conclude which gives a domino.
Now consider the case 3. Note that x, y, u 2 /
# S. Since Q # is completely
contained in S neither u 1 nor u 3 is adjacent to any vertex of Q # . On the other hand,
the cycle x - x is of length at least 6. Thus the
cycle lemma applied to the edge u 3 y implies u 2 z l # E. If z l x /
proceed as in
the case we obtain a domino.
Thus, for every connected set S, D(S, 1) is m 3 -convex. It is easy to see that
D(S, 1) is connected too. Now, since D(S, 1), we are done by
induction on k.
Corollary 2.10. If in a HHD-free graph nonadjacent vertices x, y # N k (v) are
joined by a path P such that P # {x, y} is contained in V # D(v, k), then there is a
common neighbor of x and y in N k+1 (v) # P .
3. Weak bipolarizable graphs. Here we characterize weak bipolarizable graphs
as the graphs for which the m 3 -convex alignment is a convex geometry. Let M 3 (G)
CONVEXITY AND HHD-FREE GRAPHS 127
denote the set of all m 3 -convex sets of a graph G. For a set S # V the m 3 -convex
hull m 3 -conv(S) is the smallest member of M 3 (G) containing S.
A set H # V is homogeneous i# N(x) # any pair of vertices
x, y of H. A homogeneous set H is proper
The next lemma gives a nice criterion for checking the semisimpliciality of a
vertex.
Lemma 3.1. A vertex v of a graph G is semisimplicial in G i# the connected
components of the complement of G(N(v)) are homogeneous in G.
Proof. If v is not semisimplicial then there is a P 4 containing v as midpoint, say
belong to a common connected component C of the
complement of G(N(v)). But C is not homogeneous in G due to u 3 .
To prove the converse let C be a connected component of the complement of
G(N(v)) and suppose that C is not homogeneous in G. Then there must be vertices
a vertex z # V #C such that xz # E but yz /
# E. We may choose x and
y such that their distance in the complement of G(C) is minimal. Obviously, z #= v.
Moreover, since yz /
every vertex from N(v) # C must be adjacent to every
vertex of C, we have z /
# N(v). Thus z # N 2 (v). If xy /
y be a shortest path in the complement of
G(C). Thus xu 1 /
# E. The minimal distance of x, y now implies u 1 z /
# E. Therefore,
z
Theorem 3.2 ([23]). A graph G is weak bipolarizable i# each induced subgraph
F of G is chordal or contains a proper homogeneous set.
Let H be a proper homogeneous set in G and v # H. Then the homogeneous
reduction HRed(G,H, v) is the graph induced by V (G) # (H # {v}). Conversely, the
homogeneous extension HExt(G, v, H) of G via a graph H in v with V (H)#V
is the graph obtained by substituting v by H such that the vertices of H have the
same neighbors outside of H as v had in G.
Lemma 3.3. Let H be a proper homogeneous set of a HHD-free graph G and
(1) If x is semisimplicial in HRed(G,H, v), but not in G, then x # H, i.e.,
(2) If x # H is semisimplicial in H, but not in G, then no vertex of H is semisim-
plicial in G and v is not semisimplicial in HRed(G,H, v).
Proof. Since no P 4 contains a proper homogeneous set, we conclude that for any
4-path P of G, either P # H or |P # H| # 1.
(1) Since x is not semisimplicial in G it must be a midpoint of some 4-path P . If
H then the semisimplicity of x in HRed(G,H, v) implies |P
now we can replace the vertex of P #H by v obtaining a P 4 in HRed(G,H, v),
which contains x as a midpoint-a contradiction. Thus x # H, i.e.,
(2) If x # H is semisimplicial in H, but not in G, then no P 4 in G containing
x as a midpoint is completely contained in H. Thus P #
4-path P in G with midpoint x. Since H is homogeneous we can replace x in
P by any vertex of H. Thus no vertex of H is semisimplicial in G, and v is
not semisimplicial in HRed(G,H, v).
In [16] it is proved that in a chordal graph every nonsimplicial vertex lies on an
induced path between two simplicial vertices. Next we present a stronger result which
we will subsequently use.
Lemma 3.4. Let G be a chordal graph and be an induced path
of length at least 2, i.e., k # 3. Then there are vertices
t, such that u 1 , w 1 are simplicial and
128 FEODOR DRAGAN, FALK NICOLAI, AND ANDREAS BRANDST
ADT
is an induced path in G.
Proof. If both v 1 and v k are simplicial then we are done. So suppose that v 1 is
not simplicial.
Let M be the m-convex hull of {v 1 , . , v k } and S be the neighborhood of v 1 in
M . Obviously, S is a v 1 - v 3 -separator in M , i.e., v 1 and v 3 are in di#erent connected
components of G(M)#S. We show that S is a v 1 - v 3 -separator in G too. Assuming
the contrary there must be an induced path P in V # S joining v 1 and v 3 . Since
S is the set of neighbors of v 1 in M the neighbor of v 1 in P does not belong to M .
Thus P is an induced path between vertices of M which contains vertices of V #M ,
a contradiction to the m-convexity of M . Therefore, S is a v 1 - v 3 -separator in G.
Recall that every chordal graph is either complete or contains at least two
nonadjacent simplicial vertices [7, 24]. Thus G(M) as a chordal graph must contain
at least two simplicial vertices. Since deleting a simplicial vertex from a m-convex set
preserves m-convexity and since M is the m-convex hull of {v 1 , . , v k } we immediately
conclude that v 1 and v k are the only two simplicial vertices of M . Thus S is
complete.
1 is not simplicial and all neighbors of v 1 are contained in F := G(K #S),
where K is the connected component of G# S containing v 1 , the chordal graph F is
not complete and hence there are two nonadjacent simplicial vertices in F . By the
completeness of S at most 1 of them is in S. Thus we have a simplicial vertex u 1 in
K which is simplicial in G too. Now consider a path P connecting the vertices v 1 and
K. Then no vertex up to v 2 of an induced subpath of the
path has a neighbor in {v 3 ,    , v k }. Hence,
an induced path. For v k we proceed analogously.
Note that every simplicial vertex is semisimplicial and thus, every nonsemisim-
plicial vertex is nonsimplicial.
Lemma 3.5. Every nonsemisimplicial vertex of a weak bipolarizable graph G lies
on an induced path of length at least 3 between two semisimplicial vertices.
Proof. We prove the assertion by induction on the size of G. The assertion holds
for all graphs with at most 4 vertices since the only graph of these sizes which contains
a nonsemisimplicial vertex is the P 4 . Let x be a nonsemisimplicial vertex of G, i.e., x
is a midpoint of some P 4 .
If G is chordal then by Lemma 3.4 there is a path P of length at least 3 containing
x such that both endpoints of P are simplicial and thus semisimplicial in G.
Consequently, we are done.
Now assume that G is not chordal. Hence, by Theorem 3.2, G contains a proper
homogeneous set H.
Case 1. x # H.
Suppose that x is semisimplicial in HRed(G,H,x). Then by Lemma 3.3 (2),
vertex x is not semisimplicial in H. By the induction hypothesis x lies on an induced
path of length at least 3 between semisimplicial vertices y, z in H. By Lemma 3.3 (2),
both y and z must be semisimplicial in G too.
Now assume that x is not semisimplicial in HRed(G,H,x). By the induction hypothesis
x lies on an induced path between semisimplicial vertices y, z in HRed(G,H,x).
In particular, y, z /
# H. Thus by Lemma 3.3 (1), both y and z must be semisimplicial
in G too.
Case 2. x /
From Lemma 3.3 (1) we immediately conclude that x is not semisimplicial in
HRed(G,H, v), where v is a semisimplicial vertex in the weak bipolarizable graph H.
CONVEXITY AND HHD-FREE GRAPHS 129
By the induction hypothesis x lies on an induced path between semisimplicial vertices
y, z in HRed(G,H, v). Suppose that y is not semisimplicial in G. From Lemma 3.3
(1), we infer not semisimplicial in HRed(G,H, v) by Lemma
3.3 (2)-a contradiction. Thus both y and z are semisimplicial in G too.
To prove the next corollary we use the arguments of the proof of [16, Corollary
3.4].
Corollary 3.6. The Caratheodory number of the m 3 -convex alignment of a
bipolarizable graph is at most 2.
Proof. Let E) be a weak bipolarizable graph and S be a subset of V .
Pick an arbitrary vertex x # m 3 -conv(S). If x is semisimplicial in the subgraph
induced by m 3 -conv(S), then x # S since each extreme point of m 3 -conv(S) is in S
by the definition of the hull of S. Otherwise, by Lemma 3.5, x lies on an induced
path of length at least 3 between semisimplicial vertices of the subgraph induced by
Hence, x is in the m 3 -convex hull of two extreme points of m 3 -conv(S).
Since each extreme point of m 3 -conv(S) is in S we are done.
Subsequently, we call a vertex set S of G reachable i# there is an ordering
(v 1 , . , v k ) of V # S such that for each semisimplicial in
Theorem 3.7. The following conditions are equivalent for a graph G:
(1) G is weak bipolarizable.
(2) In every induced subgraph F of G each nonsemisimplicial vertex lies on an
induced path of length at least 3 between semisimplicial vertices of F .
Each m 3 -convex set of G is the hull of its semisimplicial vertices, i.e., (V (G),
3 (G)) is a convex geometry.
(4) A set S of G is m 3 -convex i# there is an ordering (v 1 , . , v k ) of V (G)#S such
that for each
i.e., S is reachable.
Proof. We only need to prove (4) =# (1).
Claim 1. If S is a m 3 -convex set in F := HRed(G,H, v), where H is a proper
homogeneous set of G, then
is m 3 -convex in G.
Suppose S # is not m 3 -convex in G. Then there must be vertices x, y # S # and
an induced path P of length at least 3 joining x and y such that P # S #. If
is an induced path in F of length at
least 3 joining vertices of S which has at least one vertex outside S, a contradiction
to the m 3 -convexity of S in F . Now suppose |H #P | # 2. Note that P #H #. Let
be a maximal by inclusion subpath of P completely contained in
2. If u since P #H #. Since H is homogeneous
must be adjacent to the neighbor of u k in P # P # -a contradiction. If u 1 #= x
then the same argument can be applied to u k and the neighbor of u 1 in P #P # . Now
1. For |H # P | # 2 there must be a vertex z # H # P # N(u 1 ). But now
imply some chords in P , again a contradiction.
Therefore, S # is m 3 -convex in G.
2. Every homogeneous set H of a graph G is m 3 -convex.
Let x, y be nonadjacent vertices of a homogeneous set H in G. If x has a neighbor
z outside H then yz # E, and vice versa. Thus any induced path between nonadjacent
ADT
vertices of H containing vertices from V # H must be of length 2. Consequently, H
is m 3 -convex in G.
3. Let H be a proper homogeneous set of a graph G. If S is m 3 -convex in
then it is so in G.
Since S is a subset of H we can use the same arguments as in the proof of
2.
4. If v is a simplicial vertex in a graph G then any m 3 -convex set of G#{v}
is m 3 -convex in G.
Since the neighborhood of a simplicial vertex v is complete no induced path of
length at least 3 can contain v as an inner point.
Now we prove by induction on the size of G that any graph fulfilling (4) is weak
bipolarizable, i.e., HHDA-free. Since any singleton of V (G) is a m 3 -convex set, G
possesses a semisimplicial ordering, and thus does not contain a hole or a domino.
Let F be an induced subgraph of G isomorphic to the house and K be the 3-clique
of F . Now the m 3 -convex set K must be reachable, but no vertex of F # K is
semisimplicial in F -a contradiction. Therefore, G is a HHD-free graph.
Case 1. G contains a proper homogeneous set H.
Let v be a vertex of H, F := HRed(G,H, v) and S be a m 3 -convex set in F . Then
S # as defined in Claim 1 is m 3 -convex in G and thus reachable. Hence, S is reachable
in F since each semisimplicial vertex of G is semisimplicial in every induced subgraph
containing this vertex. Therefore, F fulfills (4) and, by the induction hypothesis, is
HHDA-free. Applying the same arguments to a m 3 -convex set S of H and using
implies that H is HHDA-free. Now we conclude that G itself is HHDA-free
as the homogeneous extension of the HHDA-free graph F by the HHDA-free graph
H (see [23]).
Case 2. G has no proper homogeneous set.
Suppose G contains an "A" induced by the 4-cycle x - c - d - y - x and the
pendant vertices a, b where In what follows we prove that
in G. Thus M must be reachable, but neither c
nor d are semisimplicial in the "A"-a contradiction.
First note that every semisimplicial vertex v of G is simplicial due to Lemma
3.1. From Claim 4 we conclude that G # {v} fulfills (4) and thus, by the induction
hypothesis, is HHDA-free. Therefore, a and b are the only semisimplicial vertices of
G, and D(a, 1), D(b, 1) are complete.
. If there is a common neighbor z of a and b, then z is adjacent to all vertices
y.
Considering the cycle z - a - x - y - b - z implies the edges zx and zy. Now
{z, y, c, d} induces a house, thus zc # E or zd # E. Suppose zc /
induces a house. Hence both zc # E and zd # E.
. N(a) # N(c) and N(b) # N(d).
Let w be a neighbor of a and suppose wc /
# E. Thus w #= x, wx # E, and
# E. Since G#{a} is HHDA-free w must be adjacent to y or d. If wy # E
then the graph induced by {w, x, y, c, d} implies wd # E. Hence wd # E. But
now {a, x, w, c, d} induces a house.
. Every vertex of N(a) is adjacent to every vertex of N(b).
If w # N(a) # N(b), then w is adjacent to all vertices of N(a) # N(b) since
both D(a, 1) and D(b, 1) are complete. So suppose for the contrary that there
are nonadjacent vertices z # N(a)#N(b) and w # N(b)#N(a). Since xy # E
we have either z = x and w #= y, z #= x, and y.
CONVEXITY AND HHD-FREE GRAPHS 131
First assume z = x (analogously, y). The graph induced by {w, d, y, c, z}
implies wc # E. But now {b, y, w, z, c} induces a house. So let x #= z and
y By the same arguments as above we may assume zy # E and wx # E.
Now considering {w, d, y, z, c} gives zd # E or wc # E. By symmetry, say
wc # E. But this yields a house induced by {b, y, w, z, c}.
To complete the proof suppose that G.
Then there must be nonadjacent vertices and an induced path P of length
at least 3 joining w and z such that P #M is nonempty. Since every vertex of N(a)
is adjacent to every vertex of N(b) we conclude {w, z} # {a, b} #. Say z = a. Then
# D(a, 1). Let z # be the neighbor of z in P , i.e., z # N(a). If w # N(b) then
z # w # E gives a contradiction. Hence b. Now consider the neighbor w # of w in
P . From w # N(b) we conclude z # w # E-again a contradiction.
4. The existence of r-dominating cliques. Let r : V # N be some vertex
function defined on G. Then a set D # V r-dominates G i# for all vertices x in V #D
there is a vertex y # D such that d(x, y) # r(x). D is a r-dominating clique i# D is
complete and r-dominates G. Note that there are graphs and vertex functions r such
that G has no r-dominating clique. For some graph classes, such as chordal, distance-
hereditary, and HHDS-free graphs, there is an existence criterion for r-dominating
cliques [9, 8, 10]. In what follows we prove this criterion for HHD-free graphs. The
method is similar to the one used for chordal graphs in [9] and essentially exploits
3 -convexity of disks in HHD-free graphs.
Lemma 4.1. Let C be a clique in a HHD-free graph G and v be a vertex of G
such that for all vertices w of C the distance to v is k # 1. Then there is a vertex u
at distance k - 1 to v which is adjacent to all vertices of C.
Proof. We prove the assertion by induction on k. For there is nothing to
show. Let x be a vertex of N k-1 (v) adjacent to a maximal number of vertices of C.
Suppose that there is some vertex a # C which is not adjacent to x, and let y be a
neighbor of a in N k-1 (v). By the choice of x there must be a vertex b # C adjacent
to x but not to y. Thus we have the path x - b - a - y of length 3 between vertices
x, y of D(v, k - 1), which contains vertices a, b outside of D(v, k - 1). By Theorem 2.9
by applying the induction hypothesis
to the clique {x, y} we obtain a common neighbor u of x, y in N k-2 (v). Therefore we
have constructed a house-a contradiction.
In a similar way we can prove the following lemma.
Lemma 4.2. If x, y, v are vertices of a HHD-free graph G such that d(x,
d(y, #, then there is a vertex u # N(x)#N(y)#
Define the projection of a vertex v to a set S by
and the projection of a set C to a set S by P roj(C, S) := # v#C P roj(v, S).
Lemma 4.3. Let u, v be vertices of a HHD-free graph. Then for any vertex
x in D(v, there is a shortest path between u and x going through the projection
Proof. If {u} and there is nothing to show.
1. Choose an arbitrary vertex w # P roj(u, D(v, k)) and assume
be a shortest path connecting u and x, and let
z be the vertex of V (P closest to u on the path P (see Figure 6). Thus
ADT
z
x D(v,
z
x D(v,
a
c
Fig. 6.
then we are done. So assume
z /
implying d(u, z) > d(u, w). Note that zw /
is a contradiction. Thus by Corollary 2.10 there is a common neighbor a of w and
z in N k+1 (v) # P implying that d(u, z) # d(u, w) 2.
Moreover,
applying
Lemma 4.2 to z, w, and v gives a common neighbor b of z, w in N k-1 (v). By distance
requirements ab /
applied to {a, w} and u, yields a
common neighbor c of a, w at distance d(u, w) - 1 to u. Thus neither cz # E nor
Consequently, {a, b, c, w, z} induces a house.
be subsets of V . The sets U 1 , U 2 form a join i# any vertex of U 1 is
adjacent to any vertex of U 2 .
Lemma 4.4. Let G be a HHD-free graph and xy be an edge outside of D(v, k).
Moreover, assuming P roj(x, D(v, implies that the sets P roj
Proof. We will present the proof for the equidistant case, i.e., d(x,
The cases d(x, can be handled in a similar (even
way. Let A := P roj(x, D(v, k)) #P roj(y, D(v, k)), B := P roj(x, D(v, k)) #A,
and C := P roj(y, D(v, k)) #A.
Suppose we have
contradiction to Corollary 2.10. Therefore, w x w y # E. Let b (c) be the neighbor of w x
(w y ) in a shortest path P x
Lemma 2.2 applied to the edge w x w y in the cycle induced by the vertices of P x and
induces a house where s is a common neighbor
of w x w y in N k-1 (v) due to Lemma 4.1. Consequently, either
Finally, suppose w
# E. Consider the three vertices
v. By Corollary 2.10 there is a common neighbor z of w and w x at distance
to v and d(x, w) - 1 to x. By Lemma 4.2 there is a common neighbor u of w
and w x at distance k - 1 to v. Let t be the neighbor of w on a shortest path joining
w and y. Since w x /
# A we have tw x /
# E. By distance requirements zu, tu /
induces a house. So assume tz /
consider the cycle
C formed by w and by the shortest paths joining t, y and z, x. Obviously |C| # 5.
Applying the circle lemma to edge zw yields the edge ts, where s is the neighbor of
CONVEXITY AND HHD-FREE GRAPHS 133
z in the shortest path between x and z. By distance requirements {s, t, z, w, w x , u}
induces a domino. Therefore, A and B form a join.
Lemma 4.5. Let G be a HHD-free graph and C be a clique such that C #
D(v, #. Then there is some vertex u # N k-1 (v) adjacent to all vertices of
Proof. Choose a maximal clique C # in P roj(C, D(v, k)) containing C # D(v, k).
By Lemma 4.1 there is a vertex a in N k-1 (v) adjacent to all vertices of C # . Choose
such a vertex a with a maximal number of neighbors in P roj(C, D(v, k)) and suppose
that there is some vertex y # P roj(C, D(v, k)) # C # nonadjacent to a. Since C # is
maximal there is a vertex w # C # which is not adjacent to y. Note y /
# C. Thus
there is a common neighbor z of y and w in N k+1 (v) (either z # C or the existence
of z follows from Corollary 2.10). Now applying Lemma 4.2 to w, y gives a common
neighbor b of w and y in N k-1 (v). By distance requirements za, zb /
# E. If ab # E,
then {a, b, y, z, w} induces a house. If ab /
# E, then we can apply Lemma 4.2 to a, b
yielding a common neighbor c of a, b in N k-2 (v). But now {c, a, b, y, w, z} induces a
domino.
Theorem 4.6. Let G be a HHD-free graph and r : V # N be a vertex function
on G. Then G has a r-dominating clique i# for all vertices
Proof. Obviously, if G has a r-dominating clique then the inequality is fulfilled.
To prove the converse let (v 1 , . , v n ) be any ordering of V and suppose that there is
a clique C which r-dominates {v 1 , . , v i-1 } but not v i . Thus d(v i , C) # r(v
there is
some vertex c # C such that d(c, v k
Lemma 4.3 there is a shortest path joining c and
going through B. Thus v k is r-dominated by some vertex of B.
Now choose
a vertex x k in D(v k , r(v k Lemma 4.3 there is a shortest
path joining c and x k which contains a vertex of B, say y
since both c and x k are contained in the m 3 -convex set D(v k , r(v k )).
and we are done since v k is r-dominated
by y k . So let d(c, x k 2. Again, if then we are done. Thus
immediately conclude
4.2 applied to
neighbor a of c and x k at distance r(v k ) -1 to v k . Since
applying Lemma 4.1 to the edge x k y k and to v i yields a common neighbor b of x k and
y k at distance r(v i ) to v i . By distance requirements the set {a, b, x k , y k , c} induces a
house-a contradiction. Thus y k r-dominates v k and we are done.
Let C # be a maximal clique in P roj(C, D(v i , r(v
1). By Lemma 4.5 there is a vertex a in N r(v i adjacent to all
vertices of B. Define C # := C # {a}.
2. C # r-dominates
Obviously, a r-dominates v i . Suppose there is some vertex v k , k # i - 1 which is
not r-dominated by C # . By r-dominated by B. More exactly, there is a
vertex c # C and a vertex y r-dominating
ADT
is maximal there must be a vertex w # C # nonadjacent to y k . By
Lemma 4.4 both vertices y k , w are contained in the projection of c.
Let z be a common neighbor of w and y k at distance d(c, w) - 1 to c obtained
from Lemma 4.2. If d(y k , c) # 3 then the m 3 -convexity of D(v k , r(v k )) implies z #
Now we can apply Lemma
4.1 to the edge y k z obtaining a common neighbor s of y k and z at distance r(v k
to v k . By distance requirements sw, sa, az /
# E. Thus {s, w, a, z, y k } induces a house.
In a similar way we can handle the case 2. If z #
then we proceed as above. So by assuming d(z, v k ) > r(v k ) we have
Now we can apply Lemma 4.2 to
obtaining a common neighbor b of c, y k at distance r(v k ) - 1 to v k . By distance
requirements bw, ba /
# E. Thus {c, b, z, y k , a, w} induces a domino.
Consequently we have constructed a clique which r-dominates {v 1 , . , v i }. Induction
on i settles the proof.
Corollary 4.7. For a HHD-free graph G we have
Proof. Suppose that diam(G) < 2(rad(G) - 1). Then by Theorem 4.6 for r(v) :=
there exists a r-dominating clique C in G. Hence, any vertex v of
C has e(v) # rad(G) - 1, a contradiction to the definition of the radius.

Acknowledgments

. The authors are indebted to two anonymous referees for
constructive comments improving the presentation.



--R

Perfect elimination orderings of chordal powers of graphs
Domination problems on permutation and other graphs


Centers of triangulated graphs

On rigid circuit graphs
Dominating cliques in distance-hereditary graphs


"Graphs and Combinatorics,"
Convex sets in graphs II: Minimal path convexity
Ensemble convexes dans les graphes I

On diameters and radii of bridged graphs
Convexity in graphs and hypergraphs
On local convexity in graphs
Algorithmic Graph Theory and Perfect Graphs
On the semi-perfect elimination
A perspective on abstract convexity: Classifying alignment by varieties

The Interval Function of a Graph

Triangulated graphs and the elimination process
Algorithmic aspects on vertex elimination on graphs

Conditions for invariance of set diameters under d- convexification in a graph
Simple linear time algorithms to test chordality of graphs
--TR

--CTR
J. Sawada, Oracles for vertex elimination orderings, Theoretical Computer Science, v.341 n.1, p.73-90, 5 September 2005
Victor Chepoi , Feodor Dragan, Finding a central vertex in an HHD-free graph, Discrete Applied Mathematics, v.131 n.1, p.93-111, 6 September
convexity;weak bipolarizable graphs;chordal graphs;convex geometry;semisimplicial ordering;antimatroid;HHD-free graphs;lexicographic breadth first search;dominating clique problem