𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Structuring the elementary components of graphs having a perfect internal matching

✍ Scribed by Miklós Bartha; Miklós Krész

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
336 KB
Volume
299
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Graphs with perfect internal matchings are decomposed into elementary components, and these components are given a structure re ecting the order in which they can be reached by external alternating paths. It is shown that the set of elementary components can be grouped into pairwise disjoint families determined by the "two-way accessible" relationship among them. A family tree is established by which every family member, except the root, has a unique father and mother identiÿed as another elementary component and one of its canonical classes, from which the given member is two-way accessible. It is proved that every member of the family is only accessible through a distinguished canonical class of the root by external alternating paths. The families themselves are arranged in a partial order according to the order they can be covered by external alternating paths, and a complete characterization of the graph's forbidden and impervious edges is elaborated.

📜 SIMILAR VOLUMES

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

A note on the number of perfect matching
A note on the number of perfect matchings of bipartite graphs
✍ Zhang Fuji; Zhang Heping 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 484 KB

Let G be a bipartite graph with 2n vertices, A its adjacency matrix and K the number of perfect matchings. For plane bipartite graphs each interior face of which is surrounded by a circuit of length 4s + 2, s E { 1,2,. . .}, an elegant formula, i.e. det A = (-1 )nK2, had been rigorously proved by Cv