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


Vertex-transitive graphs that are not Cayley graphs. II

код для вставкиСкачать
New Characterizations of
Digraphs Represented by
Barun K. Sanyal
Malay K. Sen
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.
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)
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
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
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.
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.
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,
if the jth edge is a self loop at the ith vertex,
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
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.
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.
Considering the intervals in the above proposition to be of unit length, we immediately
get the following:
Proposition 4.
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.
(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.
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.
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:
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.
The authors are thankful to a referee for his valuable comments and suggestions for the
improvement of the paper.
L. W. Beineke and C. M. Zamfirescu, Connection digraphs and second order line graphs.
Discrete Math. 39 (1982), 237-254.
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).
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
Без категории
Размер файла
413 Кб
vertep, cayley, graph, transition
Пожаловаться на содержимое документа