Weakly distance-regular digraphs

We introduce the concept of weakly distance-regular digraph and study some of its basic properties. In particular, the (standard) distance-regular digraphs, introduced by Damerell, turn out to be those weakly distance-regular digraphs which have a normal adjacency matrix. As happens in the case of distance-regular graphs, the study is greatly facilitated by a family of orthogonal polynomials called the distance polynomials. For instance, these polynomials are used to derive the spectrum of a weakly distance-regular digraph. Some examples of these digraphs, such as the butterfly and the cycle prefix digraph which are interesting for their applications, are analyzed in the light of the developed theory. Also, some new constructions involving the line digraph and other techniques are presented.     

Multipartite Moore digraphs

We derive some Moore-like bounds for multipartite digraphs, which extend those of bipartite digraphs, under the assumption that every vertex of a given partite set is adjacent to the same number δ of vertices in each of the other independent sets. We determine when a multipartite Moore digraph is weakly distance-regular. Within this framework, some necessary conditions for the existence of a r-partite Moore digraph with interpartite outdegree δ > 1 and diameter k = 2m are obtained. In the case δ = 1, which corresponds to almost Moore digraphs, a necessary condition in terms of the permutation cycle structure is derived. Additionally, we present some constructions of dense multipartite digraphs of diameter two that are vertex-transitive.     

A family of weakly distance-regular digraphs of girth 2

A family of commutative weakly distance-regular digraphs of girth 2 was classified in [K. Wang, Commutative weakly distance-regular digraphs of girth 2, European J. Combin. 25 (2004) 363-375]. In this paper, we classify this family of digraphs without the assumption of commutativity.     

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     

Complete characterization of almost Moore digraphs of degree three

It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In this paper, we prove that digraphs of degree three and diameter k ≥ 3 which miss the Moore bound by one do not exist. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 112–126, 2005     

A Family of Nonnormal Cayley Digraphs

We call a Cayley digraph Γ = Cay(G, S) normal for G if G _R , the right regular representation of G, is a normal subgroup of the full automorphism group Aut(Γ) of Γ. In this paper we determine the normality of Cayley digraphs of valency 2 on nonabelian groups of order 2p ² (p odd prime). As a result, a family of nonnormal Cayley digraphs is found. Received February 23, 1998, Revised September 25, 1998, Accepted October 27, 1998     

Disjoint quasi‐kernels in digraphs

A quasi‐kernel in a digraph is an independent set of vertices such that any vertex in the digraph can reach some vertex in the set via a directed path of length at most two. Chvátal and Lovász proved that every digraph has a quasi‐kernel. Recently, Gutin et al. raised the question of which digraphs have a pair of disjoint quasi‐kernels. Clearly, a digraph has a pair of disjoint quasi‐kernels cannot contain sinks, that is, vertices of outdegree zero, as each such vertex is necessarily included in a quasi‐kernel. However, there exist digraphs which contain neither sinks nor a pair of disjoint quasi‐kernels. Thus, containing no sinks is not sufficient in general for a digraph to have a pair of disjoint quasi‐kernels. In contrast, we prove that, for several classes of digraphs, the condition of containing no sinks guarantees the existence of a pair of disjoint quasi‐kernels. The classes contain semicomplete multipartite, quasi‐transitive, and locally semicomplete digraphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:251‐260, 2008     

Distance-regular digraphs of girth 4 over an extension ring of Z/4Z

Enomoto-Mena[1] showed that two one-parameter families of distance-regular digraphs of girth 4 could possibly exist. Subsequently Liebler-Mena[2] found an infinite family of such digraphs generated over an extension ring ofZ/4Z. We prove that there are no other solutions except for multiplication by principal units to generate distance-regular digraphs of girth 4 under their method. In order to prove this, we introduce Gauss sums and three kinds of Jacobi sums over an extension ring ofZ/4Z. We give necessary and sufficient conditions for the existence of these digraphs under that method. It turns out that the Liebler-Mena solutions are the only solutions which satisfy the necessary and sufficient conditions. This fact has been conjectured for a time, but has never been proved.     

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.     

Procreating tiles of double commutative-step digraphs

Double commutative-step digraph generalizes the double-loop digraph. A double commutative-step digraph can be represented by an L-shaped tile, which periodically tessellates the plane. Given an initial tile L（l, h, x, y）, Aguil5 et al. define a discrete iteration L（p） = L（l ＋ 2p, h ＋ 2p, x ＋ p, y ＋ p）, p = 0, 1, 2,..., over L-shapes （equivalently over double commutative-step digraphs）, and obtain an orbit generated by L（l, h, x,y）, which is said to be a procreating k-tight tile if L（p）（p = 0, 1, 2, ~ ~ ~ ） are all k-tight tiles. They classify the set of L-shaped tiles by its behavior under the above-mentioned discrete dynamics and obtain some procreating tiles of double commutative-step digraphs. In this work, with an approach proposed by Li and Xu et al., we define some new discrete iteration over L-shapes and classify the set of tiles by the procreating condition. We also propose some approaches to find infinite families of realizable k-tight tiles starting from any realizable k-tight L-shaped tile L（l, h, x, y）, 0 ≤ y - x ≤ 2k ＋ 2. As an example, we present an infinite family of 3-tight optimal double-loop networks to illustrate our approaches.     

On Arc-Regular Permutation Groups Using Latin Squares

For a given a permutation group G, the problem of determining which regular digraphs admit G as an arc-regular group of automorphism is considered. Groups which admit such a representation can be characterized in terms of generating sets satisfying certain properties, and a procedure to manufacture such groups is presented. The technique is based on constructing appropriate factorizations of (smaller) regular line digraphs by means of Latin squares. Using this approach, all possible representations of transitive groups of degree up to seven as arc-regular groups of digraphs of some degree is presented.Partially supported by the Comissionat per a Universitats i Recerca of the Generalitat de Catalunya under Grant 1997FI-693, and through a European Community Marie Curie Fellowship under contract HPMF-CT-2001-01211.     

Limit points of eigenvalues of (di)graphs

The study on limit points of eigenvalues of undirected graphs was initiated by A. J. Hoffman in 1972. Now we extend the study to digraphs. We prove 1. Every real number is a limit point of eigenvalues of graphs. Every complex number is a limit point of eigenvalues of digraphs. 2. For a digraph D, the set of limit points of eigenvalues of iterated subdivision digraphs of D is the unit circle in the complex plane if and only if D has a directed cycle. 3. Every limit point of eigenvalues of a set D of digraphs (graphs) is a limit point of eigenvalues of a set of bipartite digraphs (graphs), where consists of the double covers of the members in D. 4. Every limit point of eigenvalues of a set D of digraphs is a limit point of eigenvalues of line digraphs of the digraphs in D. 5. If M is a limit point of the largest eigenvalues of graphs, then −M is a limit point of the smallest eigenvalues of graphs.     

Cayley Digraphs of Finite Simple Groups with Small Out-Valency

Abstract

For a group G and a subset S of G which does not contain the identity of G, the Cayley digraph Cay(G, S) is called normal if R(G) is normal in Aut(Γ). In this paper, we investigate the normality of Cayley digraphs of finite simple groups with out-valency 2 and 3. We give several sufficient conditions for such Cayley digraphs to be normal. By using this result, we consider the digraphical regular representations of finite simple groups.     

On large vertex-symmetric digraphs

There is special interest in the design of large vertex-symmetric graphs and digraphs as models of interconnection networks for implementing parallelism. In these systems, a large number of nodes are connected with relatively few links and short paths between the nodes, and each node may execute the same communication software without modifications.In this paper, a method for obtaining new general families of large vertex-symmetric digraphs is put forward. To be more precise, from a k-reachable vertex-symmetric digraph and another (k+1)-reachable digraph related to the previous one, and using a new special composition of digraphs, new families of vertex-symmetric digraphs with small diameter are presented. With these families we obtain new vertex-symmetric digraphs that improve various values of the table of the largest known vertex-symmetric (Δ,D)-digraphs. The paper also contains the (Δ,D)-table for vertex-symmetric digraphs, for Δ≤13 and D≤12.     

广义de Bruijn有向图及其叠线图的支撑树与欧拉环游的计数

给出了一类特殊的广义deBruijn有向图的支撑树与欧环游的数目的简洁表示式，并得到了广义deBruijn有向叠线图的支撑树与欧拉环境数目的计算公式。     

Distance-regular subgraphs in a distance-regular graph, II

Let Γ be a distance-regular graph with r = l(1, a₁, b₁), a₁ > 0 and c_2r+1 = 1. We show the existence of a collinearity graph of a Moore geometry of diameter r + 1 as a subgraph in Γ. In particular, we show that r = 1.     

The Basis Digraphs of <Emphasis Type="Italic">p</Emphasis>-schemes

It is proved that association schemes with bipartite basis graphs are exactly 2-schemes. This result follows from a characterization of p-schemes for an arbitrary prime p in terms of basis digraphs. Second author work was partially supported by RFFI Grants 07-01-00485, 08-01-00379 and 08-01-00640. First author was visiting the Euler Institute of Mathematics, St. Petersburg, Russia during the time a part of this paper was written and he thanks the Euler Institute for its hospitality     

On Hamiltonicity of circulant digraphs of outdegree three

This paper deals with Hamiltonicity of connected loopless circulant digraphs of outdegree three with connection set of the form {a,ka,c}, where k is an integer. In particular, we prove that if k=−1 or k=2 such a circulant digraph is Hamiltonian if and only if it is not isomorphic to the circulant digraph on 12 vertices with connection set {3,6,4}.     

The diameters of almost all Cayley digraphs

1.IntroductionLetGbeagroupandSasubsetofGnotcontainingtheidentity,1ofG.TheCayleydigraphofGwithrespecttoS,denotedbyX(G,S),isadigraphwhosevertexsetisGandforx,yEG,thereisanarcfromxtoyinX(G,S)ifandonlyifx--laES.IfS=S--',thenX(G,S)isactuallyagraphcalledCayleygraph.ThereisadiversityofliteratureonCnyleygraphsandCayleydigraphs.Themostlyinvestigatedsubjectsaretheconnectivityll'2],theHamiltonianpropertiesl3],theisomorphismsI4]andthediameterIS'6].Recelltly,someauthorsproposedtouseCayleygraph…     

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.