Directed distance in digraphs: Centers and medians

The directed distance d_D(u, v) from a vertex u to a vertex v in a strong digraph D is the length of a shortest (directed) u - v path in D. The eccentricity of a vertex v in D is the directed distance from v to a vertex furthest from v. The distance of a vertex v in D is the sum of the directed distances from v to the vertices of D. The center C(D) of D is the subdigraph induced by those vertices of minimum eccentricity, while the median M(D) of D is the subdigraph induced by those vertices of minimum distance. It is shown that for every two asymmetric digraphs D₁ and D₂, there exists a strong asymmetric digraph H such that C(H) ? D₁ and M(H) ? D₂, and where the directed distance from C(H) to M(H) and from M(H) to C(H) can be arbitrarily prescribed. Furthermore, if K is a nonempty asymmetric digraph isomorphic to an induced subdigraph of both D₁ and D₂, then there exists a strong asymmetric digraph F such that C(F) ? D₁, M(F) ? D₂ and C(F) ∩ M(F) ? K. © 1993 John Wiley & Sons, Inc.     

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.     

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.     

Distance in stratified graphs

A graph G is stratified if its vertex set is partitioned into classes, called strata. If there are k strata, then G is k-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color X in a stratified graph G, the X-eccentricity e _X(v) of a vertex v of G is the distance between v and an X-colored vertex furthest from v. The minimum X-eccentricity among the vertices of G is the X-radius rad_X G of G and the maximum X-eccentricity is the X-diameter diam_X G. It is shown that for every three positive integers a, b and k with ab, there exist a k-stratified graph G with rad_X G = a and diam_X G = b. The number s _X denotes the minimum X-eccetricity among the X-colored vertices of G. It is shown that for every integer t with rad_X G t diam_X G, there exist at least one vertex v with e _X(v) = t; while if rad_X G t s _X, then there are at least two such vertices. The X-center C _X(G) is the subgraph induced by those vertices v with e _X(v) = rad_X G and the X-periphery P _X (G) is the subgraph induced by those vertices v with e _X(G) = diam_X G. It is shown that for k-stratified graphs H ₁, H ₂,..., H _k with colors X ₁, X ₂,..., X _k and a positive integer n, there exists a k-stratified graph G such that C X _i(G) H _i (1 ; i ; k1) and for i j. Those k-stratified graphs that are peripheries of k-stratified graphs are characterized. Other distance-related topics in stratified graphs are also discussed.     

On the sum of the total domination numbers of a digraph and its converse

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S has an in-neighbor in S. A dominating set S of D is called a total dominating set of D if the subdigraph induced by S has no isolated vertices. The total domination number of D, denoted by γt(D), is the minimum cardinality of a total dominating set of D. We show that for any connected digraph D of order n≥3, γt(D)+γt(D^? )≤5n/3, where D? is the converse of D. Furthermore, we characterize the oriented trees for which the equality holds.     

A Generalization of the Gallai–Roy Theorem

 A well-known and essential result due to Roy ([4], 1967) and independently to Gallai ([3], 1968) is that if D is a digraph with chromatic number χ(D), then D contains a directed path of at least χ(D) vertices. We generalize this result by showing that if ψ(D) is the minimum value of the number of the vertices in a longest directed path starting from a vertex that is connected to every vertex of D, then χ(D) ≤ψ(D). For graphs, we give a positive answer to the following question of Fajtlowicz: if G is a graph with chromatic number χ(G), then for any proper coloring of G of χ(G) colors and for any vertex v∈V(G), there is a path P starting at v which represents all χ(G) colors. Received: May 20, 1999 Final version received: December 24, 1999     

The minimum spanning strong subdigraph problem is fixed parameter tractable

A digraph D is strong if it contains a directed path from x to y for every choice of vertices x,y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph D on n vertices contains a spanning strong subdigraph on at most 2n−2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k≤n−2 so that D contains a spanning strong subdigraph with at most 2n−2−k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)n^c) algorithm for deciding whether a given strong digraph D on n vertices contains a spanning strong subdigraph with at most 2n−2−k arcs.We furthermore prove that if k≥1 and D has no cut vertex then it has a kernel of order at most (2k−1)². We finally discuss related problems and conjectures.     

强定向图的k-强距离

对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的Steiner子图,S的强Steiner距离d(S)等于S的Steiner子图的弧数. 如果|S|=k, 那么d(S)称为S的k-强距离. 对整数k≥2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值. D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sdiamk(D). 本文证明了,对于满足k+1≤r,d≤n的任意整数r,d,存在顶点数为n的强竞赛图T′和T″,使得sradk(T′)=r和sdiamk(T″)=d;进而给出了强定向图的k-强直径的一个上界.     

Broadcasts in graphs

We say that a function f:V→{0,1,…,diam(G)} is a broadcast if for every vertex v∈V, f(v)?e(v), where diam(G) denotes the diameter of G and e(v) denotes the eccentricity of v. The cost of a broadcast is the value . In this paper we introduce and study the minimum and maximum costs of several types of broadcasts in graphs, including dominating, independent and efficient broadcasts.     

Quasi-transitive digraphs

A digraph is quasi-transitive if there is a complete adjacency between the inset and the outset of each vertex. Quasi-transitive digraphs are interseting because of their relation to comparability graphs. Specifically, a graph can be oriented as a quasi-transitive digraph if and only if it is a comparability graph. Quasi-transitive digraphs are also of interest as they share many nice properties of tournaments. Indeed, we show that every strongly connected quasi-transitive digraphs D on at least four vertices has two vertices v₁ and v₂ such that D – v_i is strongly connected for i = 1, 2. A result of tournaments on the existence of a pair of arc-disjoint in- and out-branchings rooted at the same vertex can also be extended to quasi-transitive digraphs. However, some properties of tournaments, like hamiltonicity, cannot be extended directly to quasi-transitive digraphs. Therefore we characterize those quasi-transitive digraphs which have a hamiltonian cycle, respectively a hamiltonian path. We show the existence of highly connected quasi-transitive digraphs D with a factor (a collection of disjoint cycles covering the vertex set of D), which have a cycle of every length 3 ≦ k ≦ |V(D)| ? 1 through every vertex and yet they are not hamiltonian. Finally we characterize pancyclic and vertex pancyclic quasi-transitive digraphs. © 1995, John Wiley & Sons, Inc.     

Second Neighborhood via First Neighborhood in Digraphs

Let D be a simple digraph without loops or digons. For any v ? V(D) v\in V(D) , the first out-neighborhood N⁺(v) is the set of all vertices with out-distance 1 from v and the second neighborhood N⁺⁺(v) of v is the set of all vertices with out-distance 2 from v. We show that every simple digraph without loops or digons contains a vertex v such that |N⁺⁺(v)| 3 g|N⁺(v)| |N^{++}(v)|\geq\gamma|N^+(v)| , where % = 0.657298... is the unique real root of the equation 2x³ + x² -1 = 0.     

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?     

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)}     

Two Conjectures on Graceful Digraphs

A digraph D with p vertices and q arcs is labeled by assigning a distinct integer value g(v) from {0,1, … , q} to each vertex v. The vertex values, in turn, induce a value g(u, v) on each arc (u, v) where g(u, v) = (g(v)? g(u))(mod q + 1). If the arc values are all distinct then the labeling is called a graceful labeling of a digraph. Bloom and Hsu (SIAM J Alg Discr Methods 6:519–536, 1985) conjectured that, all unicyclic wheels are graceful. Also, Zhao et al. (J Prime Res Math 4:118–126, 2008) conjectured that, for any positive even n and any integer m ≥ 14, the digraph ${n-\overrightarrow{C_m}}$ is graceful. In this paper, we prove both the conjectures.     

Scrambling index set of primitive digraphs

The scrambling index k(D)$k(D)$ of a primitive digraph D is the smallest positive integer k such that for every pair of vertices x and y, there exists a vertex v such that there exist directed walks of length k from x to v and from y to v. In this paper, we study the scrambling index set of primitive digraphs.     

Lower and upper orientable strong radius and strong diameter of complete k-partite graphs

For two vertices u and v in a strong digraph D, the strong distance sd(u,v) between u and v is the minimum size (the number of arcs) of a strong sub-digraph of D containing u and v. For a vertex v of D, the strong eccentricity se(v) is the strong distance between v and a vertex farthest from v. The strong radius srad(D) (resp. strong diameter sdiam(D)) is the minimum (resp. maximum) strong eccentricity among the vertices of D. The lower (resp. upper) orientable strong radius srad(G) (resp. SRAD(G)) of a graph G is the minimum (resp. maximum) strong radius over all strong orientations of G. The lower (resp. upper) orientable strong diameter sdiam(G) (resp. SDIAM(G)) of a graph G is the minimum (resp. maximum) strong diameter over all strong orientations of G. In this paper, we determine the lower orientable strong radius and diameter of complete k-partite graphs, and give the upper orientable strong diameter and the bounds on the upper orientable strong radius of complete k-partite graphs. We also find an error about the lower orientable strong diameter of complete bipartite graph K_m,n given in [Y.-L. Lai, F.-H. Chiang, C.-H. Lin, T.-C. Yu, Strong distance of complete bipartite graphs, The 19th Workshop on Combinatorial Mathematics and Computation Theory, 2002, pp. 12-16], and give a rigorous proof of a revised conclusion about sdiam(K_m,n).     

Gallai colorings and domination in multipartite digraphs

Assume that D is a digraph without cyclic triangles and its vertices are partitioned into classes A₁, …, A_t of independent vertices. A set is called a dominating set of size |S| if for any vertex there is a w∈U such that (w, v)∈E(D). Let β(D) be the cardinality of the largest independent set of D whose vertices are from different partite classes of D. Our main result says that there exists a h = h(β(D)) such that D has a dominating set of size at most h. This result is applied to settle a problem related to generalized Gallai colorings, edge colorings of graphs without 3‐colored triangles. © 2011 Wiley Periodicals, Inc. J Graph Theory     

A Generalization of Opsut’s Lower Bounds for the Competition Number of a Graph

The notion of a competition graph was introduced by Cohen in 1968. The competition graph C(D) of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. In 1978, Roberts defined the competition number k(G) of a graph G as the minimum number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. In 1982, Opsut gave two lower bounds for the competition number of a graph. In this paper, we give a generalization of these two lower bounds for the competition number of a graph.     

Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

Vertex fusion under distance constraints

In this paper, we analyze parameter improvement under vertex fusion in a graph G. This is a setting in which a new graph G^′ is obtained after identifying a subset of vertices of G in a single vertex. We are interested in distance parameters, in particular diameter, radius and eccentricity of a vertex v. We show that the corresponding problem is NP-Complete for the three parameters. We also find graph classes in which the problem can be solved in polynomial time.