On semisymmetric cubic graphs of order 6p~2

A graph r is said to be G-semisymmetric if it is regular and there exists a subgroup G of A := Aut(Г) acting transitively on its edge set but not on its vertex set. In the case of G. = A, we call r a semisymmetric graph. The aim of this paper is to investigate (G-)semisymmetric graphs of prime degree. We give a group-theoretical construction of such graphs, and give a classification of semisymmetric cubic graphs of order 6p2 for an odd prime p.     

Cubic one-regular graphs of order twice a square-free integer

A graph is one-regular if its automorphism group acts regularly on the set of its arcs.Let n be a square-free integer.In this paper,we show that a cubic one-regular graph of order 2n exists if and only if n=3~tp1p2…p_s≥13,where t≤1,s≥1 and p_i's are distinct primes such that 3|(P_i—1). For such an integer n,there are 2~(s-1) non-isomorphic cubic one-regular graphs of order 2n,which are all Cayley graphs on the dihedral group of order 2n.As a result,no cubic one-regular graphs of order 4 times an odd square-free integer exist.     

一类半对称图的构造

称一个有限简单无向图X是半对称图,如果图X是正则的且边传递但非点传递.主要利用仿射几何构造了一类2p~n阶连通p~3。度的半对称图的无限族,其中p≥n≥8.     

Cubic semisymmetric graphs of order 8p~3

A regular edge-transitive graph is said to be semisymmetric if it is not vertex-transitive.By Folkman [J.Combin.Theory 3(1967),215-232],there is no semisymmetric graph of order 2p or 2p 2 for a prime p,and by Malni et al.[Discrete Math.274(2004),187-198],there exists a unique cubic semisymmetric graph of order 2p 3,the so called Gray graph of order 54.In this paper,it is shown that there is no connected cubic semisymmetric graph of order 4p 3 and that there exists a unique cubic semisymmetric graph of orde...     

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

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

一类用仿射几何构造的半对称图

图X是一个有限简单无向图,如果图X是正则的且边传递但非点传递,则称X是半对称图.主要利用仿射几何构造了一类2p~n阶连通p~4度的半对称图的无限族,其中p≥n≥11.     

Classifying cubic symmetric graphs of order 10p or 10p~2

A graph is called s-regular if its automorphism group acts regularly on the set of its s-arcs. In this paper, the s-regular cyclic or elementary abelian coverings of the Petersen graph for each s ≥ 1 are classified when the fibre-preserving automorphism groups act arc-transitively. As an application of these results, all s-regular cubic graphs of order 10p or 10p2 are also classified for each s ≥ 1 and each prime p, of which the proof depends on the classification of finite simple groups.     

New families of strongly regular graphs

We apply symmetric balanced generalized weighing matrices with zero diagonal to construct four parametrically new infinite families of strongly regular graphs. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 208–217, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10038     

Weighted scattering matrices of regular coverings of graphs

We give a decomposition formula for the determinant det(I ? U(λ)) of the weighted bond scattering matrix U(λ) of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express some determinant of the weighted bond scattering matrix of a regular covering of G by means of its L-functions.     

An infinite series of regular edge‐ but not vertex‐transitive graphs

Let n be an integer and q be a prime power. Then for any 3 ≤ n ≤ q?1, or n=2 and q odd, we construct a connected q‐regular edge‐but not vertex‐transitive graph of order 2qⁿ⁺¹. This graph is defined via a system of equations over the finite field of q elements. For n=2 and q=3, our graph is isomorphic to the Gray graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 249–258, 2002     

An infinite family of biprimitive semisymmetric graphs

A regular and edge-transitive graph that is not vertex-transitive is said to be semisymmetric. Every semisymmetric graph is necessarily bipartite, with the two parts having equal size and the automorphism group acting transitively on each of these two parts. A semisymmetric graph is called biprimitive, if its automorphism group acts primitively on each part. In this article, a classification of biprimitive semisymmetric graphs arising from the action of the group PSL(2, p), p ≡ ±1 (mod 8) a prime, acting on cosets of S₄ is given, resulting in several new infinite families of biprimitive semisymmetric graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 217–228, 1999     

K3,3-free intersection graphs of finite groups

The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper we classify all finite groups whose intersection graphs are K_3,3-free.     

Short cycle covers of cubic graphs

Let G be a bridgeless cubic graph. We prove that the edges of G can be covered by circuits whose total length is at most (44/27) |E(G)|, and if Tutte's 3-flow Conjecture is true, at most (92/57) |E(G)|.     

1-factor covers of regular graphs

We consider minimal 1-factor covers of regular multigraphs, focusing on those that are 1-factorizations. In particular, we classify cubic graphs such that every minimal 1-factor cover is also a 1-factorization, and also classify simple regular bipartite graphs with this property. For r>3, we show that there are finitely many simple r-regular graphs such that every minimal 1-factor cover is also a 1-factorization.     

s‐Regular cubic graphs as coverings of the complete bipartite graph K3,3

A graph is s‐regular if its automorphism group acts freely and transitively on the set of s‐arcs. An infinite family of cubic 1‐regular graphs was constructed in [10], as cyclic coverings of the three‐dimensional Hypercube. In this paper, we classify the s‐regular cyclic coverings of the complete bipartite graph K_3,3 for each ≥ 1 whose fibre‐preserving automorphism subgroups act arc‐transitively. As a result, a new infinite family of cubic 1‐regular graphs is constructed. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 101–112, 2004     

Bipartite density of cubic graphs

We first obtain the exact value for bipartite density of a cubic line graph on n vertices. Then we give an upper bound for the bipartite density of cubic graphs in terms of the smallest eigenvalue of the adjacency matrix. In addition, we characterize, except in the case n=20, those graphs for which the upper bound is obtained.     

Weighted zeta functions for quotients of regular coverings of graphs

Let G be a connected graph. We reformulate Stark and Terras' Galois Theory for a quotient H of a regular covering K of a graph G by using voltage assignments. As applications, we show that the weighted Bartholdi L-function of H associated to the representation of the covering transformation group of H is equal to that of G associated to its induced representation in the covering transformation group of K. Furthermore, we express the weighted Bartholdi zeta function of H as a product of weighted Bartholdi L-functions of G associated to irreducible representations of the covering transformation group of K. We generalize Stark and Terras' Galois Theory to digraphs, and apply to weighted Bartholdi L-functions of digraphs.