CONNECTIVITIES OF RANDOM CIRCULANT DIGRAPHS

ＣＯＮＮＥＣＴＩＶＩＴＩＥＳＯＦＲＡＮＤＯＭＣＩＲＣＵＬＡＮＴＤＩＧＲＡＰＨＳ￥ＭＥＮＧＪＩＸＩＡＮＧＡＮＤＨＵＡＮＧＱＩＯＮＧＸＩＡＮＧＡｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒｌｗｅｐｒｏｖｅｔｈａｔａｌｍｏｓｔａｌｌｃｉｒｃｕｌａｎｔｄｉｇｒａｐ...     

Infinite Circulant Digraphs and Random Infinite Circulant Digraphs

In this paper, we completely determine the connectivity of every infinite circulant digraphs and prove that almost all infinite circulant digraphs are infinitely strongly connected and therefore have both one- and two-way infinite Hamiltonian paths. Received February 4, 1998, Accepted May 16, 2002     

Recognizing Knödel graphs

Knödel graphs form a class of bipartite incident-graph of circulant digraphs. This class has been extensively studied for the purpose of fast communications in networks, and it has deserved a lot of attention in this context. In this paper, we show that there exists an O(n log⁵ n)-time algorithm to recognize Knödel graphs of order 2n. The algorithm is based on a characterization of the cycles of length six in these graphs (bipartite incident-graphs of circulant digraphs always have cycles of length six). A consequence of our result is that the circulant digraphs whose chords are the power of two minus one can be recognized in O(n log⁵ n) time.     

Circulant digraphs determined by their spectra

Inspired by Ádám's conjecture the isomorphism problem of circulant digraphs is widely investigated. In the literature, the spectrum method was to solve the isomorphism problem for the circulants of prime-power order by some people. In this paper, we develop the spectrum method to characterize the circulant digraphs of orders p^a and p^aq^b, where p and q are distinct primes.     

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.     

4度对称循环图的分类(英文)

本文刻划了所有4度有向和无内循环图．     

Classification of Symmetric Circulants of Degree 4

4-tegular symmetric circulant digraphs and graphs are classified in this paper.     

A class of vertex-transitive digraphs,II

(1). We determine the number of non-isomorphic classes of self-complementary circulant digraphs with pq vertices, where p and q are distinct primes. The non-isomorphic classes of these circulant digraphs with pq vertices are enumerated. (2). We also determine the number of non-isomorphic classes of self-complementary, vertex-transitive digraphs with a prime number p vertices, and the number of self-complementary strongly vertex-transitive digraphs with p vertices. The non-isomorphic classes of strongly vertex-transitive digraphs with p vertices are also enumerated.     

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

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     

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     

有向循环图寻径控制

有向循环图 G(N ;1 ,s)作为有向双环网的图论模型备受关注 .本文将图的点集分划为几个不交子集 ,找到任意节点对之间路径沿跳长为 1和跳长为 s的边数的上确界 .找到了判断节点对间最短路径的充要条件 ,利用点集的分布特征设计了一个最优寻径算法 .对双环网络的容错路径进行了深入研究 ,给出了容错直径公式 ,提出了一个最优容错路径算法 .     

Common circulant homogeneous factorisations of the complete digraph

In this paper we determine the positive integers n and k for which there exists a homogeneous factorisation of a complete digraph on n vertices with k ‘common circulant’ factors. This means a partition of the arc set of the complete digraph K_n into k circulant factor digraphs, such that a cyclic group of order n acts regularly on the vertices of each factor digraph whilst preserving the edges, and in addition, an overgroup of this permutes the factor digraphs transitively amongst themselves. This determination generalises a previous result for self-complementary circulants.     

Which Faber–Moore–Chen digraphs are Cayley digraphs?

The problem of finding the largest graphs and digraphs of given degree and diameter is known as the ‘degree–diameter’ problem. One of the families of largest known vertex-transitive digraphs of given degree and diameter is the Faber–Moore–Chen digraphs. In our contribution we will classify those Faber–Moore–Chen digraphs that are Cayley digraphs.     

N-reconstructibility of non-reconstructible digraphs

In this paper we prove that all the non-reconstructible digraphs constructed by Stockmeyer in [3] are reconstructible from their point-deleted subdigraphs with the additional knowledge of the degree pair of the deleted point for each point-deleted subdigraph.     

ON ARC-TRANSITIVE CIRCULANT DIGRAPHS

Denote by c,(s)the circulant digraph with vertex set zn=[0,1,2……n-1]and symbol set s(≠-s)∈zn\[0].let x be the automorphism group of cn(S)and xo the stabilizer of o in x.then cn(S)is arctransitive if and only if xo acts transitively on s.in this paper,co(S)with xo is being the symmetric group is characterized by its symbot set .by the way all the arctransitive clcculant digraphs of degree 2are given.     

Double-super-connected digraphs

A strongly connected digraph D is said to be super-connected if every minimum vertex-cut is the out-neighbor or in-neighbor set of a vertex. A strongly connected digraph D is said to be double-super-connected if every minimum vertex-cut is both the out-neighbor set of a vertex and the in-neighbor set of a vertex. In this paper, we characterize the double-super-connected line digraphs, Cartesian product and lexicographic product of two digraphs. Furthermore, we study double-super-connected Abelian Cayley digraphs and illustrate that there exist double-super-connected digraphs for any given order and minimum degree.     

Arc-Disjoint and Edge-Disjoint Hamilton Cycles in Circulants with Two Jumps

In this paper we give new necessary and sufficient conditions for a directed circulant with vertices of outdegree two to have a pair of arc-disjoint Hamilton cycles. These conditions explicitly identify a pair of arc-disjoint Hamilton cycles if such cycles exist. In addition, we give necessary and sufficient conditions for an undirected circulant with vertices of degree four to have a specific pair of edge-disjoint Hamilton cycles.     

Rainbow Connection in Some Digraphs

An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. This concept was introduced by Chartrand et al. (Math Bohemica 133(1):85–98, 2008), and it was extended to oriented graphs by Dorbec et al. (Discrete Appl Math 179(31):69–78, 2014). In this paper we present some results regarding this extension, mostly for the case of circulant digraphs.     

具有位数3和4的双随机循环矩阵中的素元

本文研究了双随机循环矩阵中素元的分类问题．由于任一n阶双随机循环矩阵都可以唯一地表示为移位的n-1次一元多项式,从而可把双随机循环矩阵中素元的分类问题简化为解双随机循环矩阵上的一个方程．应用此原理,本文完全解决了判别具有位数3的n阶双随机循环矩阵是否为素元的问题,并给出了n阶双随机循环矩阵中一类具有位数4的素元．