Premium
Representing groups by graphs with constant link and hypergraphs
Author(s) -
Vogler Walter
Publication year - 1986
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190100406
Subject(s) - combinatorics , mathematics , link (geometry) , discrete mathematics , vertex (graph theory) , graph , induced subgraph
A graph L is called a link graph if there is a graph G such that for each vertex of G its neighbors induce a subgraph isomorphic to L. Such a G is said to have constant link L. We prove that for any finite group Γ and any disconnected link graph L with at least three vertices there are infinitely many connected graphs G with constant link L and Aut G ⋍ Γ. We look at the analogous problem for connected link graphs, namely, link graphs that are paths or have disconnected complements. Furthermore we prove that for n, r ≥ 2, but not n = 2 = r , any finite group can be represented by infinitely many connected r ‐uniform, n ‐regular hypergraphs of arbitrarily large girth.