✦ LIBER ✦

Matchable Infinite Graphs

✍ Scribed by F. Niedermeyer; K.P. Podewski

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 612 KB
Volume: 62
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1065

No coin nor oath required. For personal study only.

✦ Synopsis

We give a new proof of Aharoni's criterion for the existence of perfect matchings in infinite graphs. 1994 Academic Press, Jnc.

📜 SIMILAR VOLUMES

Randomly matchable graphs

✍ David P. Summer 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB

## Abstract A graph is defined to be randomly matchable if every matching of __G__ can be extended to a perfect matching. It is shown that the connected randomly matchable graphs are precisely __K__~2__n__~ and __K~n,n~__ (__n__ ≥ 1).

Infinite generalized friendship graphs

✍ Charles Delorme; Geňa Hahn 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 312 KB

We give necessary and sufficient conditions for the existence of infinite generalized friendship graphs and show that there are 2 c non-isomorphic ones of each admissible order c and chromatic number. Further we prove that such graphs and their complements are almost always regular of degree equal t

Reconstruction of infinite graphs

✍ C.St.J.A. Nash-Williams 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 929 KB

The paper recalls several known results concerning reconstruction and edge-reconstruction of infinite graphs, and draws attention to some possibly interesting unsolved problems.

Infinite median graphs, (0, 2)-graphs, a

Infinite median graphs, (0, 2)-graphs, and hypercubes

✍ Hans-J. Bandelt; Henry Martyn Mulder 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 450 KB

Hypercubes are characterized among connected bipartite graphs by interval conditions in several ways. These results are based on the following two facts: (i) connected bipartite graphs are median provided that all their intervals induce median graphs, and (ii) median (0, 2)graphs are hypercubes. No

Invariant Hamming graphs in infinite qua

Invariant Hamming graphs in infinite quasi-median graphs

✍ Marc Chastand; Norbert Polat 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 593 KB

It is shown that a quasi-median graph G without isometric infinite paths contains a Hamming graph (i.e., a cartesian product of complete graphs) which is invariant under any automorphism of G, and moreover if G has no infinite path, then any contraction of G into itself stabilizes a finite Hamming g

Miscellaneous problems on infinite graph

Miscellaneous problems on infinite graphs

✍ R. Halin 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 1 views