✦ LIBER ✦

A Note on Intertwines of Infinite Graphs

✍ Scribed by B. Oporowski

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 224 KB
Volume: 59
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1993.1054

No coin nor oath required. For personal study only.

✦ Synopsis

We present a construction of two infinite graphs (G_{1}, G_{2}) and of an infinite set of graphs such that (\mathscr{F}) is an antichain with respect to the minor relation and, for every graph (G) in (\mathscr{F}), both (G_{1}) and (G_{2}) are subgraphs of (G) but no graph obtained from (G) by deletion or contraction of an edge has both (G_{1}) and (G_{2}) as minors. These graphs show that the extension to infinite graphs of the intertwining conjecture of Lovász, Milgram, and Ungar fails. "/" 1993 Academic Press, Inc.

📜 SIMILAR VOLUMES

Note on Infinite Families of Trivalent S

Note on Infinite Families of Trivalent Semisymmetric Graphs

✍ Seymour Lipschutz; Ming-Yao Xu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 60 KB

A simple undirected graph is said to be semisymmetric if it is regular and edge-transitive but not vertex-transitive. This paper uses the groups PSL(2, p) and PGL(2, p), where p is a prime, to construct two new infinite families of trivalent semisymmetric graphs.

Note on the reconstruction of infinite g

Note on the reconstruction of infinite graphs with a fixed finite number of components

✍ Thomas Andreae 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB 👁 1 views

For every positive integer c , we construct a pair G, , H, of infinite, nonisomorphic graphs both having exactly c components such that G, and H, are hypomorphic, i.e., G, and H, have the same families of vertex-deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G

A note on conservative graphs

✍ Arthur T. White 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An application of conservative graphs to topological graph theory is indicated.

A note on coset graphs

✍ Ulrike Baumann 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Coset graphs are a generalization of Cayley graphs. They arise in the construction of graphs and digraphs with transitive automorphism groups. Moreover, the consideration of coset graphs makes it possible to give an algebraic description of regular connected graphs of even degree. In th

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

A note on graphs spanned by Eulerian gra

A note on graphs spanned by Eulerian graphs

✍ W. R. Pulleyblank 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 1 views

## Abstract We show that the problem raised by Boesch, Suffel, and Tindell of determining whether or not a graph is spanned by an Eulerian subgraph is NP‐complete. We also note that there does exist a good algorithm for determining if a graph is spanned by a subgraph having positive even degree at