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

1/--страниц