Premium
Connected‐Homomorphism‐Homogeneous Graphs
Author(s) -
Lockett Deborah C.
Publication year - 2015
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.21788
Subject(s) - mathematics , homomorphism , combinatorics , discrete mathematics , graph homomorphism , finite graph , graph isomorphism , cograph , isomorphism (crystallography) , homogeneous , graph , chordal graph , 1 planar graph , line graph , voltage graph , chemistry , crystal structure , crystallography
Abstract A relational structure is (connected‐) homogeneous if every isomorphism between finite (connected) substructures extends to an automorphism of the structure. We investigate notions that generalise (connected‐) homogeneity, where ‘isomorphism’ may be replaced by ‘homomorphism’ or ‘monomorphism’ in the definition. In particular, we study the classes of finite connected‐homomorphism‐homogeneous graphs, with the aim of producing classifications. The main result is a classification of the finite C - HHgraphs, where a graph G is C - HHif every homomorphism from a finite connected induced subgraph of G into G extends to an endomorphism of G . The finite C - II(connected‐homogeneous) graphs were classified by Gardiner in 1976, and from this we obtain classifications of the finite C - HIand C - MIfinite graphs. Although not all the classes of finite connected‐homomorphism‐homogeneous graphs are completely characterised, we may still obtain the final hierarchy picture for these classes.