Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-28T06:57:17.524Z Has data issue: false hasContentIssue false
  • English
  • Français

Partial automorphisms and the reconstruction conjecture

Part of: Graph theory

Published online by Cambridge University Press:  09 April 2009

W. L. Kocay
W. L. Kocay
Affiliation:
Department of Mathematics The University of ManitobaWinnipeg, Manitoba, Canada
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.

Let Γ be a graph with isomorphic subgraphs G and H, and let θ: G → H be an isomorphism. If θ can be extended to an automorphism of Γ, we call θ a partial automorphism of Γ.

We consider the application of partial automorphisms to the graph reconstruction conjecture, in particular, to the problem of reconstructing graphs with two vertices of degree k – 1 and the remaining vertices of degree k.

MSC classification

Secondary: 05C60: Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 37 , Issue 3 , December 1984 , pp. 317 - 336
Copyright
Copyright © Australian Mathematical Society 1984

References

[1]Bondy, J. A. and Hemminger, R. L., ‘Graph reconstruction-a survey’, J. Graph Theory 1 (1977), 227–268.CrossRefGoogle Scholar
[2]Kocay, W. L., ‘Some new methods in reconstruction theory’, Proceedings of the Ninth Australian Combinatorial Conference, (Springer-Verlag), to appear.Google Scholar
[3]Kocay, W. L., ‘Partial automorphisms and the reconstruction of bi-degreed graphs’, Congr. Numer., to appear.Google Scholar