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