Circular-arc digraphs: A characterization

Given a family F of ordered pairs of sets {(S_u,T_u): u ? V}, the intersection digraph of F is the digraph with vertices V defined by uv ? E(D) if S_u ≠ T_v Ø. Interval digraphs are intersection digraphs of families in which every set is an interval, and were characterized in a previous paper by conditions on the adjacency matrix. In this paper, another such condition leads to an adjacency matrix characterization of circular-arc digraphs, the intersection digraphs of families in which every set is an arc of a circle.     

Characterization of eccentric digraphs

The eccentric digraphED(G) of a digraph G represents the binary relation, defined on the vertex set of G, of being ‘eccentric’; that is, there is an arc from u to v in ED(G) if and only if v is at maximum distance from u in G. A digraph G is said to be eccentric if there exists a digraph H such that G=ED(H). This paper is devoted to the study of the following two questions: what digraphs are eccentric and when the relation of being eccentric is symmetric.We present a characterization of eccentric digraphs, which in the undirected case says that a graph G is eccentric iff its complement graph is either self-centered of radius two or it is the union of complete graphs. As a consequence, we obtain that all trees except those with diameter 3 are eccentric digraphs. We also determine when ED(G) is symmetric in the cases when G is a graph or a digraph that is not strongly connected.     

On CCE graphs of doubly partial orders

Let D be a digraph. The competition-common enemy graph (CCE graph) of D has the same set of vertices as D and an edge between vertices u and v if and only if there are vertices w and x in D such that (w,u), (w,v), (u,x), and (v,x) are arcs of D. We call a graph a CCE graph if it is the CCE graph of some digraph. In this paper, we show that if the CCE graph of a doubly partial order does not contain C₄ as an induced subgraph, it is an interval graph. We also show that any interval graph together with enough isolated vertices is the CCE graph of some doubly partial order.     

Kernels by monochromatic paths in digraphs with covering number 2

We call the digraph D an k-colored digraph if the arcs of D are colored with k colors. A subdigraph H of D is called monochromatic if all of its arcs are colored alike. A set N⊆V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v∈N, there is no monochromatic directed path between them, and (ii) for every vertex x∈(V(D)?N), there is a vertex y∈N such that there is an xy-monochromatic directed path. In this paper, we prove that if D is an k-colored digraph that can be partitioned into two vertex-disjoint transitive tournaments such that every directed cycle of length 3,4 or 5 is monochromatic, then D has a kernel by monochromatic paths. This result gives a positive answer (for this family of digraphs) of the following question, which has motivated many results in monochromatic kernel theory: Is there a natural numberlsuch that if a digraphDisk-colored so that every directed cycle of length at mostlis monochromatic, thenDhas a kernel by monochromatic paths?     

Excluding a Simple Good Pair Approach to Directed Cuts

In 1972, Mader proved that every undirected graph has a good pair, that is, an ordered pair (u,v) of nodes such that the star of v is a minimum cut separating u and v. In 1992, Nagamochi and Ibaraki gave a simple procedure to find a good pair as the basis of an elegant and very efficient algorithm to find minimum cuts in graphs. This paper rules out the simple good pair approach for the problem of finding a minimum directed cut in a digraph and for the more general problem of minimizing submodular functions. In fact, we construct a digraph with no good pair. Note that if a graph has no good pair, then it may not possess a so-called cut-equivalent tree. Benczúr constructed a digraph with no cut-equivalent tree; our counterexample thus extends Benczúr's one. Received: March 12, 1999 Final version received: June 19, 2000     

Hypotraceable digraphs

A hypotraceable digraph is a digraph D = (V, E) which is not traceable, i.e., does not contain a (directed)Hamiltonian path, but for which D - v is traceable for all ve ∈ V. We prove that a hypotraceable digraph of order n exists iff n ≥ 7 and that for each k ≥ 3 there are infinitely many hypotraceable oriented graphs with a source and a sink and precisely k strong components. We also show that there are strongly connected hypotraceable oriented graphs and that there are hypotraceable digraphs with precisely two strong components one of which is a source or a sink. Finally, we prove that hypo-Hamiltonian and hypotraceable digraphs may contain large complete subdigraphs.     

Influence Digraphs Induced by Time-Stamped Graphs (Extended Abstract)

A time-stamped graph is an undirected graph with a real number on each edge. Vertex u influences vertex v if there is an increasing path from u to v. The induced influence digraph of a time-stamped graph is the directed graph that records the influences. In this paper we study the realizability problem: Given a parameter value, does there exist a time-stamped graph whose induced influence digraph has the given parameter value? In particular, we solve this problem when the parameter is the number of arcs. Moreover, if the candidates for the time-stamped graphs are restricted to trees, then every realizable value can be achieved by a tree homeomorphic to K₂ or K_1,3. A number of other questions are also explored. The full version of this paper is submitted to a referreed journal.     

Degree sets for digraphs

The degree setD _D of a digraphD is the set of outdegrees of the vertices ofD. For a finite, nonempty setS of nonnegative integers, it is shown that there exists an asymmetric digraph (oriented graph)D such thatD _D =S. Furthermore, the minimum order of such a digraphD is determined. Also, given two finite sequences of nonnegative integers, a necessary and sufficient condition is provided for which these sequences are the outdegree sequences of the two sets of an asymmetric bipartite digraph.     

Multiplicativity of acyclic local tournaments

A homomorphism of a digraph to another digraph is an edge-preserving vertex mapping. A digraphH is said to be multiplicative if the set of digraphs which do not admit a homomorphism toH is closed under categorical product. In this paper we discuss the multiplicativity of acyclic Hamiltonian digraphs, i.e., acyclic digraphs which contains a Hamiltonian path. As a consequence, we give a complete characterization of acyclic local tournaments with respect to multiplicativity.     

Enumerations of vertex orders of almost Moore digraphs with selfrepeats

An almost Moore digraph G of degree d>1, diameter k>1 is a diregular digraph with the number of vertices one less than the Moore bound. If G is an almost Moore digraph, then for each vertex u∈V(G) there exists a vertex v∈V(G), called repeat of u and denoted by r(u)=v, such that there are two walks of length ?k from u to v. The smallest positive integer p such that the composition r^p(u)=u is called the order of u. If the order of u is 1 then u is called a selfrepeat. It is known that if G is an almost Moore digraph of diameter k?3 then G contains exactly k selfrepeats or none. In this paper, we propose an exact formula for the number of all vertex orders in an almost Moore digraph G containing selfrepeats, based on the vertex orders of the out-neighbours of any selfrepeat vertex.     

A Characterization of Locally Semicomplete CKI-digraphs

A digraph is locally-in semicomplete if for every vertex of D its in-neighborhood induces a semicomplete digraph and it is locally semicomplete if for every vertex of D the in-neighborhood and the out-neighborhood induces a semicomplete digraph. The locally semicomplete digraphs where characterized in 1997 by Bang-Jensen et al. and in 1998 Bang-Jensen and Gutin posed the problem if finding a kernel in a locally-in semicomplete digraph is polynomial or not. A kernel of a digraph is a set of vertices, which is independent and absorbent. A digraph D such that every proper induced subdigraph of D has a kernel is said to be critical kernel imperfect digraph (CKI-digraph) if the digraph D does not have a kernel. A digraph without an induced CKI-digraph as a subdigraph does have a kernel. We characterize the locally semicomplete digraphs, which are CKI. As a consequence of this characterization we conclude that determinate whether a locally semicomplete digraph is a CKI-digraph or not, is polynomial.     

Ultracritical and hypercritical binary structures

A binary structure is an arc-coloured complete digraph, without loops, and with exactly two coloured arcs (u,v) and (v,u) between distinct vertices u and v. Graphs, digraphs and partial orders are all examples of binary structures. Let B be a binary structure. With each subset W of the vertex set V(B) of B we associate the binary substructure B[W] of B induced by W. A subset C of V(B) is a clan of B if for any c,d∈C and v∈V(B)?C, the arcs (c,v) and (d,v) share the same colour and similarly for (v,c) and (v,d). For instance, the vertex set V(B), the empty set and any singleton subset of V(B) are clans of B. They are called the trivial clans of B. A binary structure is primitive if all its clans are trivial.With a primitive and infinite binary structure B we associate a criticality digraph (in the sense of [11]) defined on V(B) as follows. Given v≠w∈V(B), (v,w) is an arc of the criticality digraph of B if v belongs to a non-trivial clan of B[V(B)?{w}]. A primitive and infinite binary structure B is finitely critical if B[V(B)?F] is not primitive for each finite and non-empty subset F of V(B). A finitely critical binary structure B is hypercritical if for every v∈V(B), B[V(B)?{v}] admits a non-trivial clan C such that |V(B)?C|≥3 which contains every non-trivial clan of B[V(B)?{v}]. A hypercritical binary structure is ultracritical whenever its criticality digraph is connected.The ultracritical binary structures are studied from their criticality digraphs. Then a characterization of the non-ultracritical but hypercritical binary structures is obtained, using the generalized quotient construction originally introduced in [1].     

Chronological orderings of interval digraphs

An interval digraph is the intersection digraph of a family of ordered pairs of intervals on the real line; the family is an interval representation of the digraph. It is well known that an interval digraph has many representations that differ in the order of the endpoints of the intervals on the line. This paper generalizes the corresponding results on interval graphs by Skrien [Chronological orderings of interval graphs, Discrete Appl. Math. 8 (1984) 69-83] and describes how, given an interval digraph, the order of intervals of one representation differs from another.     

On double and multiple interval graphs

In this paper we discuss a generalization of the familiar concept of an interval graph that arises naturally in scheduling and allocation problems. We define the interval number of a graph G to be the smallest positive integer t for which there exists a function f which assigns to each vertex u of G a subset f(u) of the real line so that f(u) is the union of t closed intervals of the real line, and distinct vertices u and v in G are adjacent if and only if f(u) and f(v)meet. We show that (1) the interval number of a tree is at most two, and (2) the complete bipartite graph K_{m, n} has interval number ?(mn + 1)/(m + n)?.     

Randomly antitraceable digraphs

An antipath in a digraph is a semipath containing no (directed) path of length 2. A digraph D is randomly antitraceable if for each vertex v of D, any antipath beginning at v can be extended to a hamiltonian antipath beginning at v. In this paper randomly antitraceable digraphs are characterized.     

Strong Asymmetric Digraphs with Prescribed Interior and Annulus

The directed distance d(u,v) from u to v in a strong digraph D is the length of a shortest u-v path in D. The eccentricity e(v) of a vertex v in D is the directed distance from v to a vertex furthest from v in D. The center and periphery of a strong digraph are two well known subdigraphs induced by those vertices of minimum and maximum eccentricities, respectively. We introduce the interior and annulus of a digraph which are two induced subdigraphs involving the remaining vertices. Several results concerning the interior and annulus of a digraph are presented.     

Local-edge-connectivity in digraphs and oriented graphs

A digraph without any cycle of length two is called an oriented graph. The local-edge-connectivityλ(u,v) of two vertices u and v in a digraph or graph D is the maximum number of edge-disjoint u-v paths in D, and the edge-connectivity of D is defined as . Clearly, λ(u,v)?min{d⁺(u),d^-(v)} for all pairs u and v of vertices in D. Let δ(D) be the minimum degree of D. We call a graph or digraph D maximally edge-connected when λ(D)=δ(D) and maximally local-edge-connected when

λ(u,v)=min{d⁺(u),d^-(v)}     

The competition number of a graph whose holes do not overlap much

Let D be an acyclic digraph. The competition graph of D is a graph which has the same vertex set as D and has an edge between u and v if and only if there exists a vertex x in D such that (u,x) and (v,x) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices.A hole of a graph is an induced cycle of length at least four. Kim (2005) [8] conjectured that the competition number of a graph with h holes is at most h+1. Recently, Li and Chang (2009) [11] showed that the conjecture is true when the holes are independent. In this paper, we show that the conjecture is true though the holes are not independent but mutually edge-disjoint.     

Vosperian and superconnected Abelian Cayley digraphs

A digraphX is said to be Vosperian if any fragment has cardinality either 1 or|V(X)| – d ⁺ (X) – 1.A digraph is said to be superconnected if every minimum cutset is the set of vertices adjacent from or to some vertex.In this paper we characterize Vosperian and superconnected Abelian Cayley directed graphs. Our main tool is a difficult theorem of J.H. Kemperman from Additive Group Theory.In particular we characterize Vosperian and superconnected loops network (also called circulants).