The diameter of a graph is the maximal distance between two vertices of . A graph is said to be diameter-edge-invariant, if for all its edges, diameter-vertex-invariant, if for all its vertices and diameter-adding-invariant if for all edges of the complement of the edge set of . This paper describes some properties of such graphs and gives several existence results and bounds for parameters of diameter-invariant graphs.
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...
A graph G is a difference graph iff there exists S ⊂ IN⁺ such that G is isomorphic to the graph DG(S) = (V,E), where V = S and E = i,j:i,j ∈ V ∧ |i-j| ∈ V. It is known that trees, cycles, complete graphs, the complete bipartite graphs and , pyramids and n-sided prisms (n ≥ 4) are difference graphs (cf. [4]). Giving a special labelling algorithm, we prove that cacti with a girth of at least 6 are difference graphs, too.
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...
We show that any digraph on vertices and with not less than arcs is contractible onto .
The domination graph of a directed graph has an edge between vertices x and y provided either (x,z) or (y,z) is an arc for every vertex z distinct from x and y. We consider directed graphs D for which the domination graph of D is isomorphic to the underlying graph of D. We demonstrate that the complement of the underlying graph must have k connected components isomorphic to complete graphs, paths, or cycles. A complete characterization of directed graphs where k = 1 is presented.