Back to search

University of Southampton

Some properties of transposition graphs

Abstract

dc:description.abstract

<p>For every finite graph G without isolated vertices, there is an associated set of transpositions Ω(G) which correspond in a natural way to the edges of G. G. Ω(G) generates a group H which is a symmetric group iff G is connected. The Cayley graph Γ(H,Ω) clearly depends only on G, and is called the transposition graph of G,.r(G).</p><p>The distance between any two vertices of a transposition graph Γ(G) is established in the cases where G is a complete graph, a complete graph with an edge deleted, a path graph, or a star. The diameter of Γ(G) is obtained as a corollary in these cases. General upper and lower bounds are found for the diameter of Γ(G) which depend on the number of vertices and the diameter of G.</p><p>If G has no connected components isomorphic to C<sub>4</sub> or K<sub>n</sub> then the automorphisms of Γ(G) are completely determined by the automorphisms of G. In particular, if G is a connected graph on n vertices with no non-trivial automorphisms, then Γ(G) is a graphical regular representation of S<sub>n</sub>. </p><p>Every transposition graph with at least four vertices is hamiltonian. </p><p>If the complement of the line graph of a graph G is hamiltonian then the genus of Γ(G) depends only on the number of vertices and edges of G. This result can be generalised if G has no circuits of length three. </p><p>Finally, it is proved that the Complement of the line graph of a graph G is hamiltonian if every vertex of G is incident to at most half the edges of 0 and every edge of G is non-incident to at least two other edges of G, provided G has at least thirty four edges.</p>

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
1982

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Prudden, Nicholas John
Advisor dc:contributor.advisor
  • Lloyd, E.K.

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Prudden, Nicholas John. Some properties of transposition graphs. doctoral thesis, University of Southampton, 1982.