On the weak distance-regularity of Moore-type digraphs

We prove that Moore digraphs, and some other classes of extremal digraphs, are weakly distance-regular in the sense that there is an invariance of the number of walks between vertices at a given distance. As weakly distance-regular digraphs, we then compute their complete spectrum from a ‘small’ intersection matrix. This is a very useful tool for deriving some results about their existence and/or their structural properties. For instance, we present here an alternative and unified proof of the existence results on Moore digraphs, Moore bipartite digraphs and, more generally, Moore generalized p-cycles. In addition, we show that the line digraph structure appears as a characteristic property of any Moore generalized p-cycle of diameter D?≥?2p.     

On Moore bipartite digraphs

In the context of the degree/diameter problem for directed graphs, it is known that the number of vertices of a strongly connected bipartite digraph satisfies a Moore‐like bound in terms of its diameter k and the maximum out‐degrees (d₁, d₂) of its partite sets of vertices. It has been proved that, when d₁d₂ > 1, the digraphs attaining such a bound, called Moore bipartite digraphs, only exist when 2 ≤ k ≤ 4. This paper deals with the problem of their enumeration. In this context, using the theory of circulant matrices and the so‐called De Bruijn near‐factorizations of cyclic groups, we present some new constructions of Moore bipartite digraphs of diameter three and composite out‐degrees. By applying the iterated line digraph technique, such constructions also provide new families of dense bipartite digraphs with arbitrary diameter. Moreover, we show that the line digraph structure is inherent in any Moore bipartite digraph G of diameter k = 4, which means that G = L G′, where G′ is a Moore bipartite digraph of diameter k = 3. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 171–187, 2003     

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.     

Local bases of primitive non-powerful signed digraphs

In 1994, Z. Li, F. Hall and C. Eschenbach extended the concept of the index of convergence from nonnegative matrices to powerful sign pattern matrices. Recently, Jiayu Shao and Lihua You studied the bases of non-powerful irreducible sign pattern matrices. In this paper, the local bases, which are generalizations of the base, of primitive non-powerful signed digraphs are introduced, and sharp bounds for local bases of primitive non-powerful signed digraphs are obtained. Furthermore, extremal digraphs are described.     

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.     

Gaussian integral circulant digraphs

The spectrum of a digraph in general contains real and complex eigenvalues. A digraph is called a Gaussian integral digraph if it has a Gaussian integral spectrum that is all eigenvalues are Gaussian integers. In this paper, we consider Gaussian integral digraphs among circulant digraphs.     

若干图的卡氏积的距离谱和距离能量(英文)

G是顶点集为{v_1,v_2,…,v_n}的连通简单图,G_1,G_2,…,G_n是有限图。联并图G[G_1,G_2,…,G_n】是按如下方式在G_1UG_2U…UG_n上加边而成的图:在G_i和G_j之间的任何两个顶点间加边,若v_i和v_j在G中相邻.[7]给出了两个距离正则图的卡氏积的距离谱.本文计算了联并图和距离正则图的卡氏积及两个联并图的卡氏积的距离谱.在此基础之上,我们得到了两个利用联并图与非同谱距离正则等能量图作卡氏积及联并图作卡氏积构造非同谱等距离能量图族的方法.     

Acyclically pushable bipartite permutation digraphs: An algorithm

Given a digraph D=(V,A) and an X⊆V, D^X denotes the digraph obtained from D by reversing those arcs with exactly one end in X. A digraph D is called acyclically pushable when there exists an X⊆V such that D^X is acyclic. Huang, MacGillivray and Yeo have recently characterized, in terms of two excluded induced subgraphs on 7 and 8 nodes, those bipartite permutation digraphs which are acyclically pushable. We give an algorithmic proof of their result. Our proof delivers an O(m²) time algorithm to decide whether a bipartite permutation digraph is acyclically pushable and, if yes, to find a set X such that D^X is acyclic. (Huang, MacGillivray and Yeo's result clearly implies an O(n⁸) time algorithm to decide but the polynomiality of constructing X was still open.)We define a strongly acyclic digraph as a digraph D such that D^X is acyclic for every X. We show how a result of Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1-3) (1999) 27-33] can be essentially regarded as a characterization of strongly acyclic digraphs and also provides linear time algorithms to find a strongly acyclic orientation of an undirected graph, if one exists. Besides revealing this connection, we add simplicity to the structural and algorithmic results first given in Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1-3) (1999) 27-33]. In particular, we avoid decomposing the graph into triconnected components.We give an alternate proof of a theorem of Huang, MacGillivray and Wood characterizing acyclically pushable bipartite tournaments. Our proof leads to a linear time algorithm which, given a bipartite tournament as input, either returns a set X such that D^X is acyclic or a proof that D is not acyclically pushable.     

On weakly cospectral graphs

We prove that any set of pair-wise nonisomorphic strongly connected weakly cospectral pseudodigraphs whose set of nilpotency indices is finite also is finite.     

New sufficient conditions for bipancyclicity of balanced bipartite digraphs

The main results provide sufficient conditions for balanced bipartite digraphs to be bipancyclic. These are analogues to well-known results on pancyclic digraphs.     

Linear arboricity of regular digraphs

A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.     

A note on total colourings of digraphs

In the paper two different arc-colourings and two associated with the total colourings of digraphs are considered. In one of these colourings we show that the problem of calculating the total chromatic index reduces to that of calculating the chromatic number of the underlying graph. In the other colouring we find the total chromatic indices of complete symmetric digraphs and tournaments.     

On the structure of strong 3-quasi-transitive digraphs

In this paper, D=(V(D),A(D)) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V(D). Given a digraph D, we say that D is 3-quasi-transitive if, whenever u→v→w→z in D, then u and z are adjacent or u=z. In Bang-Jensen (2004) [3], Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs.     

The kth upper and lower bases of primitive nonpowerful minimally strong signed digraphs

In this article, we study the kth upper and lower bases of primitive nonpowerful minimally strong signed digraphs. A bound on the kth upper bases for primitive nonpowerful minimally strong signed digraphs is obtained, and the equality case of the bound is characterized. For the kth lower bases, we obtain some bounds. For some cases, the bounds are best possible and the extremal signed digraphs are characterized. We also show that there exist ‘gaps’ in both the kth upper base set and the kth lower base set of primitive nonpowerful minimally strong signed digraphs.     

Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs

A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x,y, every in-neighbor of x and every in-neighbor of y either are adjacent or are the same vertex. A digraph is quasi-arc-transitive if for any arc xy, every in-neighbor of x and every out-neighbor of y either are adjacent or are the same vertex. Laborde, Payan and Xuong proposed the following conjecture: Every digraph has an independent set intersecting every non-augmentable path (in particular, every longest path). In this paper, we shall prove that this conjecture is true for arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs.