Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-08T07:23:23.895Z Has data issue: false hasContentIssue false
  • English
  • Français

Regular graphs and stability

Published online by Cambridge University Press:  09 April 2009

D. A. Holton  and
Douglas D. Grant
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.

Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 20 , Issue 3 , November 1975 , pp. 377 - 384
Copyright
Copyright © Australian Mathematical Society 1975

References

Chartrand, M. (1971), Introduction to the Theory of Graphs (Allyn and Bacon (Boston), 1971).Google Scholar
Harary, F. (1969), Graph Theory (Addison Wesley Reading, Mass. 1969).CrossRefGoogle Scholar
Holton, D. A. (1973), ‘A Report on Stable Graphs’, J. Austral. Math. Soc. 15, 163–171.CrossRefGoogle Scholar
Holton, D. A. (1973a), ‘Two Applications of Semi-stable Graphs’, Discrete Math. 4, 151–158.CrossRefGoogle Scholar
Holton, D. A. (1973b), ‘Stable Trees’, J. Austral. Math. Soc. 15, 476–481.CrossRefGoogle Scholar
Grant, D. D. (to appear), ‘Stability and Operations on Graphs’, Proc. Third Australian Conference on Combinatorial Mathematics.Google Scholar
McAvaney, K. L., Grant, D. D. and Holton, D. A. (1974), ‘Stable and Semi-stable Unicyclic Graphs, Discrete Math. 9, 277–288.CrossRefGoogle Scholar
Sheehan, J., (1972), ‘Fixing Subgraphs’, J. Comb. Th 12A, 226–243.CrossRefGoogle Scholar
Wielandt, H. (1964), Finite Permutation Groups (Academic Press, New York, 1964).Google Scholar