-favouring Eulerian trails in digraphs
Das lexikographische Produkt gerichteter Graphen.
Decidability problems for the variety generated by tournaments.
Deciding soccer scores and partial orientations of graphs.
Decomposition of a Digraph into Isomorphic Subgraphs
Decomposition of the Complete Directed Graph into Two Factors with Given Diameters
Decomposition tree and indecomposable coverings
Let G = (V,A) be a directed graph. With any subset X of V is associated the directed subgraph G[X] = (X,A ∩ (X×X)) of G induced by X. A subset X of V is an interval of G provided that for a,b ∈ X and x ∈ V∖X, (a,x) ∈ A if and only if (b,x) ∈ A, and similarly for (x,a) and (x,b). For example ∅, V, and {x}, where x ∈ V, are intervals of G which are the trivial intervals. A directed graph is indecomposable if all its intervals are trivial. Given an integer k > 0, a directed graph G = (V,A) is called...
Decompositions of a complete multidigraph into almost arbitrary paths
For n ≥ 4, the complete n-vertex multidigraph with arc multiplicity λ is proved to have a decomposition into directed paths of arbitrarily prescribed lengths ≤ n - 1 and different from n - 2, unless n = 5, λ = 1, and all lengths are to be n - 1 = 4. For λ = 1, a more general decomposition exists; namely, up to five paths of length n - 2 can also be prescribed.
Decompositions of nearly complete digraphs into t isomorphic parts
An arc decomposition of the complete digraph Kₙ into t isomorphic subdigraphs is generalized to the case where the numerical divisibility condition is not satisfied. Two sets of nearly tth parts are constructively proved to be nonempty. These are the floor tth class ( Kₙ-R)/t and the ceiling tth class ( Kₙ+S)/t, where R and S comprise (possibly copies of) arcs whose number is the smallest possible. The existence of cyclically 1-generated decompositions of Kₙ into cycles and into paths is characterized....
Degree constrained orientations in countable graphs.
Degree sequences of digraphs with highly irregular property
A digraph such that for each its vertex, vertices of the out-neighbourhood have different in-degrees and vertices of the in-neighbourhood have different out-degrees, will be called an HI-digraph. In this paper, we give a characterization of sequences of pairs of out- and in-degrees of HI-digraphs.
Diametrically critical tournaments
Dichromatic number, circulant tournaments and Zykov sums of digraphs
The dichromatic number dc(D) of a digraph D is the smallest number of colours needed to colour the vertices of D so that no monochromatic directed cycle is created. In this paper the problem of computing the dichromatic number of a Zykov-sum of digraphs over a digraph D is reduced to that of computing a multicovering number of an hypergraph H₁(D) associated to D in a natural way. This result allows us to construct an infinite family of pairwise non isomorphic vertex-critical k-dichromatic circulant...
Difference labelling of digraphs
A digraph G is a difference digraph iff there exists an S ⊂ N⁺ such that G is isomorphic to the digraph DD(S) = (V,A), where V = S and A = {(i,j):i,j ∈ V ∧ i-j ∈ V}.For some classes of digraphs, e.g. alternating trees, oriented cycles, tournaments etc., it is known, under which conditions these digraphs are difference digraphs (cf. [5]). We generalize the so-called source-join (a construction principle to obtain a new difference digraph from two given ones (cf. [5])) and construct a difference labelling...
Digraphs contractible onto
We show that any digraph on vertices and with not less than arcs is contractible onto .
Digraphs maximal with respect to arc connectivity
Digraphs maximal with respect to connectivity
Digraphs with large exponent.
Direct product decompositions of digraphs
Direct product decompositions of -digraphs