New Characterizations of Digraphs Represented by Intervals Barun K. Sanyal DEPARTMENT OF MATHEMATICS UNIVERSITY COLLEGE, RAIGANJ WEST BENGAL, INDIA, PIN-733 134 Malay K. Sen DEPARTMENT OF MATHEMATICS NORTH BENGAL UNIVERSIPr: DARJEELING WEST BENGAL, INDIA, PIN-734 430 ABSTRACT We present new characterizations of interval digraphs, interval graphs, and indifference digraphs, using linear orderings of edges and vertices. 0 1996 John Wiley & Sons, Inc. 1. INTRODUCTION The intersection digraph of a family F of ordered pairs of sets {(Sv, T,): v E V} is the digraph D(V,E ) such that vw E E if and only if S, n T, # 4. The sets S, and T, are called the source sets and terminal sets of V. This concept is a natural analogue of the notion of intersection graphs and was introduced independently in different contexts by Beineke and Zamfirescu [l] and Sen et al. (81. When the sets are intervals on the real line, it is an interval digraph. Interval digraphs were introduced and characterized in [S]. A digraph D ( V , E ) is an indifleerence digraph if there exists an ordered pair of real valued functions (f,g) on the vertices satisfying ww E E * If(v) - g(W)l 5 1. These were characterized in [9] and were shown to be equivalent to unit interval digraphs and proper interval digraphs. Unit interval digraphs are interval digraphs with interval representations such that all the source and terminal intervals have unit length. Proper intervat digraphs are interval digraphs with representation in which no source interval Journal of Graph Theory Vol. 22, No. 4, 297-303 (1996) Q 1996 John Wiley & Sons, Inc. CCC 0364-9024/96/040297-07 298 JOURNAL OF GRAPH THEORY properly contains another source interval and no terminal interval properly contains another terminal interval. Indifference digraphs were also characterized in terms of a monotone consecutive arrangement (MCA) of its adjacency matrix in [9]. A (0, 1)-matrix is said to have a monotone consecutive arrangement if there exist independent row and column permutations exhibiting the following structure: the 0’s of the resulting matrix can be labeled R or C such that every position above and to the right of an R is an R, and every position below and to the left of a C is a C. It was proved that a digraph is an indifference digraph if and only if its adjacency matrix has an MCA. Most characterizations of interval graphs and interval digraphs so far involve an order of their vertices [5, 6, 81. In this paper, we first pose the question, “Is there any ordering among the edges of a (di)graph that characterizes an interval (di)graph?’ In Section 2, we answer this question in the affirmative. We introduce the notion of a consistent ordering of the edge set of a (di)graph and prove that a (di)graph is an interval (dilgraph if and only if its edge set has a consistent ordering. The set E of all edges of a digraph D(V,E ) will be said to have a consistent ordering if E has a linear ordering (<) such that for pq, T S , ~t q, E E (i) p q < T S < p u =+ p s E E ( q # u),and (ii) p q < T S < t q + T S E E ( p # t ) . (We write p q E E for an edge from a vertex p to a vertex q). We prove that a digraph is an interval digraph if and only if its edge set has a consistent ordering. In [lo] it was shown that an interval digraph is actually a generalization of an interval graph in the sense that an undirected graph is an interval graph if and only if the corresponding symmetric digraph with loops at all vertices is an interval digraph. From this viewpoint we appropriately modify the definition of consistent ordering of the edge set of an undirected graph and obtain a corresponding characterization of an interval graph. In the last section of this paper a characterization of indifference digraphs is given. We first observe that a matrix having an MCA evidently has the consecutive 1’s property for columns. A (0, 1)-matrix is said to have the consecutive 1’s property for columns if its rows can be permuted so that the 1’s in each column appear consecutively. Tucker [ 111 gave a complete characterization of consecutive 1’s property of columns of a (0, 1)-matrix in terms of some forbidden configurations of the matrix. Again, Lin and West [4] obtained a characterization of an indifference digraph in terms of forbidden submatrices of its adjacency matrix. As observed by Tucker, when a (0, 1)matrix is treated as the adjacency matrix of a bipartite graph between vertices representing the rows and columns in the obvious way, the consecutive 1’s property for the columns of the matrix corresponds to ordering the row vertices so that the neighborhood of each column vertex is one interval in the ordering. This means that if z, y, and z are any three vertices of the partite set representing the row such z < y < z in the ordering, then y is adjacent to any path connecting z and z . Considering that a (0, 1)-matrix M is the adjacency matrix of a directed graph D(V,E ) , we say that the bipartite graph B(D)obtained in the above manner is the associated bipartite graph (or simply bigraph) of the directed graph D.More precisely, B ( D ) is the bigraph with two disjoint copies U u V of V as vertex set, and where uw forms an edge, u E U and w E V iff uw E E. The (0, 1)-matrix M will also be termed the bzadjacency matrix of the bipartite graph subsequently. DIGRAPHS REPRESENTED BY INTERVALS 299 Instead of taking the partite set representing the rows, if we take the entire vertex set of the bigraph B ( D ) and extend the above idea, we get a characterization of an indifference digraph. A linear order of the vertices of a bigraph B ( D ) will be called aputh dominating order if for any three vertices II:, y, z of B ( D ) , whenever y lies between 2 and z , y is adjacent to every path connecting II: and z . The term dominating path has been taken from the paper on AT-free graphs by Corneil et al. [2].In this paper we prove that a digraph is an indifference digraph if and only if the vertices of the corresponding bigraph has a path dominating order. 2. CHARACTERIZATIONOF INTERVAL DIGRAPHS To characterize interval digraphs, we take the help of vertex-edge incidence matrix. Recall that an n by e matrix [ a i j ] whose , n rows correspond to the n vertices and the e columns correspond to the e edges of a digraph, is the vertex-edge incidence matrix, where aij = { +1 (-1), if the jth edge is incident out of (into) the ith vertex, *, 0, if the jth edge is a self loop at the ith vertex, otherwise. Theorem 1. A digraph D(V,E) is an interval digraph if and only if its edge set E has a consistent ordering. Proof. (Necessity). To prove the necessity, we introduce the notion of primitive intervals for the family 3 = {(S,, T,)}. An interval that is the intersection of s, and T, for some u , w E V,vw E E, is called a primitive interval. Consider the family of primitive intervals corresponding to all the edges. Now order the primitive intervals by usual lexicographic ordering on the pairs (left-end point, right-end point) defining the primitive intervals. This ordering of primitive intervals is our required ordering (<) of the edges. For edges having identical primitive intervals, order them arbitrarily among themselves. Now let pq < r s < tq. Then T,, the terminal interval of vertex q , must contain the primitives of both pq and tq, and by the above ordering the left-end point of the primitive interval of T S lies between the left ends of the primitive intervals of pq and t q or is identical with one or both of them. It follows that the source interval S, of the vertex r has a nonempty intersection with T,, implying that rq is an edge of D. Thus condition (ii) of consistent ordering is satisfied. The other condition follows similarly. (Sufficiency). Consider the vertex-edge incidence matrix of the digraph D , the ordering of the columns being determined by the given linear ordering of its edges. Now label the edges in increasing order of natural numbers as they occur in the matrix. Consider the row corresponding to vertex v. If the first and last columns of this row that contain +1 or * are the ath and bth columns, let S, = [a,b]. Similarly, if the first and last columns of this row that contain -1 or * are the cth and dth columns, let T, = [c,4. Now we prove that these intervals S, and T, for v E V are actually the source and terrninal intervals in an interval representation of the digraph D. Every edge in the vertex-edge incidence matrix has in its corresponding column only two entries +1 and -1 corresponding to the initial vertex and terminal vertex (or only one entry * corresponding to a self loop). Whenever S, n T,, = 4 there exists no such column that corresponds to a number 300 JOURNAL OF GRAPH THEORY belonging to both S, and T,. In other words, there is no edge in the digraph whose initial end point is v and terminal end point is w ,that is, uw 6 E. Next let S, n T, # 4. We shall show that there is a number such that a column corresponding to this number has entries +1 in row u and -1 in row w ,and this will prove that uw is an edge in D. We write S, = [a,, b,], T, = [c,, d,]. From the nonemptiness of S,, n T, arise two cases, viz., Consider case (i). When either a, = c, or c, = 'bvl the proof is immediate. So let a, < c, < b,. The entry +1, which corresponds to a,, determine an edge say wx in digraph D. Similarly, let the entries +1 at 6, and -1 at c, determine the edges, say uy and pw,respectively. Since a, < c, < b,, it follows that ux < pw < vy and by condition (i) of consistent ordering we get uw E E.The other case can be similarly proved. Observe that by making appropriate changes in the definition of consistent ordering and primitives, we obtain an analogous result for interval graphs. The set E of all edges of a graph G(V,E ) will be said to have a consistent ordering if E has a linear ordering (<) such that for pq,rs,puE E pq < rs < p u + p s E E and pr E E. Theorem 2. A graph G(V,E ) is an interval graph if and only if its edge set E has a consistent ordering. To prove the necessity, we moderate the definition of primitive interval in the following way: if 3 = {I,} is a family of intervals on the real line corresponding to the vertex set V of the interval graph, then an interval I, n I , for some u,w of the vertex set is a primitive interval. Order the family of primitives in the usual lexicographic manner and the proof of the necessity follows the same pattern as in Theorem 1. To give an outline of the proof of sufficiency we first ignore all the loops and consider the (0, 1)-incidencematrix of the simple graph with the given linear ordering of its edges. Then an interval I , corresponding to a vertex 'u is the interval [a,b]where the first 1 and last 1 in the w row appear in the ath column and bth column of the incidence matrix, respectively. The rest of the proof follows consequently. 3. CHARACTERIZATION OF INDIFFERENCE DIGRAPHS For a digraph D( V, E ) , let B(0 )denote the corresponding bigraph. An interval bigraph is a bigraph (U,V, E ) (with bipartition U and V )for which there are two families {S,/x E U } and {T,/y E V} of intervals such that 5 and y are adjacent whenever S, n Tv# 4. This class was introduced in [3]. As observed by Prisner [7], the following proposition is an immediate consequence of the definitions of an interval digraph and an interval bigraph. Proposition 3. (Prisner). A digraph D is an interval digraph if and only if B ( D ) is an interval bigraph. DIGRAPHS REPRESENTED BY INTERVALS 301 Considering the intervals in the above proposition to be of unit length, we immediately get the following: Proposition 4. bigraph. A digraph D is a unit interval digraph if and only if B ( D )is a unit interval In [9] it was proved that a digraph is a unit interval digraph if and only if its adjacency matrix has an MCA. Proposition 4 prompts us to state this result in the following form. Theorem 5. A bigraph is a unit interval bigraph if and only if its biadjacency matrix has an MCA. Now we are in a position to prove the following theorem characterizing a unit interval bigraph in terms of the notion of path dominating order of its vertices. Theorem 6. A bipartite graph B f D ) is a unit interval bigraph if and only if its vertices have a path dominating order. Proof. (Necessity). Let B be a unit interval bigraph. Then by Theorem 2, its biadjacency matrix has an MCA. Let us denote the rearranged matrix by A’(B). Consider the lower stair in A‘tB) (the stair that separates 1’s from C’s) so that the positions just above or just to the right of this stair are all 1’s; we ignore the degenerate cases where there are rows or columns of all 0’s as because the corresponding vertices become isolated ones in the bigraph having no bearing upon the dominating paths and so can be placed at the end of the order. These positions define a natural ordering of the vertices of B. We call this ordering R and shall prove that this is our required path dominating order. Let z < y < z in R and let P be an zz-path. Case 1. The z, y in the same partite set. Suppose z, y E V. Let A [ B ] denote the vertices of U that appear in R before [after] all neighbors of y, respectively. If P contains no neighbor of y, then the vertices of P in U all belong to A or B. Since z has no neighbor in B , P enters A from z. Also, P arrives at z from B (if z E V ) or z E B (if z E U ) . Hence P must travel from A to B via some vertex of V that has a neighbor in both A and B , but there is no such vertex. The argument when z, y E U is obtained by switching U and V. Case 2. The z, y in different bipartite sets. We may assume that y is not adjacent to this case, all neighbors of z come before y in R, whether 2 is in U or V. If y E U and y is not adjacent to z , or if y E V and z comes after y in R, then z is not adjacent to any vertex of U before y. Hence P contains a vertex of the same partite set as y that is after y in R. Let w be the first such vertex with P = 5 , .. . ,u,o, w,. . . , z . By the choice of w,uis before y in R, and now consecutivity implies that y is adjacent to o. 5. In It can be observed that the above order R is not the unique order serving our purpose. In fact, the order obtained from the upper stair (separating 1’s from R’s) in A’(D) or any stair that lies between the lower stair and upper stair is a path dominating order. 302 JOURNAL OF GRAPH THEORY (Sufficiency). Suppose that the vertices W = U u V of a bigraph B(U, V,A ) have path dominating order. Let z1 . .z, be the natural order of U obtained from the order of W deleting the elements of V from W and let y1 . . . y7,,be natural order of V similarly obtained from W by deleting the elements of U from W. Then if we rearrange the adjacency matrix of the corresponding digraph D with z1 . . .z, as rows and y1 . . y, as columns, the given order of W immediately provides us with a stair partition of the rearranged matrix. I Let now the entry (2, j ) in the above matrix be 1 so that z,Ay,. Suppose that the entry in the lower sector of the partition and so yJ < 5 , . Let p be the greatest integer such that yp < z, and accordingly y3 < yJ+l < . . . < yp < z, (and z, < yp+l). Note that the possible 5)’s in the above chain between yJ and z, (when j # p ) are not shown here. From the definition of path dominating order all the vertices lying between yJ and z, in R are adjacent to every yJ , z,-path. Since the edge yj z, is itself such a path, those vertices must be adjacent to either z, or y3. Since G is bipartite, the intermediate vertices in V cannot be adjacent to yj and so all those vertices must be adjacent to z,. In other words, ( a , ~ occurs ) + 1,j + 2, . . . ,p . Thus if ( i , j ) is in the bottom sector, then all the (2, j + l ) ,( i , j + 2). .. up to the stair will z i y k E A for k = j be 1. Now considering xi’s within the chain between yj and x i , we can similarly show that allthe(i-l,j),(z-2,j).~.uptothestairwillbe 1. I Similar arguments hold for the case when ( i , j )belongs to the upper sector. Hence the digraph is a unit interval bigraph. Combining Theorem 2 and Theorem 3, we can state the following: Theorem 7. The following four statements are equivalent: (i) (ii) (iii) (iv) D is a unit interval digraph; B ( D ) is a unit interval bigraph; the vertex set of B( 0 )has a path dominating order; the adjacency matrix of D has an MCA. ACKNOWLEDGMENTS The authors are thankful to a referee for his valuable comments and suggestions for the improvement of the paper. References [l] L. W. Beineke and C. M. Zamfirescu, Connection digraphs and second order line graphs. Discrete Math. 39 (1982), 237-254. [2] D. G . Corneil, S. Olariu, and L. Stewart, Asteroidal triple free graphs. Technical Report No. TR 94-31, Department of Computer Science, Old Dominion University (1994). DIGRAPHS REPRESENTED BY INTERVALS 303 F. Harary, J. A. Kabell, and F. R. McMorris, Bipartite intersection graphs. Comm. Math. Univ. Carolinae 23 (1982) 739-745. I. J. Lin and D. B. West, Forbidden substructure characterization of interval digraphs that are indifference digraphs. Preprint. M. S. Jacobson, F. R. McMorris, and H. M. Mulder, An introduction to tolerance intersection graphs, in (Y. Alavi et al., Eds), Graph Theory, Combinatories and Applications, Vol. 2 (1991) J. Wiley and Sons, Inc., New York (1991), 705-723. C. G. Lekerkerker and J. C. Boland, Representation of a finite graph by a set of intervals on the real line. Fund. Math. 51 (1962) 45-64. E. Primer, Three remarks on interval digraphs. Preprint. 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. M. Sen and B. K. Sanyal, Indifference digraphs: A generalization of indifference graphs and semiorders. SIAM J. Discrete Math. 7 (1994) 157-165. M. K. Sen, B. K. Sanyal, and D. B. West, Representing digraphs using intervals or circular arcs. Discrete Math. 147 (1995) 235-245. A. Tucker, A structure theorem for the consecutive 1’s property. J. Combinat. Theory (B) 12 (1972) 153-162. Received September 20, 1993

1/--страниц