正圆有向图中的弧不相交的Hamilton路和圈

2012年,Bang-Jensen和Huang(J.Combin.Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图可以分解为两个弧不相交的强连通生成子图当且仅当D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图中包含两个弧不相交的Hamilton圈的猜想.主要研究正圆有向图中的弧不相交的Hamilton路和Hamilton圈,并证明了任意3-弧强的正圆有向图中包含两个弧不相交的Hamilton圈和任意4-弧强的正圆有向图中包含一个Hamilton圈和两个Hamilton路,使得它们两两弧不相交.由于任意圆有向图一定是正圆有向图,所得结论可以推广到圆有向图中.又由于圆有向图是局部竞赛图的子图类,因此所得结论说明对局部竞赛图的子图类――圆有向图,Bang-Jensen和Huang的猜想成立.     

Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.     

Kernels of digraphs with finitely many ends

According to Richardson’s theorem, every digraph $G$ without directed odd cycles that is either (a) locally finite or (b) rayless has a kernel (an independent subset $K$ with an incoming edge from every vertex in $G?K$). We generalize this theorem showing that a digraph without directed odd cycles has a kernel when (a) for each vertex, there is a finite set separating it from all rays, or (b) each ray contains at most finitely many vertices dominating it (having an infinite fan to the ray) and the digraph has finitely many ends. The restriction to finitely many ends in (b) can be weakened, admitting infinitely many ends with a specific structure, but the possibility of dropping it remains a conjecture.     

Distance and size in digraphs

We determine the maximum number of arcs in an Eulerian digraph of given order and diameter. Our bound generalises a classical result on the maximum number of edges of an undirected graph of given order and diameter by Ore (1968) and Homenko and Ostroverhii? (1970). We further determine the maximum size of a bipartite digraph of given order and radius.     

Openly disjoint circuits through a vertex in regular digraphs

In 1985, Thomassen [14] constructed for every positive integer r, finite digraphs D of minimum degree δ(D)=r which do not contain a vertex x lying on three openly disjoint circuits, i.e. circuits which have pairwise exactly x in common. In 2005, Seymour [11] posed the question, whether an r-regular digraph contains a vertex x such that there are r openly disjoint circuits through x. This is true for r≤3, but does not hold for r≥8. But perhaps, in contrast to the minimum degree, a high regularity degree suffices for the existence of a vertex lying on r openly disjoint circuits also for r≥4. After a survey of these problems, we will show that every r-regular digraph with r≥7 has a vertex which lies on 4 openly disjoint circuits.     

Enumerations of vertex orders of almost Moore digraphs with selfrepeats

An almost Moore digraph G of degree d>1, diameter k>1 is a diregular digraph with the number of vertices one less than the Moore bound. If G is an almost Moore digraph, then for each vertex u∈V(G) there exists a vertex v∈V(G), called repeat of u and denoted by r(u)=v, such that there are two walks of length ?k from u to v. The smallest positive integer p such that the composition r^p(u)=u is called the order of u. If the order of u is 1 then u is called a selfrepeat. It is known that if G is an almost Moore digraph of diameter k?3 then G contains exactly k selfrepeats or none. In this paper, we propose an exact formula for the number of all vertex orders in an almost Moore digraph G containing selfrepeats, based on the vertex orders of the out-neighbours of any selfrepeat vertex.     

A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints

Let $k\ge 4$ and $n\ge k+4$ be positive integers. We determine the maximum size of digraphs of order $n$ that avoid distinct walks of length $k$ with the same endpoints. We also characterize the extremal digraphs attaining this maximum number when $k\ge 5$.     

On the restricted arc-connectivity of s-geodetic digraphs

For a strongly connected digraph D the minimum ,cardinality of an arc-cut over all arc-cuts restricted arc-connectivity λ′（D） is defined as the S satisfying that D - S has a non-trivial strong component D1 such that D - V（D1） contains an arc. Let S be a subset of vertices of D. We denote by w＋（S） the set of arcs uv with u ∈ S and v S, and by w-（S） the set of arcs uv with u S and v ∈ S. A digraph D = （V, A） is said to be λ′-optimal if λ′（D） =ξ′（D）, where ξ′（D） is the minimum arc-degree of D defined as ξ（D） = min {ξ′（xy） ： xy ∈ A}, and ξ′（xy） = min（｜ω＋（{x,y}）｜, ｜w-（{x,y}）｜, ｜w＋（x） ∪ w- （y） ｜, ｜w- （x） ∪ω＋ （y）｜}. In this paper a sufficient condition for a s-geodetic strongly connected digraph D to be λ′-optimal is given in terms of its diameter. Furthermore we see that the h-iterated line digraph Lh（D） of a s-geodetic digraph is λ′-optimal for certain iteration h.     

ON THE EXPONENT SET OF PRIMITIVELOCALLY SEMICOMPLETE DIGRAPHS

A locally semicomplete digraph is a digraph D=(V,A) satisfying the following condi-tion for every vertex x∈V the D[O(x)] and D[I(x)] are semicomplete digraphs. In this paper,we get some properties of cycles and determine the exponent set of primitive locally semicompleted digraphs.     

Improved upper and lower bounds for the spectral radius of digraphs

Let G be a digraph with n vertices and m arcs without loops and multiarcs. The spectral radius ρ(G) of G is the largest eigenvalue of its adjacency matrix. In this paper, sharp upper and lower bounds on ρ(G) are given. We show that some known bounds can be obtained from our bounds.     

Bounding the feedback vertex number of digraphs in terms of vertex degrees

The Turán bound (Turán (1941) [17]) is a famous result in graph theory, which relates the independence number of an undirected graph to its edge density. Also the Caro-Wei inequality (Caro (1979) [4] and Wei (1981) [18]), which gives a more refined bound in terms of the vertex degree sequence of a graph, might be regarded today as a classical result. We show how these statements can be generalized to directed graphs, thus yielding a bound on directed feedback vertex number in terms of vertex out-degrees and in terms of average out-degree, respectively.     

The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed digraph H, the homomorphism problem is to decide whether an input digraph D admits a homomorphism to H or not, and is denoted as HOM(H).An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in Gutin, Rafiey, Yeo and Tso (2006) [13]. If each vertex u∈V(D) is associated with costs c_i(u),i∈V(H), then the cost of the homomorphism f is ∑_u∈V(D)c_f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem forH and denote it as MinHOM(H). The problem is to decide, for an input graph D with costs c_i(u),u∈V(D),i∈V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost.Although a complete dichotomy classification of the complexity of MinHOM(H) for a digraph H remains an unsolved problem, complete dichotomy classifications for MinHOM(H) were proved when H is a semicomplete digraph Gutin, Rafiey and Yeo (2006) [10], and a semicomplete multipartite digraph Gutin, Rafiey and Yeo (2008) [12] and [11]. In these studies, it is assumed that the digraph H is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in Gutin and Kim (2008) [9].     

On the number of noncritical vertices in strongly connected digraphs

By definition, a vertex w of a strongly connected (or, simply, strong) digraph D is noncritical if the subgraph D — w is also strongly connected. We prove that if the minimal out (or in) degree k of D is at least 2, then there are at least k noncritical vertices in D. In contrast to the case of undirected graphs, this bound cannot be sharpened, for a given k, even for digraphs of large order. Moreover, we show that if the valency of any vertex of a strong digraph of order n is at least 3/4n, then it contains at least two noncritical vertices. The proof makes use of the results of the theory of maximal proper strong subgraphs established by Mader and developed by the present author. We also construct a counterpart of this theory for biconnected (undirected) graphs.     

On the existence of 3- and 4-kernels in digraphs

Let $D=(V\left(D\right),A\left(D\right))$ be a digraph. A subset $S?V\left(D\right)$ is $k$-independent if the distance between every pair of vertices of $S$ is at least $k$, and it is $?$-absorbent if for every vertex $u$ in $V\left(D\right)?S$ there exists $v\in S$ such that the distance from $u$ to $v$ is less than or equal to $?$. A $k$-kernel is a $k$-independent and $(k?1)$-absorbent set. A kernel is simply a $2$-kernel.A classical result due to Duchet states that if every directed cycle in a digraph $D$ has at least one symmetric arc, then $D$ has a kernel. We propose a conjecture generalizing this result for $k$-kernels and prove it true for $k=3$ and $k=4$.