✦ LIBER ✦

Cores and Compactness of Infinite Directed Graphs

✍ Scribed by Bruce L. Bauslaugh

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 665 KB
Volume: 68
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.0068

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper 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 } is not compact, then there is a digraph G of size at most } + such that H is not compact with respect to G. We then give examples of some sufficient conditions for compactness.

📜 SIMILAR VOLUMES

Core-like properties of infinite graphs

Core-like properties of infinite graphs and structures

✍ B. Bauslaugh 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 554 KB

We define several properties of infinite graphs (structures) which are analogous to the property of being a core in a finite graph. We describe completely the relationships between these properties. We also show which of these properties are invariant under homomorphic equivalence.

Cores of class II graphs

✍ D. G. Hoffman 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 230 KB

## Abstract We find necessary and sufficient conditions for a graph __G__ to be the core of a graph containing an overfull subgraph of the same maximum degree. Thus we enlarge the list of graphs known to be cores of class II graphs. © 1995 John Wiley & Sons, Inc.

Realization of Matrices and Directed Gra

Realization of Matrices and Directed Graphs

✍ Rajeev Motwani 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 182 KB

We consider the problem of constructing a matrix with prescribed row and Ä 4 column sums, subject to the condition that the off-diagonal entries are in 0, 1 and the diagonal entries are nonnegative integers. The pair of row and column sum vectors is called realizable if such a matrix exists. This is

Divisors and the spectrum of infinite gr

Divisors and the spectrum of infinite graphs

✍ Bojan Mohar; Matjaž Omladič 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 530 KB

Directed Graphs and Combinatorial Proper

Directed Graphs and Combinatorial Properties of Semigroups

✍ A.V. Kelarev; S.J. Quinn 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 104 KB

On self-immersions of infinite graphs

✍ Thomas Andreae 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract The existence of an infinite graph which is not isomorphic to a proper minor of itself was proved by Oporowski. In the present note, it is shown that an analogous result holds when immersions are considered instead of minors. The question whether or not the same is true for weak immersi