Connected-homomorphism-homogeneous graphs

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

Authors: Deborah C. Lockett 

Publication date: 21 January 2015

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

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.

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

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

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)

Cites Work

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

Cited In (12)

• Countable homogeneous multipartite graphs
• On \(K_*\)-ultrahomogeneous graphs.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Characterization of the finite C-MH-homogeneous graphs
• Constant-to-one and onto global maps of homomorphisms between strongly connected graphs
• Homomorphism-homogeneous graphs with loops
• Title not available (Why is that?)
• Homomorphism-homogeneous graphs
• Homomorphism-Homogeneous Relational Structures
• Countable connected-homogeneous graphs
• On \(k\)-connected-homogeneous graphs

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)