Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-04T21:56:28.084Z Has data issue: false hasContentIssue false

Completely rigid graphs

Published online by Cambridge University Press:  09 April 2009

J. S. V. Symons
Affiliation:
Department of MathematicsUniversity of Western AustraliaNedlands, 6009
Rights & Permissions [Opens in a new window]

Extract

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.

In general, a structure is called rigid if it admits only the trivial structure preserving transformations. Of course, what is trivial depends on the context. In [7] the authors understand by a rigid graph one which has the property that the only edge preserving transformation of the vertices is the identity map. In other contexts, however, it is convenient to regard the constant maps as trivial also. (See [2] where a topological space is given which admits as continuous transformations only the identity and the constants.) The purpose of this note is to construct graphs rigid in the later sense; we call them completely rigid.

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1974

References

[1]Frucht, R., ‘Herstellung von Graphen mit vorgegebener abstrakter Gruppe’, Compos. Math. 6 (1938), 239250.Google Scholar
[2]De Groot, J., ‘Groups represented by homeomorphism groups, I'’, Math. Annalen 138 (1959), 80102.CrossRefGoogle Scholar
[3]Hedrlin, Z. and Pultr, A., ‘Symmetric Relations (Undirected Graphs) with Given Semigroups’, Monatsh. Math. 69, (1965), 318322.CrossRefGoogle Scholar
[4]Ore, O., Theory of Graphs, (Rhode Island, 1962.)CrossRefGoogle Scholar
[5]Pultr, A. and Hedrlin, Z., ‘Relations (Graphs) with Given Infinite Semigroups’, Monatsh. Math. 68 (1964), 421425.CrossRefGoogle Scholar
[6]Sierpinski, W., Cardinal and Ordinal Numbers, (Warszawa, 1958.)Google Scholar
[7]Vopenka, P., Pultr, A., and Hedrlin, Z., ‘A Rigid Relation Exists on Any Set’, Comment. Math. Univ. Carolinae 6 (1965), 149155.Google Scholar