Connected-homomorphism-homogeneous graphs

DOI10.1002/JGT.21788zbMATH Open1306.05130OpenAlexW1768992667MaRDI QIDQ2940985FDOQ2940985

Authors Deborah C. Lockett 

Publication date 21 January 2015

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.4373

zbMATH Keywords

finite graphshomomorphismshomogeneous structures

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Connectivity (05C40)

Abstract: A relational structure is (connected-)homogeneous if every isomorphism between finite (connected) substructures extends to an automorphism of the structure. We investigate notions which generalise (connected-)homogeneity, where "isomorphism" may be replaced by "homomorphism" or "monomorphism" in the definition. Specifically, 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-HH graphs, where a graph G is C-HH if 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-HI and C-MI finite 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.

Recommendations

• Homomorphism-Homogeneous Relational Structures
• Characterization of the finite C-MH-homogeneous graphs
• Towards finite homomorphism-homogeneous relational structures
• Homomorphism-homogeneous \(L\)-colored graphs
• Towards the characterization of finite homomorphism-homogeneous oriented graphs with loops

Cites work

• Combinatorially homogeneous graphs
• Countable Homogeneous Tournaments
• Countable Ultrahomogeneous Undirected Graphs
• Countable connected-homogeneous graphs
• Countable homogeneous partially ordered sets
• Finite irreflexive homomorphism-homogeneous binary relational systems
• Homogeneity conditions in graphs
• Homogeneous graphs
• Homomorphism-Homogeneous Relational Structures
• Homomorphism-homogeneous graphs
• Homomorphism-homogeneous partially ordered sets
• Infinite distance transitive graphs of finite valency
• Locally-finite connected-homogeneous digraphs
• On finite reflexive homomorphism-homogeneous binary relational systems
• Posets, homomorphisms and homogeneity
• Remarks on homomorphism-homogeneous lattices and semilattices
• The classification of connected-homogeneous digraphs with more than one end

Cited in

(16)

• Homomorphism-homogeneity classes of countable \(L\)-colored graphs
• Countable homogeneous multipartite graphs
• Characterization of the finite C-MH-homogeneous graphs
• scientific article; zbMATH DE number 5308096 (Why is no real title available?)
• Homomorphism-Homogeneous Relational Structures
• scientific article; zbMATH DE number 3851988 (Why is no real title available?)
• Countable connected-homogeneous graphs
• scientific article; zbMATH DE number 887760 (Why is no real title available?)
• On finite reflexive homomorphism-homogeneous binary relational systems
• Constant-to-one and onto global maps of homomorphisms between strongly connected graphs
• Some more notions of homomorphism-homogeneity
• Homomorphism-homogeneous graphs with loops
• On \(k\)-connected-homogeneous graphs
• On \(K_*\)-ultrahomogeneous graphs.
• Homomorphism-homogeneous graphs
• Towards the characterization of finite homomorphism-homogeneous oriented graphs with loops

This page was built for publication: Connected-homomorphism-homogeneous graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2940985)