Optimally super-edge-connected transitive graphs

Let X=(V,E) be a connected regular graph. X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ′(X) of X is the minimum number of edges whose removal disconnects X into non-trivial components. A super-edge-connected k-regular graph is said to be optimally super-edge-connected if its restricted edge connectivity attains the maximum 2k−2. In this paper, we define the λ′-atoms of graphs with respect to restricted edge connectivity and show that if X is a k-regular k-edge-connected graph whose λ′-atoms have size at least 3, then any two distinct λ′-atoms are disjoint. Using this property, we characterize the super-edge-connected or optimally super-edge-connected transitive graphs and Cayley graphs. In particular, we classify the optimally super-edge-connected quasiminimal Cayley graphs and Cayley graphs of diameter 2. As a consequence, we show that almost all Cayley graphs are optimally super-edge-connected.     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Two sufficient conditions for non-normal Cayley graphs and their applications

A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in the full automorphism group of Cay(G, S). In this paper, two sufficient conditions for non-normal Cayley graphs are given and by using the conditions, five infinite families of connected non-normal Cayley graphs are constructed. As an application, all connected non-normal Cayley graphs of valency 5 on A5 are determined, which generalizes a result about the normality of Cayley graphs of valency 3 or 4 on A5 determined by Xu and Xu. Further, we classify all non-CI Cayley graphs of valency 5 on A5, while Xu et al. have proved that As is a 4-CI group.     

Semi-hyper-connected vertex transitive graphs

A graph G is said to be semi-hyper-connected if the removal of every minimum cut of G creates exactly two connected components. In this paper, we characterize semi-hyper-connected vertex transitive graphs, in particular Cayley graphs.     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

On normal 2-geodesic transitive Cayley graphs

We investigate connected normal 2-geodesic transitive Cayley graphs Cay(T,S). We first prove that if Cay(T,S) is neither cyclic nor K_4[2], then 〈a〉?{1}??S for all a∈S. Next, as an application, we give a reduction theorem proving that each graph in this family which is neither a complete multipartite graph nor a bipartite 2-arc transitive graph, has a normal quotient that is either a complete graph or a Cayley graph in the family for a characteristically simple group. Finally we classify complete multipartite graphs in the family.     

Regular Balanced Cayley Maps for Cyclic, Dihedral and Generalized Quaternion Groups

A Cayley map is a Cayley graph embedded in an orientable surface such that. the local rotations at every vertex are identical. In this paper, balanced regular Cayley maps for cyclic groups, dihedral groups, and generalized quaternion groups are classified.     

Tetravalent vertex‐transitive graphs of order 4p

A graph is vertex‐transitive if its automorphism group acts transitively on vertices of the graph. A vertex‐transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this article, the tetravalent vertex‐transitive non‐Cayley graphs of order 4p are classified for each prime p. As a result, there are one sporadic and five infinite families of such graphs, of which the sporadic one has order 20, and one infinite family exists for every prime p>3, two families exist if and only if p≡1 (mod 8) and the other two families exist if and only if p≡1 (mod 4). For each family there is a unique graph for a given order. © 2011 Wiley Periodicals, Inc.     

The vertex-transitive TLF-planar graphs

We consider the class of the topologically locally finite (in short TLF) planar vertex-transitive graphs. We characterize these graphs by finite combinatorial objects called labeling schemes. As a result, we are able to enumerate and describe all TLF-planar vertex-transitive graphs of given degree, as well as most of their transitive groups of automorphisms. In addition,we are able to decide whether a given TLF-planar transitive graph is Cayley or not. This class contains all the one-ended planar Cayley graphs and the normal transitive tilings of the plane.     

Planar embeddings with infinite faces

We investigate vertex‐transitive graphs that admit planar embeddings having infinite faces, i.e., faces whose boundary is a double ray. In the case of graphs with connectivity exactly 2, we present examples wherein no face is finite. In particular, the planar embeddings of the Cartesian product of the r‐valent tree with K₂ are comprehensively studied and enumerated, as are the automorphisms of the resulting maps, and it is shown for r = 3 that no vertex‐transitive group of graph automorphisms is extendable to a group of homeomorphisms of the plane. We present all known families of infinite, locally finite, vertex‐transitive graphs of connectivity 3 and an infinite family of 4‐connected graphs that admit planar embeddings wherein each vertex is incident with an infinite face. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 257–275, 2003     

Almost all Cayley graphs are hamiltonian

It has been conjectured that there is a hamiltonian cycle in every finite connected Cayley graph. In spite of the difficulty in proving this conjecture, we show that almost all Cayley graphs are hamiltonian. That is, as the order n of a groupG approaches infinity, the ratio of the number of hamiltonian Cayley graphs ofG to the total number of Cayley graphs ofG approaches 1.Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University.     

HAMILTONIAN DECOMPOSITION OF CAYLEY GRAPHS OF ORDERS p~2 AND pq

1. IntroductionLet G be a finite group and S a subset of G such that S--1 ~ S, and 1 f S. The Cayleygraph Cay (G, S) is defined as the simple graph with V ~ G, and E = {glgZ I g,'g, or g,'g,6 S, gi, gi E G}. Cay (G, S) is vertex-transitive, and it is connected if and only if (S) = G,i.e. S is a generating set of G[1]. If G = Zn, then Cay (Zn, S) is called a circulant graph. Ithas been proved that any connected Cayley graph on a finite abelian group is hamiltonianl2].Furthermore, …     

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

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

一类拟二面体群的四度Cayley图的正规性

群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在AutX中正规.研究了4m阶拟二面体群G=a,b|a~(2m)=b~2=1,a~b=a~(m+1)的4度Cayley图的正规性,其中m=2~r,且r2,并得到拟二面体群的Cayley图的同构类型.     

Cayley color graphs of inverse semigroups and groupoids

The notion of Cayley color graphs of groups is generalized to inverse semigroups and groupoids. The set of partial automorphisms of the Cayley color graph of an inverse semigroup or a groupoid is isomorphic to the original inverse semigroup or groupoid. The groupoid of color permuting partial automorphisms of the Cayley color graph of a transitive groupoid is isomorphic to the original groupoid.     

Isomorphisms of finite semi-Cayley graphs

Let G be a finite group. A Cayley graph over G is a simple graph whose automorphism group has a regular subgroup isomorphic to G. A Cayley graph is called a CI-graph(Cayley isomorphism) if its isomorphic images are induced by automorphisms of G. A well-known result of Babai states that a Cayley graph Γ of G is a CI-graph if and only if all regular subgroups of Aut(Γ) isomorphic to G are conjugate in Aut(Γ). A semi-Cayley graph(also called bi-Cayley graph by some authors) over G is a simple graph whose automorphism group has a semiregular subgroup isomorphic to G with two orbits(of equal size). In this paper, we introduce the concept of SCI-graph(semi-Cayley isomorphism)and prove a Babai type theorem for semi-Cayley graphs. We prove that every semi-Cayley graph of a finite group G is an SCI-graph if and only if G is cyclic of order 3. Also, we study the isomorphism problem of a special class of semi-Cayley graphs.     

Roundness Properties of Groups

Roundness of metric spaces was introduced by Per Enflo as a tool to study uniform structures of linear topological spaces. The present paper investigates geometric and topological properties detected by the roundness of general metric spaces. In particular, we show that geodesic spaces of roundness 2 are contractible, and that a compact Riemannian manifold with roundness >1 must be simply connected. We then focus our investigation on Cayley graphs of finitely generated groups. One of our main results is that every Cayley graph of a free Abelian group on ⩾ 2 generators has roundness =1. We show that if a group has no Cayley graph of roundness =1, then it must be a torsion group with every element of order 2,3,5, or 7 Partially supported by a Canisius College Summer Research Grant     

关于4p阶3度Cayley图的正规性的一点注记

群G的Cayley图Cay(G,S)称为是正规的,如果G的右正则表示R(G)在Cay(G,S)的全自同构群中正规.设p为奇素数,相关文献决定了4p阶连通3度Cayley图的正规性.本文给出了上述文献的主要结果的一个新的简短的证明.     

Graphs obtained from Moufang loops and regular maps

Using ideas from regular maps, we prove the existence of infinitely many non‐vertex‐transitive Cayley graphs obtained from Moufang loops. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

关于交换群上的Cayley有向图的正规性

Cayley有向图X=Cay(G,S)叫做正规的,如果G的右正则表示R(G)在X的全自同构群Aut(X)中正规,我们定出了交换群上的小度数的非正规的Cayley有向图, 并给出了一个猜想．应用这个结果,给出了pn(n≤2)个点上的度数不超过3的有向对称图的分类,这里p是一个奇素数．