4p阶3度点传递图

一个图称为点传递图,如果它的全自同构群在它的顶点集合上作用传递.证明了一个4p(p为素数)阶连通3度点传递图或者是Cayley图,或者同构于下列之一;广义Petersen图P(10,2),正十二面体,Coxeter图,或广义Petersen图P(2p,k),这里k2≡-1(mod 2p).     

广义Petersen图的宽直径

广义Petersen图是一类重要的并被广泛研究的互连网络。本文证明了广义Petersen图 P(m,2)的直径和3宽直径分别为O(m/4)和O(m/3)。     

2p2阶3度点传递图

一个图称为点传递图,如果它的全自同构群在它的顶点集合上作用传递.本文证明了一个2p～2（p为素数）阶连通3度点传递图或者是Calyley图,或者同构于广义Petersen图P（p～2,t）,这里t～2≡-1（modp～2）.     

G(2m+1,m)的不可定向强最大亏格

图G的最大亏格指图G能嵌入到亏格为k的曲面的最大整数k.对于广义Petersen图G(2m 1,m),当m=1,4(mod 6),给出了最大亏格的表达式,对其余形,给出了不可定向强最大亏格的上界和下界.     

4p~2阶4度半传递图

如果图X的全自同构群Aut(X)作用在其顶点集V(X)和边集E(X)上都是传递的,但作用在弧集Arc(X)上非传递,则称X是半传递图.研究了4p~2(p3且p≡-1(mod4))阶4度半传递图,确定了4p~2阶4度半传递图的连通性及其自同构群的阶.     

图的逆符号边全控制数

设γ_(st)(G)是图G的逆符号边全控制数,p(n,k)是广义Petersen图.得到了γ_(st)(G)的两个上界,并且确定了γ_(st)(p(n,k)).     

Petersen图的点传递正则覆盖图

运用基图自同构能被提升的线性准则 ,对满足 :1覆叠变换群 K =Znp,2覆盖图的保簇变换群是点传递的 Petersen图的连通正则覆盖图进行了完全分类 .这种图共有 1 2种类型 .     

广义字典序积的自同态幺半群

讨论了图的广义字典序积的自同态幺半群的性质,给出了广义字典序积图X[Yz|x∈V（X）]的自同态幺半群与X,Yx(x∈V(X))的自同态幺半群的圈积相等的充要条件。     

广义联图的正则性

讨论了两个图的广义联图的End-正则性,给出了当图X、Y的广义联图G（y1,…ym）End-正则时,图X也End-正则应满足的条件。     

第二小阶数的双本原半对称图

如果一个正则图是边传递但不是点传递的,那么我们称它是半对称的.每一个半对称图X必定是两部分点数相等的二部图,并且它的自同构群Aut(X)在每一部分上是传递的.如果一个半对称图的自同构群在每一部分上作用是本原的,那么我们称它是双本原的.本文决定了第二小阶数的双本原半对称图.     

Hexavalent symmetric graphs of order 9p

A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. In this paper, we classify hexavalent symmetric graphs of order $9p$ for each prime $p$.     

三度边正则图的三个无限族

图X称为边正则图，若X的自同构群Aut(X)在X的边集上的作用是正则的．本文考察了三度边正则图与四度Cayley图的关系，给出了一个由四度Cayley图构造三度边正则图的方法，并且构造了边正则图的三个无限族．     

Hypohamiltonian Planar Cubic Graphs with Girth 5

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.     

Edge-primitive Cayley graphs on abelian groups and dihedral groups

A graph is called edge-primitive if its automorphism group acts primitively on its edge set. In 1973, Weiss (1973) determined all edge-primitive graphs of valency three, and recently Guo et al. (2013,2015) classified edge-primitive graphs of valencies four and five. In this paper, we determine all edge-primitive Cayley graphs on abelian groups and dihedral groups.     

Semisymmetric cubic graphs as regular covers of K 3,3

A regular graph X is called semisymmetric if it is edge-transitive but not vertex-transitive. For G ≤ AutX, we call a G-cover X semisymmetric if X is semisymmetric, and call a G-cover X one-regular if Aut X acts regularly on its arc-set. In this paper, we give the sufficient and necessary conditions for the existence of one-regular or semisymmetric Zn-Covers of K3,3. Also, an infinite family of semisymmetric Zn×Zn-covers of K3,3 are constructed.     

Classification of a family of symmetric graphs with complete 2-arc-transitive quotients

In this paper we give a classification of a family of symmetric graphs with complete 2-arc-transitive quotients. Of particular interest are two subfamilies of graphs which admit an arc-transitive action of a projective linear group. The graphs in these subfamilies can be defined in terms of the cross ratio of certain 4-tuples of elements of a finite projective line, and thus may be called the second type ‘cross ratio graphs’, which are different from the ‘cross ratio graphs’ studied in [A. Gardiner, C. E. Praeger, S. Zhou, Cross-ratio graphs, J. London Math. Soc. (2) 64 (2001), 257–272]. We also give a combinatorial characterisation of such second type cross ratio graphs.     

A Local Analysis of Imprimitive Symmetric Graphs

Let Г be a G-symmetric graph admitting a nontrivial G-invariant partition . Let Г be the quotient graph of Г with respect to . For each block B ∊ , the setwise stabiliser G_B of B in G induces natural actions on B and on the neighbourhood Г (B) of B in Г . Let G_(B) and G_[B] be respectively the kernels of these actions. In this paper we study certain “local actions" induced by G_(B) and G_[B], such as the action of G_[B] on B and the action of G_(B) on Г (B), and their influence on the structure of Г. Supported by a Discovery Project Grant (DP0558677) from the Australian Research Council and a Melbourne Early Career Researcher Grant from The University of Melbourne.     

On triconnected and cubic plane graphs on given point sets

Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.     

On the Dot Product Graph of a Commutative Ring

Let A be a commutative ring with nonzero identity, 1 ≤ n < ∞ be an integer, and R = A × A × … ×A (n times). The total dot product graph of R is the (undirected) graph TD(R) with vertices R* = R?{(0, 0,…, 0)}, and two distinct vertices x and y are adjacent if and only if x·y = 0 ∈ A (where x·y denote the normal dot product of x and y). Let Z(R) denote the set of all zero-divisors of R. Then the zero-divisor dot product graph of R is the induced subgraph ZD(R) of TD(R) with vertices Z(R)* = Z(R)?{(0, 0,…, 0)}. It follows that each edge (path) of the classical zero-divisor graph Γ(R) is an edge (path) of ZD(R). We observe that if n = 1, then TD(R) is a disconnected graph and ZD(R) is identical to the well-known zero-divisor graph of R in the sense of Beck–Anderson–Livingston, and hence it is connected. In this paper, we study both graphs TD(R) and ZD(R). For a commutative ring A and n ≥ 3, we show that TD(R) (ZD(R)) is connected with diameter two (at most three) and with girth three. Among other things, for n ≥ 2, we show that ZD(R) is identical to the zero-divisor graph of R if and only if either n = 2 and A is an integral domain or R is ring-isomorphic to ?₂ × ?₂ × ?₂.