Premium
Graphs with given group and given constant link
Author(s) -
Vogler Walter
Publication year - 1984
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.3190080113
Subject(s) - combinatorics , mathematics , vertex (graph theory) , induced subgraph , graph , discrete mathematics , vertex transitive graph , graph power , line graph
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 Sabidussi proved that for any finite group F and any n ⩾ 3 there are infinitely many n ‐regular connected graphs G with Aut G ≅ Γ. We will prove a stronger result: For any finite group Γ and any link graph L with at least one isolated vertex and at least three vertices there are infinitely many connected graphs G with constant link L and Aut G ≅ Γ.