Hamiltonicity of tree-like graphs (Q914698): Difference between revisions

The conjecture of Lovász, that every connected, vertex transitive graph has a Hamiltonian path, has been verified for graphs of various special orders. For example, the author and \textit{T. D. Parsons} [ibid. 42, 227- 242 (1982; Zbl 0501.05041), and ibid. 43, 91-96 (1983; Zbl 0514.05037)] have shown the conjecture true for orders 5p and 4p. Further results have been catalogued by \textit{B. Alspach} [Lect. Notes Math. 884, 14-22 (1981; Zbl 0468.05046)]. The present author, generalizing some of the techniques he and Parsons introduced, considers galactic graphs whose factor graphs are trees. A graph G is called (m,p)-galactic iff there is an automorphism \(\alpha\) of G that has m orbits of cardinality p, p prime, and no others. The a-factor graph G/\(\alpha\) of G is a homomorphic image of G with the set of orbits of \(\alpha\) as its vertex set. A graph H is a factor graph of G iff it is isomorphic to G/\(\alpha\) for some such \(\alpha\).