Cores and compactness of infinite directed graphs

DOI10.1006/JCTB.1996.0068MaRDI QIDQ1125952zbMATH OpenOpenAlexFDO

Authors Bruce L. Bauslaugh

Publication date 8 December 1996

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1996.0068

zbMATH Keywords

compactcoredigraphshomomorphic compactness

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (05C99)

Review text

We define the property of homomorphic compactness for digraphs. We prove that if a digraph \(H\) is homomorphically compact then \(H\) has a core, although the converse does not hold. We also examine a weakened compactness condition and show that when this condition is assumed, compactness is equivalent to containing a core. We use this result to prove that if a digraph \(H\) of size \(\kappa\) is not compact, then there is a digraph \(G\) of size at most \(\kappa^+\) such that \(H\) is not compact with respect to \(G\). We then give examples of some sufficient conditions for compactness.

Recommendations

• Compactness and finite equivalence of infinite digraphs
• List-compactness of infinite directed graphs
• The core of a graph

Cited in

(10)

• Compactness and finite equivalence of infinite digraphs
• Homomorphisms and amalgamation
• Core-like properties of infinite graphs and structures
• The quest for a characterization of hom-properties of finite character
• Graph cores via universal completability
• Preserving constraints with the stable chase
• On random digraphs and cores
• List-compactness of infinite directed graphs
• SHACL validation in the presence of ontologies: semantics and rewriting techniques
• Maximal digraphs with respect to primitive positive constructability

This page was built for publication: Cores and compactness of infinite directed graphs

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