close

Вход

Забыли?

вход по аккаунту

?

265

код для вставкиСкачать
Unit and Proper Bitolerance
Digraphs
Randy Shull
DEPARTMENT OF COMPUTER SCIENCE
WELLESLEY COLLEGE
WELLESLEY, MA 02181 USA
Ann N. Trenk
DEPARTMENT OF MATHEMATICS
WELLESLEY COLLEGE
WELLESLEY, MA 02181 USA
ABSTRACT
~ are
In this paper we prove that the following statements about a directed graph G
~ is a unit bitolerance digraph, (2) G
~ is a proper bitolerance digraph, and
equivalent. (1) G
~ is an interval catch digraph
(3) the digraph obtained by reversing all arc directions of G
(also known as a point-core digraph). This result combined with known algorithms for
recognizing interval catch digraphs, gives the first known polynomial-time algorithm for
c 1997 John Wiley & Sons, Inc.
recognizing a class of (bi)tolerance digraphs. 1. INTRODUCTION
1.1. Background
Tolerance graphs are a generalization of interval graphs in which some overlap of intervals is
allowed before an edge is formed between the vertices that correspond to those intervals. They
were introduced in [7] and studied more extensively in [8]. Formally, a graph G is a bounded
tolerance graph if each vertex v ∈ V (G) corresponds to a real interval I(v) and a tolerance
tv ≤ |I(v)| so that vertices x and y are adjacent in G iff |I(x) ∩ I(y)| ≥ min{tx , ty }.
Bogart and Trenk [4] introduced the class of bounded bitolerance graphs in which each interval receives both a left and a (potentially different) right tolerance. Directed versions of
tolerance and bitolerance graphs are introduced in [3], motivated by the observation that when
an adjacency occurs between vertices x and y in a tolerance graph, it could be caused by the
Journal of Graph Theory Vol. 24, No. 2, 193 199 (1997)
c 1997 John Wiley & Sons, Inc.
CCC 0364-9024/97/020193-07
194 JOURNAL OF GRAPH THEORY
intersection I(x) ∩ I(y) exceeding y's tolerance, or exceeding x's tolerance, or both. Thus
in a bounded (bi)tolerance digraph, there is an arc from x to y if and only if I(x) ∩ I(y)
exceeds y's tolerance.
The unit and proper variations of interval graphs and tolerance and bitolerance graphs and
digraphs have received a great deal of study, and are the subject of this paper. Whenever a class of
graphs or digraphs is defined via a representation involving intervals, there is a natural subclass
defined by insisting that all the intervals in the representation have the same length. This is the
‘‘unit’’ subclass. The ‘‘proper’’ subclass consists of the (di)graphs with representations in which
no interval properly contains another. Clearly the unit subclass is contained in the proper subclass.
A question which has been studied by several authors is, are they equal?
Roberts [16] proved that the classes of unit and proper interval graphs are indeed equal. Bogart
et al. [1] show that the classes of unit and proper tolerance graphs are unequal. Jacobson and
McMorris [9] prove that the classes of unit and proper sum-tolerance graphs are equal. (The
definition of sum-tolerance graphs is the same as that of bounded tolerance graphs except that
‘‘min{tx , ty }’’ is replaced by ‘‘tx + ty .’’) Most recently, Bogart and Isaak [2] have proven that
the classes of unit and proper bitolerance graphs are equal. In Theorem 6 of this paper, we prove
the classes of unit and proper bitolerance digraphs are equal, which generalizes the result in [2].
1.2. Preliminaries
~ (abbreviated digraph) is composed of a vertex set V and an arc set A(G)
~
A directed graph G
of ordered pairs of distinct elements of V . We do not consider digraphs with loops or multiple
~ If (x, y) ∈ A(G)
~ then
arcs, except that it is possible for both (x, y) and (y, x) to be arcs of G.
we say that x is the initial endpoint of the arc (x, y). If G is a directed graph, the reverse
~ r ) if and only if
~ (denoted G
~ r ) is the digraph on the same vertex set with (x, y) ∈ A(G
of G
~
(y, x) ∈ A(G).
~ is a bounded bitolerance digraph if it has a representation
Definition 1.
A directed graph G
~ there corresponds a real interval I(v) =
I(v); lt(v), rt(v) as follows. To each vertex v ∈ V (G)
[le(v), re(v)], a left tolerant point lt(v) ∈ I(v), and a right tolerant point rt(v) ∈ I(v), so that
~ if and only if
for distinct vertices x and y, (x, y) ∈ A(G)
• I(x) ∩ I(y) ⊆
/ [le(y), lt(y)) and
• I(x) ∩ I(y) ⊆
/ (rt(y), re(y)].
Such a representation is called a bitolerance representation.
Intuitively, vertex y's interval will tolerate an overlap with the interval I(x) as long as the
overlap stays completely to the left of the left tolerant point lt(y) or completely to the right of the
right tolerant point rt(y).
We next define several classes of bounded bitolerance digraphs which will be important in our
main result about unit and proper bitolerance digraphs. The definition of interval catch digraphs
is taken from [15], while our definition of point-core digraphs is a directed graph analog of the
point-core graphs in [11].
~ is a unit bitolerance digraph if it has a bitolerance representation I(v); lt(v), rt(v)
A digraph G
in which all the interval lengths |I(v)| are equal. We call this representation a unit bitolerance
~ is a proper bitolerance digraph if it has a bitolerance representation
representation. Digraph G
I(v); lt(v), rt(v) in which no interval properly contains another, and we call this representation a
~ is one with a bitolerance representation
proper bitolerance representation. A point-core digraph G
BITOLERANCE DIGRAPHS 195
~ A digraph G
~ is a interval catch
I(v); lt(v), rt(v) for which lt(v) = rt(v) for all v ∈ V (G).
~ corresponds to a real interval
digraph if it can be represented as follows: each vertex v ∈ V (G)
~ iff p(y) ∈ I(x).
I(v) and a point p(v) ∈ I(v) so that for distinct vertices x and y, (x, y) ∈ A(G)
It is easy to check that these last two classes are identical. We record this observation as
a lemma.
Lemma 2.
~ is a point-core digraph if and only if it is an interval catch digraph.
A digraph G
2. MAIN RESULTS
The next lemma generalizes a result in [11] about undirected graphs.
Lemma 3.
~ is a unit bitolerance digraph if and only if G
~ r is a point-core digraph.
A digraph G
Our proof of Lemma 3 will be purely algebraic. For a geometric proof one can associate to
vertex v the trapezoid T (v) with corners at the coordinate points (le(v), 1), (rt(v), 1), (lt(v), 0),
(re(v), 0) and apply the methods used in [1] and [11].
Proof. (⇒) For the forward direction, we produce a function F that maps unit bitolerance
~ = G
~ r for all unit bitolerance didigraphs to point-core digraphs, and then show that F (G)
~
graphs G.
~
Let G be a unit bitolerance digraph and choose a unit bitolerance representation I(v); lt(v), rt(v)
~ Since the representation is unit, let c = |I(v)| = re(v) − le(v) for all v ∈ V (G).
~ We
of G.
0
0
~ = F (G)
~ with bitolerance representation I (v); lt (v), rt0 (v)
construct a point-core digraph H
~ as follows. Let V (H)
~ = V (G)
~ and for each v ∈ V (H)
~
from the unit bitolerance digraph G
0
0
0
0
0
0
let I (v) = [le (v), re (v)] where le (v) = lt(v), re (v) = rt(v) + c, lt (v) = le(v) + c, and
rt0 (v) = re(v).
~ lt0 (v) = rt0 (v) since c = re(v) − le(v). In addition,
First note that for all v ∈ V (H),
0
0
le (v) = lt(v) ≤ re(v) = rt (v) (where the inequality follows from lt(v) ∈ I(v)) and similarly,
lt0 (v) = le(v) + c ≤ rt(v) + c = re0 (v). Hence lt0 (v)(= rt0 (v)) is inside the interval I 0 (v).
~ and the function F does indeed
Thus the representation given is a point-core representation of H
map unit bitolerance digraphs into point-core digraphs.
~ =G
~ r (i.e., F (G)
~ =G
~ r ) by demonstrating that (x, y) ∈ A(G)
~ iff (y, x) ∈
Now we show H
~
~
A(H). First suppose (x, y) ∈ A(G). By Definition 1, we know (i) I(x) ∩ I(y) ⊆
/ [le(y), lt(y))
~ Again using
and (ii) I(x) ∩ I(y) ⊆
/ (rt(y), re(y)]. For a contradiction, assume (y, x) ∈
/ A(H).
Definition 1, we know that either (a) I 0 (x) ∩ I 0 (y) ⊆ [le0 (x), lt0 (x)) or (b) I 0 (x) ∩ I 0 (y) ⊆
(rt0 (x), re0 (x)].
If re0 (y) ≥ lt0 (x) = rt0 (x) ≥ le0 (y) then lt0 (x) = rt0 (x) ∈ I 0 (x) ∩ I 0 (y), contradicting (a)
and (b) above. Since lt0 (x) = rt0 (x), one of the two cases below must hold.
Case 1. re0 (y) < lt0 (x). In this instance, rt(y) + c < le(x) + c and hence rt(y) < le(x).
But then I(x) ∩ I(y) ⊆ (rt(y), re(y)], contradicting (ii) above.
Case 2. rt0 (x) < le0 (y). In this instance, re(x) = rt0 (x) < le0 (y) = lt(y), and thus
I(x) ∩ I(y) ⊆ [le(y), lt(y)), contradicting (i) above.
~ implies (y, x) ∈ A(H).
~
We have just shown that (x, y) ∈ A(G)
196 JOURNAL OF GRAPH THEORY
FIGURE 1. A diasteroidal triple {x, y, z}.
~ By Definition 1 we know that (i) I(x) ∩ I(y) ⊆ [le(y), lt(y))
Now suppose (x, y) ∈
/ A(G).
or (ii) I(x) ∩ I(y) ⊆ (rt(y), re(y)]. We start by showing that either (a) re(x) < lt(y) or (b)
le(x) > rt(y) and then we consider these two cases separately.
If I(x) ∩ I(y) = ∅, then either I(x) lies entirely to the left of I(y), in which case (a) holds,
or I(x) lies entirely to the right of I(y), in which case (b) holds. If I(x) ∩ I(y) =
/ ∅, then (i)
implies (a) and (ii) implies (b). Thus either (a) or (b) must hold.
Case a. re(x) < lt(y).
In this instance, rt0 (x) = re(x) < lt(y) = le0 (y). Hence I 0 (x) ∩ I 0 (y) ⊆ (rt0 (x), re0 (x)], so
~
(y, x) ∈
/ A(H).
Case b. le(x) > rt(y).
In this instance, lt0 (x) = le(x) + c > rt(y) + c = re0 (y) which means that I 0 (x) ∩ I 0 (y) ⊆
0
~
[le (x), lt0 (x)), so (y, x) ∈
/ A(H).
~ iff (y, x) ∈ A(H),
~ thus H
~ =G
~ r , as desired.
In summary, (x, y) ∈ A(G)
~ be a point-core digraph. Choose a representation of H
~ in which vertex
(⇐) Conversely, let H
0
0
0
0
v corresponds to the interval I (v) = [le (v), re (v)] and tolerant point lt (v) = rt0 (v) ∈ I 0 (v).
~ (This
Choose a constant c so that le0 (v) + c > lt0 (v) and rt0 (v) + c > re0 (v) for all v ∈ V (H).
is possible since our graphs are finite).
~ with vertex set V (G)
~ = V (H)
~ as follows. For
Form a new bounded bitolerance digraph G
0
0
0
~ let le(v) = lt (v) − c, re(v) = rt (v), lt(v) = le (v), rt(v) = re0 (v) − c, and
each v ∈ V (G),
I(v) = [le(v), re(v)].
~ is indeed a bounded bitolerance digraph.
Note that lt(v), rt(v) ∈ I(v) by our choice of c, so G
~ is
In fact, the representation is unit since re(v) − le(v) = rt0 (v) − lt0 (v) + c = 0 + c = c, so G
~
~
a unit bitolerance digraph. Finally, observe that again H = F (G) because the construction here
~ =G
~ r as before.
is the inverse of that in the first half of the proof. Thus H
We next introduce the concept of a diasteroidal triple, which is a directed graph analog of an
asteroidal triple. For a background on asteroidal triples, see [6].
~ be a digraph. An x − y chain C:
~ x = a0 , a1 , a2 , . . . , an = y in G
~ is a digraph with
Let G
~
~ so that for each
~
vertex set V (C) = {a0 , a1 , a2 , . . . , an } ⊆ V (G) and arc set A(C) ⊆ A(G)
~ and these
i = 0, 1, 2, . . . , n − 1, exactly one of the arcs (ai , ai+1 ), (ai+1 , ai ) is an arc of C,
~ An x − y chain C:
~ x = a0 , a1 , a2 , . . . , an = y is called z-avoiding
are the only arcs of C.
~ if ai is the initial endpoint of an arc of C,
~ then
~ and (ii) for all ai ∈ V (C),
if (i) z ∈
/ V (C)
~
(ai , z) ∈
/ A(G). The set {x, y, z} forms a diasteroidal triple if there is a z-avoiding x − y chain,
~ In Figure 1, the set {x, y, z} forms
an x-avoiding y − z chain, and a y-avoiding x − z chain in G.
BITOLERANCE DIGRAPHS 197
a diasteroidal triple. Note that the x − y chain with arcs {(x, v), (v, y)} is not z-avoiding, but the
x − y chain {(x, v), (y, v)} is z-avoiding.
In [15], Prisner gives the following characterization of interval catch digraphs.
Theorem 4 (Prisner).
triple.
A digraph is an interval catch digraph if and only if it has no diasteroidal
We need one more lemma before proving our main result.
~ is a proper bitolerance digraph, then G
~ has a proper bitolerance representation
Lemma 5. If G
in which the endpoints of all intervals are distinct.
~ If the endpoints
Proof. Choose a proper bitolerance representation I(v); lt(v), rt(v) of G.
of all intervals I(v) are distinct, we are done. Otherwise, let > 0 be the minimum of all
non-zero quantities: {|le(x) − le(y)|, |re(x) − re(y)|, |re(x) − le(y)|, |le(x) − lt(y)|, |le(x) −
rt(y)|, |re(x) − lt(y)|, |re(x) − rt(y)|}, where x and y range over all pairs of distinct vertices
~
of G.
First consider the case in which two or more intervals of the representation are identical. Let
~ Change I(xj )
t ≥ 2 be the maximum such that I(x1 ) = I(x2 ) = · · · = I(xt ) for xi ∈ V (G).
0
to I (xj ) = [le(xj ) − /(j + 1), re(xj ) + /(t + 2 − j)] for each j, and leave the rest of the
representation (including lt(xj ) and rt(xj )) unchanged. Once can readily check that the new
~ yet has one fewer set of identical intervals.
representation is proper and yields the same digraph G,
Calculate the new and continue this process until no more identical intervals remain.
Now suppose intervals I(v) and I(w) share an endpoint. Since the representation is proper
and we have eliminated all identical intervals, it must be the case that either le(v) = re(w)
or le(w) = re(v). Without loss of generality, assume the former. Calculate as above and
replace the interval I(v) with I 0 (v) = [le(v) − /2, re(v)]. Again it is easy to check that the new
~ Calculate the new and continue until
representation is proper and yields the same digraph G.
no shared endpoints remain.
Theorem 6.
~
The following are equivalent statements about a digraph G.
~ is a unit bitolerance digraph
(1.) G
~ is a proper bitolerance digraph
(2.) G
~ r is an interval catch digraph.
(3.) G
Proof. (1 ⇒ 2) This follows immediately from the fact that any unit representation is also
proper.
~ be a proper bitolerance digraph with proper representation I(v) = [le(v), re(v)];
(2 ⇒ 3) Let G
~ r has no diasteroidal triple, then apply Prisner's Theorem. For
lt(v), rt(v). We will show that G
~ r . Using Lemma 5, we
a contradiction, assume that {x, y, z} were a diasteroidal triple of G
~ x = a0 , a1 , a2 , . . . , an = y be a z-avoiding
may assume le(x) < le(z) < le(y). Let C:
r
~
x − y chain in G . Choose i as the minimum index for which le(ai ) < le(z) < le(ai+1 )
(such an i exists because le(a0 ) < le(z) < le(an )). Since the representation is proper we
know I(ai ) ∩ I(ai+1 ) ⊆ I(ai ) ∩ I(z) and I(ai ) ∩ I(ai+1 ) ⊆ I(z) ∩ I(ai+1 ). Thus (i) if
~ then (z, ai+1 ) ∈ A(G),
~ and (ii) if (ai+1 , ai ) ∈ A(G)
~ then (z, ai ) ∈ A(G),
~
(ai , ai+1 ) ∈ A(G)
using Definition 1. One of these two possibilities must occur by the definition of an x − y chain,
~ being z-avoiding in G
~ r.
but each contradicts C's
r
~ r is an interval catch digraph, prov~
Thus G has no diasteroidal triple. Now by Theorem 4, G
ing (3).
198 JOURNAL OF GRAPH THEORY
FIGURE 2. Four classes and their recognition times (if known).
~ r be an interval catch digraph. Then by Lemma 2, G
~ r is a point-core digraph,
(3 ⇒ 1) Let G
~ is a unit bitolerance digraph.
and finally by Lemma 3, G
3. RECOGNITION ALGORITHMS
Our characterization of unit and proper bitolerance digraphs in Theorem 6 leads to an efficient
~ with vertices ordered
recognition algorithm. Recall that the adjacency matrix A of a digraph G
~ The augmented
v1 , v2 , . . . , vn is the 0, 1-matrix with Ai,j = 1 if and only if (vi , vj ) is an arc of G.
adjacency matrix A∗ is constructed from A by placing 1's on the main diagonal (which corresponds
to adding a loop at each vertex). Maehara [13] characterizes the class of interval catch digraphs
~ whose augmented adjacency matrices A∗ have the consecutive ones property
as those digraphs G
for rows, without allowing column permutations. Testing A∗ for the consecutive 1's property can
~ and m = |A(G)|.
~ Hence by Theorem
be achieved in O(n + m) time (see [6]), where n = |V (G)|
6, we have an O(n + m) algorithm for recognizing the classes of unit and proper bitolerance
digraphs.
~ is an interval catch digraph and
Furthermore, Maehara's algorithm is constructive. If G
~ which yields an augmented adjacency matrix A∗ with
v1 , v2 , . . . , vn is an ordering of V (G)
the consecutive one's property for rows, then one can construct an interval catch representation
~ by taking p(vk ) = k and I(vk ) = [a(vk ) − 1 , b(vk ) + 1 ], where a(vk ) = min{i|A∗ = 1}
of G
ki
2
2
and p(vk ) ∈ I(vk ) since A∗ has 1's along the main diagonal. Since our proof of Lemma 3 is
also constructive, we obtain a recognition algorithm for the classes of unit and proper bitolerance digraphs which constructs a unit bitolerance representation in the case that the recognition
algorithm answers in the affirmative.
In related work, Sen et al. [17] generalize Maehara's work to give an algorithm that recognizes
both interval catch digraphs and interval point digraphs, where the latter class is the interval
catch digraphs without the requirement that p(v) ∈ I(v). An alternative algorithm for recogniing
interval catch digraphs is given by Prisner [14].
We conclude with an observation about the difficulty of recognizing classes of tolerance
graphs. At present the only classes with efficient recognition algorithms are bounded bitolerance
graphs (see [5], [10], or [12]) and unit (= proper) bitolerance digraphs. In particular, no efficient
recognition algorithms are known for the classes of bounded bitolerance digraphs or for unit (=
proper) bitolerance graphs (see Figure 2). Thus it is unclear at this point whether directed or
undirected classes are easier to recognize.
ACKNOWLEDGMENTS
The authors are grateful to an anonymous referee for improving the proof of Lemma 3.
BITOLERANCE DIGRAPHS 199
References
[1]
K. Bogart, P. Fishburn, G. Isaak, and L. Langley, Proper and unit tolerance graphs. Discrete Appl.
Math. 60 (1995), 99–117.
[2]
K. P. Bogart and G. Isaak, Proper and unit bitolerance orders, Discrete Math., to appear.
[3]
K. P. Bogart and A. N. Trenk, Bounded bitolerance digraphs, preprint.
[4]
K. P. Bogart and A. N. Trenk, Bipartite tolerance orders. Discrete Math. 132 (1994), 11–22.
[5]
S. Felsner, M. Habib, and R. Möhring, On the interplay between interval dimension and ordinary
dimension. SIAM J. Discrete Math. 7 (1994), 32–40.
[6]
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, San Diego (1980).
[7]
M. C. Golumbic and C. L. Monma, A characterization of interval graphs with tolerances. Congress.
Numer. 35 (1982), 321–331.
[8]
M. C. Golumbic, C. L. Monma, and W. T. Trotter, Tolerance graphs. Discrete Appl. Math. 9 (1984),
157–170.
[9]
M. S. Jacobson and F. R. McMorris, Sum-tolerance proper interval graphs are precisely sum-tolerance
unit interval graphs. J. Combinatorics, Information and System Sciences 16 (1991), 25–28.
[10]
L. Langley, A recognition algorithm for orders of interval dimension 2. Discrete Appl. Math. 60 (1995),
257–266.
[11]
L. J. Langley, Interval tolerance orders and dimension, PhD thesis, Dartmouth College, July (1993).
[12]
T. Ma, Algorithms on special classes of graphs and partially ordered sets, PhD thesis, Vanderbilt
University, August (1990).
[13]
H. Maehara, A digraph represented by family of boxes or spheres. J. Graph Theory 8 (1984), 431–439.
[14]
E. Prisner, Algorithms for interval catch digraphs. Discrete Appl. Math. 51 (1994), 147–157.
[15]
E. Prisner, A characterization of interval catch digraphs. Discrete Math. 73 (1994), 285–289.
[16]
F. S. Roberts, Indifference graphs, in F. Harary (Ed.), Proof Techniques in Graph Theory (pp. 139–146),
Academic Press, New York (1969).
[17]
M. Sen, S. Das, A. B. Roy, and D. B. West, Interval digraphs: an analogue of interval graphs. J. Graph
Theory 13 (1989) 189–202.
Received August 22, 1996
Документ
Категория
Без категории
Просмотров
2
Размер файла
95 Кб
Теги
265
1/--страниц
Пожаловаться на содержимое документа