Resolving The Hamiltonian Problem for Vertex-Transitive Graphs of Order a Product of Two Primes

A step forward is made in a long standing Lovász problem regarding existence of Hamilton paths in vertex-transitive graphs. It is shown that a vertex-transitive graph of order a product of two primes arising from a primitive action of PSL(2; p ) on the cosets of a subgroup isomorphic to D p −1 has a...

Full description

Saved in:
Bibliographic Details
Published in:Combinatorica (Budapest. 1981) 2021-08, Vol.41 (4), p.507-543
Main Authors: Du, Shaofei, Kutnar, Klavdija, Marušič, Dragan
Format: Article
Language:English
Subjects:
Combinatorics
Existence theorems
Fields (mathematics)
Graphical representations
Graphs
Manufacturers representatives
Mathematical analysis
Mathematics
Mathematics and Statistics
Matrix algebra
Order quantity
Original Paper
Polynomials
Subgroups
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A step forward is made in a long standing Lovász problem regarding existence of Hamilton paths in vertex-transitive graphs. It is shown that a vertex-transitive graph of order a product of two primes arising from a primitive action of PSL(2; p ) on the cosets of a subgroup isomorphic to D p −1 has a Hamilton cycle. Essential tools used in the proof range from classical results on existence of Hamilton cycles, such as Chvátal's theorem and Jackson's theorem, to certain results from matrix algebra, graph quotienting, and polynomial representations of quadratic residues in terms of primitive roots in finite fields. Also, Hamilton cycles are proved to exist in vertex-transitive graphs of order a product of two primes arising from a primitive action of either PΩ (2 d ; 2), M 22 , A 7 , PSL(2; 13), or PSL(2; 61). The results of this paper, combined together with other known results, imply that all connected vertex-transitive graphs of order a product of two primes, except for the Petersen graph, have a Hamilton cycle.
ISSN:0209-9683
1439-6912
DOI:10.1007/s00493-020-4384-6