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...
The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph where = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph of G. In particular we investigate conditions for G and k such that becomes a complete graph.
If D = (V,A) is a digraph, its competition hypergraph (D) has vertex set V and e ⊆ V is an edge of (D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that . We give characterizations of (D) in case of hamiltonian digraphs D and, more general, of digraphs D having a τ-cycle factor. The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [4] and Guichard [6].
If D = (V,A) is a digraph, its competition hypergraph 𝓒𝓗(D) has the vertex set V and e ⊆ V is an edge of 𝓒𝓗(D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that e = {w ∈ V|(w,v) ∈ A}. We tackle the problem to minimize the number of strong components in D without changing the competition hypergraph 𝓒𝓗(D). The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [3].
If D = (V, A) is a digraph, its competition graph (with loops) CGl(D) has the vertex set V and {u, v} ⊆ V is an edge of CGl(D) if and only if there is a vertex w ∈ V such that (u, w), (v, w) ∈ A. In CGl(D), loops {v} are allowed only if v is the only predecessor of a certain vertex w ∈ V. For several products D1 ⚬ D2 of digraphs D1 and D2, we investigate the relations between the competition graphs of the factors D1, D2 and the competition graph of their product D1 ⚬ D2.
If D = (V,A) is a digraph, its niche hypergraph NH(D) = (V, E) has the edge set ℇ = {e ⊆ V | |e| ≥ 2 ∧ ∃ v ∈ V : e = N−D(v) ∨ e = N+D(v)}. Niche hypergraphs generalize the well-known niche graphs (see [11]) and are closely related to competition hypergraphs (see [40]) as well as double competition hypergraphs (see [33]). We present several properties of niche hypergraphs of acyclic digraphs.
Page 1