Non-Cayley Vertex-Transitive Graphs of Order Twice the Product of Two Odd Primes

For a positive integer n, does there exist a vertex-transitive graph Γ on n vertices which is not a Cayley graph, or, equivalently, a graph Γ on n vertices such that Aut Γ is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2pq, where 2 < q < p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2pq vertices which are not Cayley graphs in the case where p ≡ 1 (mod q). Further, if p ? 1 (mod q), p ≡ q ≡ 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2pq = 66, or every vertex-transitive graph of order 2pq admitting a transitive imprimitive group of automorphisms is a Cayley graph.     

1/2-Transitive Graphs of Order 3p

A graph X is called vertex-transitive, edge-transitive, or arc-transitive, if the automorphism group of X acts transitively on the set of vertices, edges, or arcs of X, respectively. X is said to be 1/2-transitive, if it is vertex-transitive, edge-transitive, but not arc-transitive.In this paper we determine all 1/2-transitive graphs with 3p vertices, where p is an odd prime. (See Theorem 3.4.)     

GI-graphs: a new class of graphs with many symmetries

The class of generalized Petersen graphs was introduced by Coxeter in the 1950s. Frucht, Graver and Watkins determined the automorphism groups of generalized Petersen graphs in 1971, and much later, Nedela and ?koviera and (independently) Lovre?i?-Sara?in characterised those which are Cayley graphs. In this paper we extend the class of generalized Petersen graphs to a class of GI-graphs. For any positive integer n and any sequence j ₀,j ₁,…,j _t?1 of integers mod n, the GI-graph GI(n;j ₀,j ₁,…,j _t?1) is a (t+1)-valent graph on the vertex set \(\mathbb{Z}_{t} \times\mathbb{Z}_{n}\) , with edges of two kinds:

• an edge from (s,v) to (s′,v), for all distinct \(s,s' \in \mathbb{Z}_{t}\) and all \(v \in\mathbb{Z}_{n}\) ,
• edges from (s,v) to (s,v+j _s ) and (s,v?j _s ), for all \(s \in\mathbb{Z}_{t}\) and \(v \in\mathbb{Z}_{n}\) .

By classifying different kinds of automorphisms, we describe the automorphism group of each GI-graph, and determine which GI-graphs are vertex-transitive and which are Cayley graphs. A GI-graph can be edge-transitive only when t≤3, or equivalently, for valence at most 4. We present a unit-distance drawing of a remarkable GI(7;1,2,3).     

On the average genus of the random graph

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex-set {u_j; i ? Z_n} ∪ {v_j; i ? Z_n}, and edge-set {u_iu_i, u_iv_i, v_iv_{i+k, i?}Z_n}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k² ? 1 (mod n); and (ii) GP(n, k) is a vertex-transitive graph that is not a Cayley graph if and only if k² ? -1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1-skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n-dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211-218]. © 1995 John Wiley & Sons, Inc.     

Arc transitive covering digraphs and their eigenvalues

We prove that every finite regular digraph has an arc-transitive covering digraph (whose arcs are equivalent under automorphisms) and every finite regular graph has a 2-arc-transitive covering graph. As a corollary, we sharpen C. D. Godsil's results on eigenvalues and minimum polynomials of vertex-transitive graphs and digraphs. Using Godsil's results, we prove, that given an integral matrix A there exists an arc-transitive digraph X such that the minimum polynomial of A divides that of X. It follows that there exist arc-transitive digraphs with nondiagonalizable adjacency matrices, answering a problem by P. J. Cameron. For symmetric matrices A, we construct a 2-arc-transitive graphs X.     

Realizing finite edge‐transitive orientable maps

J.E. Graver and M.E. Watkins, Memoirs Am. Math. Soc. 126 (601) ( 5 ) established that the automorphism group of an edge‐transitive, locally finite map manifests one of exactly 14 algebraically consistent combinations (called types) of the kinds of stabilizers of its edges, its vertices, its faces, and its Petrie walks. Exactly eight of these types are realized by infinite, locally finite maps in the plane. H.S.M. Coxeter (Regular Polytopes, 2nd ed., McMillan, New York, 1963) had previously observed that the nine finite edge‐transitive planar maps realize three of the eight planar types. In the present work, we show that for each of the 14 types and each integer n ≥ 11 such that n ≡ 3,11 (mod 12), there exist finite, orientable, edge‐transitive maps whose various stabilizers conform to the given type and whose automorphism groups are (abstractly) isomorphic to the symmetric group Sym(n). Exactly seven of these types (not a subset of the planar eight) are shown to admit infinite families of finite, edge‐transitive maps on the torus, and their automorphism groups are determined explicitly. Thus all finite, edge‐transitive toroidal maps are classified according to this schema. Finally, it is shown that exactly one of the 14 types can be realized as an abelian group of an edge‐transitive map, namely, as ?_n × ?₂ where n ≡ 2 (mod 4). © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 1–34, 2001     

Arc-transitive distance-regular covers of cliques with <Emphasis Type="Italic">λ</Emphasis> = µ

We study antipodal distance-regular graphs of diameter 3 such that their automorphism group acts transitively on the set of pairs (a, b), where {a, b} is an edge of the graph. Since the automorphism group of such graphs acts 2-transitively on the set of antipodal classes, the classification of 2-transitive permutation groups can be used. We classify arc-transitive distance-regular graphs of diameter 3 in which any two vertices at distance at most two have exactly µ common neighbors.     

Strongly regular locally <Emphasis Type="Italic">GQ</Emphasis>(4,<Emphasis Type="Italic">t</Emphasis>)-graphs

Amply regular with parameters (v, k, λ, μ) we call an undirected graph with v vertices in which the degrees of all vertices are equal to k, every edge belongs to λ triangles, and the intersection of the neighborhoods of every pair of vertices at distance 2 contains exactly μ vertices. An amply regular diameter 2 graph is called strongly regular. We prove the nonexistence of amply regular locally GQ(4,t)-graphs with (t,μ) = (4, 10) and (8, 30). This reduces the classification problem for strongly regular locally GQ(4,t)-graphs to studying locally GQ(4, 6)-graphs with parameters (726, 125, 28, 20).     

On graphs with regular groups

A new method for the construction of graphs with given regular group is developed and used to show that to every nonabelian group G of order 3^k, k ≥ 4, there exists a graph X whose automorphism group is isomorphic to G and regular as a permutation group on the set of vertices of X.     

Hamiltonian cycles in generalized petersen graphs

Watkins (J. Combinatorial Theory 6 (1969), 152–164) introduced the concept of generalized Petersen graphs and conjectured that all but the original Petersen graph have a Tait coloring. Castagna and Prins (Pacific J. Math. 40 (1972), 53–58) showed that the conjecture was true and conjectured that generalized Petersen graphs G(n, k) are Hamiltonian unless isomorphic to G(n, 2) where n ≡ 5(mod 6). The purpose of this paper is to prove the conjecture of Castagna and Prins in the case of coprime numbers n and k.     

Locally arc-transitive graphs of valence {3,4} with trivial edge kernel

In this paper, we consider connected locally G-arc-transitive graphs with vertices of valence 3 and 4, such that the kernel $G_{uv}^{[1]}$ of the action of an edge-stabiliser on the neighbourhood Γ(u)∪Γ(v) is trivial. We find 19 finitely presented groups with the property that any such group G is a quotient of one of these groups. As an application, we enumerate all connected locally arc-transitive graphs of valence {3,4} on at most 350 vertices whose automorphism group contains a locally arc-transitive subgroup G with $G_{uv}^{[1]} = 1$ .     

F-Sets in graphs

A subset S of the vertex set of a graph G is called an F-set if every α?Γ(G), the automorphism group of G, is completely specified by specifying the images under α of all the points of S, and S has a minimum number of points. The number of points, k(G), in an F-set is an invariant of G, whose properties are studied in this paper. For a finite group Γ we define k(Γ) = max{k(G) | Γ(G) = Γ}. Graphs with a given Abelian group and given k-value (k ≤ k(Γ)) have been constructed. Graphs with a given group and k-value 1 are constructed which give simple proofs to the theorems of Frucht and Bouwer on the existence of graphs with given abstract/permutation groups.     

Graphs with three mutually pseudo-similar vertices

Vertices u and v of a graph X are pseudo-similar if X ? u ? X ? v but no automorphism of X maps u to v. We describe a group-theoretic method for constructing graphs with a set of three mutually pseudo-similar vertices. The method is used to construct several examples of such graphs. An algorithm for extending, in a natural way, certain graphs with three mutually pseudo-similar vertices to a graph in which the three vertices are similar is given. The algorithm suggests that no simple characterization of graphs with a set of three mutually pseudo-similar vertices can exist.     

On non-normal arc-transitive 4-valent dihedrants

Let X be a connected non-normal 4-valent arc-transitive Cayley graph on a dihedral group Dn such that X is bipartite, with the two bipartition sets being the two orbits of the cyclic subgroup within Dn. It is shown that X is isomorphic either to the lexicographic product Cn[2K1] with n 〉 4 even, or to one of the five sporadic graphs on 10, 14, 26, 28 and 30 vertices, respectively.     

On generalized Petersen graphs labeled with a condition at distance two

An L(2,1)-labeling of graph G is an integer labeling of the vertices in V(G) such that adjacent vertices receive labels which differ by at least two, and vertices which are distance two apart receive labels which differ by at least one. The λ-number of G is the minimum span taken over all L(2,1)-labelings of G. In this paper, we consider the λ-numbers of generalized Petersen graphs. By introducing the notion of a matched sum of graphs, we show that the λ-number of every generalized Petersen graph is bounded from above by 9. We then show that this bound can be improved to 8 for all generalized Petersen graphs with vertex order >12, and, with the exception of the Petersen graph itself, improved to 7 otherwise.     

On graphical regular representations of direct products of groups

A given group G may or may not have the property that there exists a graph X such that the automorphism group of X is regular, as a permutation group, and isomorphic to G. Mark E. Watkins has shown that the direct product of two finite groups has this property if each factor has this property and both factors are different from the cyclic group of order 2. Later, Wilfried Imrich generalized this result to infinite groups. In this paper, a new proof of this result for finite groups is given. The proof rests heavily on the result which states that if X is a graphical regular representation of the group G, then X is not self-complementary.     

Local automorphisms of standard operator algebras

Let X be an infinite-dimensional separable real or complex Banach space and A a closed standard operator algebra on X. Then every local automorphism of A is an automorphism. The assumptions of infinite-dimensionality, separability, and closeness are all indispensable.     

Examples of groups which have a graphical regular representation

A group G is said to have a graphical regular representation if there exists a simple graph X such that (i) G · Aut(X), the full automorphism group of X, and (ii) G is regular as a permutation group on the sea V(X) of the vertices of X. Many papers studying which groups have a graphical regular representation have been published. The purpose of this note is to add some examples of groups which have a graphical regular representation.     

On 3-Steiner simplicial orderings

Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering.