✦ LIBER ✦

Forbidden triples for perfect matchings

✍ Scribed by Katsuhiro Ota; Michael D. Plummer;; Akira Saito

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 117 KB
Volume: 67
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20529

No coin nor oath required. For personal study only.

✦ Synopsis

Let H be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. Plummer and Saito [J Graph Theory 50 (2005), 1-12] and Fujita et al. [J Combin Theory Ser B 96 (2006), 315-324] characterized all H with |H| ≤ 2 such that every connected H-free graph of sufficiently large even order has a perfect matching. Extending this line of research, we give the characterization in the case of |H| ≤ 3.

📜 SIMILAR VOLUMES

Rook Theory for Perfect Matchings

✍ J. Haglund; J.B. Remmel 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 302 KB

In classical rook theory there is a fundamental relationship between the rook numbers and the hit numbers relative to any board. In that theory the k-th hit number of a board B can be interpreted as the number of permutations whose intersection with B is of size k. In the case of Ferrers boards ther

A compactness result for perfect matchin

A compactness result for perfect matchings

✍ Norbert Polat 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 537 KB

We show that an infinite set system (V, ~g), for which ~ is a subspace of the vector space of all finite subsets of V, has a perfect matching if and only if every finite subset of V is covered by a matching of (V, ~).

Forbidden (Perfect for them Book 1)

✍ Melissa Adams 📂 Fiction 📅 2020 🏛 Lost & Bound Publishing 🌐 English ⚖ 144 KB 👁 3 views

A first kiss at a party: that kiss haunts me to this day, no kiss after that has ever made me feel anything comparable. But It happened during a party game, the lights were turned off, so I have no idea who kissed me. That summer, I fell for two amazing boys: Chase and Reid. Everything fell a

Forbidden (Perfect for them Book 1)

✍ Adams, Melissa 📂 Fiction 📅 2020 🌐 English ⚖ 143 KB 👁 2 views

A Complementation Theorem for Perfect Ma

A Complementation Theorem for Perfect Matchings of Graphs Having a Cellular Completion

✍ Mihai Ciucu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 589 KB

A cellular graph is a graph whose edges can be partitioned into 4-cycles (called cells) so that each vertex is contained in at most two cells. We present a ``Complementation Theorem'' for the number of matchings of certain subgraphs of cellular graphs. This generalizes the main result of M. Ciucu (J

Heuristic enhancements of the search for

Heuristic enhancements of the search for the generation of all perfect matchings

✍ M.M. Balakrishnarajan; P. Venuvanalingam 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 313 KB

A search based algorithm has been introduced by us [1] to generate all perfect matchings on a graph. This paper presents a modified search that employs novel heuristics for rapid generation. This is done by an intelligent selection of edges for generating the branch nodes of the associated semantic