Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T20:56:18.676Z Has data issue: false hasContentIssue false

Regular graphs and stability

Published online by Cambridge University Press:  09 April 2009

D. A. Holton
Affiliation:
University of MelbourneParkville Victoria 3052, Australia.
Douglas D. Grant
Affiliation:
University of MelbourneParkville Victoria 3052, Australia.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that a graph G is semi-stable at vertex v if and only if the set of vertices of G adjacent to v is fixed by the automorphism group of Gv, the subgraph of G obtained by deleting v and its incident edges. This result leads to a neat proof that regular graphs are semi-stable at each vertex. We then investigate stable regular graphs, concentrating mainly on stable vertex-transitive graphs. We conjecture that if G is a non-trivial vertex-transitive graph, then G is stable if and only if γ(G) contains a transposition, offering some evidence for its truth.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1975