4p阶二面体群连通3度Cayley有向图的正规性

设G是一个有限群,S是G的不包含单位元1的非空子集,定义群G关于S的Cayley(有向)图X:=Cay(G,S)如下:V(X)=G,E(X)={(g,sg)|g∈G,s∈S}.Cayley(有向)图X:=Cay(G,S)称为正规的,如果G的右正则表示R(G)在X的自同构群Aut(X)中是正规的.设G是4p阶二面体群(p为素数).考察了Cay(G,S)连通3度的正规性,并给出了这些图的全自同构群.     

关于有向图代数中Lie理想的注记

本文加深了Hopenwasser和Paulsen关于有向图代数中Lie理想的一个结果,证明了有向图代数A的一个线性子空间是A的Lie理想当且仅当存在A的一个结合理想Y及A的masa D的一个子代数E,使得(Y)~0■■Y+E,其中(Y)~0是Y中迹为零的所有元的集合．     

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.     

Small stable generic graphs with infinite weight. Digraphs without furcations

Grounding on Herwig’s generic construction that modifies Hrushovski’s construction, we give some examples of small stable theories of digraphs without furcations which have an infinite weight.     

对称本原图的集指数与本原简单图的广义上指数的极图

一个有向图D称为本原的，如果存在某个正整数k，使得对于D中的任一点x到任一点y都有长为k的途径，这样的正整数k中的最小者称为D的本原指数，作为本原指数概念的推广，R．A．Brualdi和柳柏濂于1990年引入了本原有向图的广义本原指数的新概念，本文给出了对称本原图的集指数的一些性质，并对本原简单图的广义上指数的极图进行了完全刻划。     

De Bruijn digraphs and affine transformations

Let be the additive group of 1×n row vectors over . For an n×n matrix T over  and , the affine transformation F_T,ω of sends x to xT+ω. Let α be the cyclic group generated by a vector . The affine transformation coset pseudo-digraph has the set of cosets of α in as vertices and there are c arcs from x+α to y+α if and only if the number of zx+α such that F_T,ω(z)y+α is c. We prove that the following statements are equivalent: (a)  is isomorphic to the d-nary (n−1)-dimensional De Bruijn digraph; (b) α is a cyclic vector for T; (c)  is primitive. This strengthens a result conjectured by C.M. Fiduccia and E.M. Jacobson [Universal multistage networks via linear permutations, in: Proceedings of the 1991 ACM/IEEE Conference on Supercomputing, ACM Press, New York, 1991, pp. 380–389]. Under the further assumption that T is invertible we show that each component of is a conjunction of a cycle and a De Bruijn digraph, namely a generalized wrapped butterfly. Finally, we discuss the affine TCP digraph representations for a class of digraphs introduced by D. Coudert, A. Ferreira and S. Perennes [Isomorphisms of the De Bruijn digraph and free-space optical networks, Networks 40 (2002) 155–164].     

线图和有向线图的第二等周点连通度

证明了最小度大于等于2的强连通有向线图的第二等周点连通度等于它的点连通度.对于无向线图,给出了第二等周点连通度存在的充要条件,并且证明了在第二等周点连通度存在的前提下它或者等于限制点连通度或者等于d1 d2,其中d1和d2分别是最小和次小度.     

Concerning two conjectures on the set of fixed points of a complete rotation of a Cayley digraph

In 1996, J.C. Bermond, T. Kodate, S. Perennes and N. Marlin conjectured that the set F_σ of fixed points of some complete rotation σ of the toroidal mesh TM(p)^k is not separating (that is F_σ does not disconnect TM(p)^k). They also conjectured that the set F_ω of fixed points of any complete rotation ω of any Cayley digraph is not separating. In this paper, we prove the first conjecture and disprove the second one.     

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.     

Okhuma Graphs and Coloured Chains

A structure is said to be ‘Okhuma’ if its automorphism group acts on it uniquely transitively, or slightly generalizing this, if its automorphism group acts uniquely transitively on each orbit. In this latter case we can think of the orbits as ‘colours’. Okhuma chains and related structures have been studied by Okhuma and others. Here we generalize their results to coloured chains, and give some constructions resulting from this of Okhuma graphs and digraphs. Mathematics Subject Classifications (2000) 06A05, 06F15.