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, …     

6-regular Cayley graphs on abelian groups of odd order are hamiltonian decomposable

Alspach conjectured that any 2k-regular connected Cayley graph on a finite abelian group A has a hamiltonian decomposition. In this paper, the conjecture is shown true if k=3, and the order of A is odd.     

Hamiltonian circuits in Cayley graphs

The following result is proved: If either G is a finite abelian group or a semidirect product of a cyclic group of prime order by a finite abelian group of odd order, then every connected Cayley graph of G is hamiltonian.     

Graphs that admit square 1-factorizations are hamiltonian Cayley graphs

A square 1-factorization of a graph is a 1-factorization in which the union of any two distinct 1-factors is a disjoint union of 4-cycles. We show that a graph admits a square 1-factorization if and only if it is a Cayley graph with group (₂) ⁿ for somen. The rest of the title follows since Cayley graphs of abelian groups are known to be hamiltonian.     

Hamiltonian cycles in cayley color graphs

A group Γ is said to possess a hamiltonian generating set if there exists a minimal generating set Δ for Γ such that the Cayley color graph D_Δ(Γ) is hamiltonian. It is shown that every finite abelian group has a hamiltonian generating set. Certain classes of nonabelian groups are also investigated.     

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is n‐HC‐extendable if it contains a path of length n and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is weakly n‐HP‐extendable if it contains a path of length n and if every such path is contained in some Hamilton path of Γ. Moreover, Γ is strongly n‐HP‐extendable if it contains a path of length n and if for every such path P there is a Hamilton path of Γ starting with P. These concepts are then studied for the class of connected Cayley graphs on abelian groups. It is proved that every connected Cayley graph on an abelian group of order at least three is 2‐HC‐extendable and a complete classification of 3‐HC‐extendable connected Cayley graphs of abelian groups is obtained. Moreover, it is proved that every connected Cayley graph on an abelian group of order at least five is weakly 4‐HP‐extendable. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

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.     

On the extendability of certain semi-Cayley graphs of finite abelian groups

A connected graph Γ with at least 2n+2 vertices is said to be n-extendable if every matching of size n in Γ can be extended to a perfect matching. The aim of this paper is to study the 1-extendability and 2-extendability of certain semi-Cayley graphs of finite abelian groups, and the classification of connected 2-extendable semi-Cayley graphs of finite abelian groups is given. Thus the 1-extendability and 2-extendability of Cayley graphs of non-abelian groups which can be realized as such semi-Cayley graphs of abelian groups can be deduced. In particular, the 1-extendability and 2-extendability of connected Cayley graphs of generalized dicyclic groups and generalized dihedral groups are characterized.     

Elementary abelian <Emphasis Type="Italic">p</Emphasis>-groups of rank 2<Emphasis Type="Italic">p</Emphasis>+3 are not CI-groups

For every prime p>2 we exhibit a Cayley graph on \mathbbZ_p^2p+3\mathbb{Z}_{p}^{2p+3} which is not a CI-graph. This proves that an elementary abelian p-group of rank greater than or equal to 2p+3 is not a CI-group. The proof is elementary and uses only multivariate polynomials and basic tools of linear algebra. Moreover, we apply our technique to give a uniform explanation for the recent works of Muzychuk and Spiga concerning the problem.     

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     

Vertex-transitive graphs that are not Cayley graphs. II

The Petersen graph on 10 vertices is the smallest example of a vertex-transitive graph that is not a Cayley graph. In 1983, D. Marus˘ic˘ asked, “For what values of n does there exist such a graph on n vertices?” We give several new constructions of families of vertex-transitive graphs that are not Cayley graphs and complete the proof that, if n is divisible by p² for some prime p, then there is a vertex-transitive graph on n vertices that is not a Cayley graph unless n is p², p³, or 12. © 1996 John Wiley & Sons, Inc.     

A Family of Nonnormal Cayley Digraphs

We call a Cayley digraph Γ = Cay(G, S) normal for G if G _R , the right regular representation of G, is a normal subgroup of the full automorphism group Aut(Γ) of Γ. In this paper we determine the normality of Cayley digraphs of valency 2 on nonabelian groups of order 2p ² (p odd prime). As a result, a family of nonnormal Cayley digraphs is found. Received February 23, 1998, Revised September 25, 1998, Accepted October 27, 1998     

The Langlands classification for non-connectedp-adic groups

We give the Langlands classification for a non-connected reductive quasisplitp-adic groupG, under the assumption thatG/G ⁰ is abelian (here,G ⁰ denotes the connected component of the identity ofG). The Langlands classification for non-connected groups is an extension of the Langlands classification from the connected case.     

On s‐Hamiltonian Line Graphs

For an integer s ≥ 0, a graph G is s‐hamiltonian if for any vertex subset with |S^′| ≤ s, G ‐ S^′ is hamiltonian. It is well known that if a graph G is s‐hamiltonian, then G must be (s+2)‐connected. The converse is not true, as there exist arbitrarily highly connected nonhamiltonian graphs. But for line graphs, we prove that when s ≥ 5, a line graph is s‐hamiltonian if and only if it is (s+2)‐connected.     

Graphically abelian groups

We define a group G to be graphically abelian if the function g?g⁻¹ induces an automorphism of every Cayley graph of G. We give equivalent characterizations of graphically abelian groups, note features of the adjacency matrices for Cayley graphs of graphically abelian groups, and show that a non-abelian group G is graphically abelian if and only if G=E×Q, where E is an elementary abelian 2-group and Q is a quaternion group.     

On integral Cayley sum graphs

Let S be a subset of a finite abelian group G. The Cayley sum graph Cay⁺(G, S) of G with respect to S is a graph whose vertex set is G and two vertices g and h are joined by an edge if and only if g + h ∈ S. We call a finite abelian group G a Cayley sum integral group if for every subset S of G, Cay⁺(G, S) is integral i.e., all eigenvalues of its adjacency matrix are integers. In this paper, we prove that all Cayley sum integral groups are represented by Z₃ and Zn₂ ⁿ, n ≥ 1, where Z_k is the group of integers modulo k. Also, we classify simple connected cubic integral Cayley sum graphs.     

Weak Closure of Singular Abelian L p -Bundles in 3 Dimensions

We prove the closure for the sequential weak L ^p -topology of the class of vector fields on B ³ having integer flux through almost every sphere. We show how this problem is connected to the study of the minimization problem for the Yang–Mills functional in dimension higher than critical, in the abelian case.     

Hamiltonian groups are color-graph-hamiltonian

A group Γ is said to be color -graph -hamiltonian if Γ has a minimal generating set Δ such that the Cayley color graph D_Δ(Γ) is hamiltonian. It is shown that every hamiltonian group is color -graph -hamiltonian.     

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.