Three Problems About Distances In Graphs And Digraphs

In this paper, we restrict our attention to three problems about distances in graphs and digraphs: (1) Minimum diameter orientations of K_m ∨ K_n(m ≥ 1, n ≥ 1), (2) Disjoint quasi-kernels in digraphs, (3) Eccentric digraphs.For a graph G, let D denote an orientation of G having minimum diameter. Define f(G) =diamD. In this paper, we concentrate on exploring the minimum diameter of K_m ∨ K_n(m ≥ 1, n ≥ 1) . Some special cases are known: f(K_m ∨ K_n) = ∞, 2, 3, where m = 1 and n ≥ 1, m = 2 or m ≥ 4 and n = 1, m = 3 and n = 1, respectively. So we only consider the case when m ≥ 2 and n ≥ 2. The following results are obtained: (1) f(K_m ∨ K_n) = 3, where m = 2,3, n ≥ 2 and m = n = 4; (2) f(K_m ∨ K_n) = 2, where m ≥ 5 and m is odd, , where m ≥ 5 and m is odd, (4) , where m ≥ 4 and m = 0 (mod 4), ; (5) f(K_m ∨ K_n) = 2, where m ≥ 6 and m ≡ 2 (mod 4), 2 ≤ n ≤ - m/2; (6) f(K_m ∨ K_n) = 3, where m > 4 and m is even, A vertex set X of a digraph D = (V, A) is a quasi-kernel if X is independent and for every v ∈ V - X there exist w ∈V — X, x e X such that either vx ∈Aor vw, wx ∈ A. In this paper, we provide a necessary condition and several sufficient conditions for a digraph to have a pair of disjoint quasi-kernels.The eccentricity e(v) of vertex v is the maximum distance of v to any other vertex of D. A vertex u is an eccentric vertex of vertex v if the distance from v to u is equal to the eccentricity of v. The eccentric digraph ED(D) of a digraph D is the digraph that has the same vertex set as D and the arc set defined by: there is an arc from u to v if and only if v is an eccentric vertex of u. The eccentric digraph ED{G) of graph G is similarly defined.In this paper, we examine eccentric digraphs of several classes of graphs and digraphs. Let T be an undirected tree. We determine the structure of ED2{T), which is an open problem listed in [12].