×

Representing groups by graphs with constant link and hypergraphs. (English) Zbl 0632.05034

Frucht, Sabidussi, Izbicki, and others, have developed techniques to construct graphs with given automorphism group and various graph- theoretic properties, such as regularity, high girth or connectivity, etc. The author generalizes these results in two different ways: Firstly, he constructs regular uniform hypergraphs with high girth and given automorphism groups. (Uniform hypergraphs with given automorphism group - or even endomorphism monoid - have been constructed previously by the reviewer and J. Nešetřil [Can. Math. Bull. 13, 375-381 (1970)].) Secondly, he constructs connected graphs with given automorphism group and given disconnected neighborhood. (In other words, the constructed graph, in addition to having the prescribed automorphism group, has each vertex not only having the same number of neighbors, but actually having those neighbors induce the same given graph L; it is assumed that L is disconnected and has at least three vertices.) In both cases the methods depend on two new consruction techniques which modify a given graph, changing its girth, degrees and neighborhoods, but (under mild restrictions) not changing its automorphism group. In addition, results of Izbicki and Sabidussi are used for the first theorem, and those of Brown and Connelly for the second.
The author also explores similar questions for graphs with given neighborhood L which is connected. It is easy to see that such a result cannot hold in general, for if L is a complete graph then there is a unique graph in which each neighborhood is L. Partial results given here concern paths, and graphs L with disconnected complement. Other results which relate automorphism groups and graphs with given neighborhoods may be found in a paper by the reviewer, H. Levinson and M. E. Watkins [Combinatorics and computing, Proc. 2nd Caribb. Conf., Cave Hill/Barbados 1977, 115-122 (1977)].
Reviewer: P.Hell

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C65 Hypergraphs
05C38 Paths and cycles
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blass, J. Combinatorial Theory B 29 pp 277– (1980)
[2] and , On graphs with constant link I. In New Directions in the Theory of Graphs. Ed. Academic, New York (1973) 19–51.
[3] Brown, Discrete Math. 11 pp 199– (1975)
[4] Frucht, Compositio Math. 6 pp 239– (1938)
[5] Frucht, Canad. J. Math. 1 pp 365– (1949) · Zbl 0034.25802 · doi:10.4153/CJM-1949-033-6
[6] Hall, J. Graph Theory 4 pp 173– (1980)
[7] Hall, J. Graph Theory 9 pp 479– (1985)
[8] Graphs with given neighbourhoods I. Proc. Colloque Internationale CNRS (Orsay 1976). CNRS, Paris (1978) 219–223.
[9] Izbicki, Monatsh. Math. 61 pp 42– (1957)
[10] Izbicki, Monatsh. Math. 64 pp 15– (1960)
[11] Sabidussi, Canad. J. Math. 9 pp 515– (1957) · Zbl 0079.39202 · doi:10.4153/CJM-1957-060-7
[12] Sabidussi, Duke Math. J. 26 pp 693– (1959)
[13] Sabidussi, Math. Z. 72 pp 446– (1960)
[14] Vince, J. Graph Theory 5 pp 417– (1981)
[15] Vogler, J. Graph Theory 8 pp 111– (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.