Perfect Matchings: A Theory of Matching Covered Graphs

Cover
Springer Nature, 25.03.2024 - 580 Seiten

Beginning with its origins in the pioneering work of W.T. Tutte in 1947, this monograph systematically traces through some of the impressive developments in matching theory.

A graph is matchable if it has a perfect matching. A matching covered graph is a connected graph on at least two vertices in which each edge is covered by some perfect matching. The theory of matching covered graphs, though of relatively recent vintage, has an array of interesting results with elegant proofs, several surprising applications and challenging unsolved problems.

The aim of this book is to present the material in a well-organized manner with plenty of examples and illustrations so as to make it accessible to undergraduates, and also to unify the existing theory and point out new avenues to explore so as to make it attractive to graduate students.


 

Ausgewählte Seiten

Inhalt

Part I Basic Theory
2
Part II Brick and Brace Generation
274
Part III Pfaffian Orientations
414
Unsolved Problems
497
Appendix A Solutions to Selected Exercises
499
References
554
List of Figures
561
Glossary
569
Index
573
Urheberrecht

Andere Ausgaben - Alle anzeigen

Perfect Matchings: A Theory of Matching Covered Graphs
Cláudio L. Lucchesi,U.S.R. Murty
Keine Leseprobe verfügbar - 2025
Perfect Matchings: A Theory of Matching Covered Graphs
Cláudio L. Lucchesi,U.S.R. Murty
Keine Leseprobe verfügbar - 2024

Häufige Begriffe und Wortgruppen

2-connected 2-separation cut adjacent Adjust notation algorithm b-invariant edge B₁ barrier cut barrier of G bicritical bipartite graph bipartite matching covered brick G C-contractions of G class of G component of G conformal subgraph Corollary critical graph cubic graph cut of G deduce degree three denote digraph ear decomposition edge f edge of G Exercise follows G₁ graph G graph obtained H₁ Heawood graph hence incidence vectors induction integer Lemma Let G Lin(G Lovász M₁ matchable graph matching covered graph matching minor matching of G maximal barrier Möbius ladder multiple edges near-bipartite near-brick non-Pfaffian nontrivial barrier nontrivial tight cut odd component oddly oriented orientation of G perfect matching Petersen graph Pfaffian orientation planar graph polytope prove removable class removable doubleton removable edge removable in G separating cut shown in Figure solid brick subgraph of G subset Theorem thin edge tight cut decomposition tight in G

Autoren-Profil (2024)

Cláudio Leonardo Lucchesi graduated from the University of Sao Paulo in 1968 with a degree in Electrical Engineering. He then went to the University of Waterloo in Canada with the intention of doing a doctorate in Computer Science. But, attracted by a conjectured minimax relation, he switched to graph theory, worked under the guidance of Daniel H Younger, and obtained his PhD degree in 1976. Returning to Brazil, he taught for a number of years in the Department of Computer Science at the State University of Campinas. After retirement in 2001, and after a short tenure at the Federal University of Mato Grosso do Sul, he is now happily back at his alma mater.

U.S.R. Murty learned graph theory from Professor Claude Berge and finished his PhD at the Indian Statistical Institute under the supervision of the well-known statistician Dr. C.R. Rao. He has been at the University of Waterloo, Canada, since 1967. He co-authored two books on graph theory with J.A. Bondy (Graph Theorywith Applications, Macmillan, 1976; and Graph Theory, Springer, 2008.


Bibliografische Informationen

TitelPerfect Matchings: A Theory of Matching Covered Graphs
Algorithms and Computation in Mathematics
Mathematics and Statistics
Mathematics and Statistics (R0)
AutorenCláudio L. Lucchesi, U.S.R. Murty
VerlagSpringer Nature, 2024
ISBN3031475046, 9783031475047
Länge580 Seiten
  
Zitat exportierenBiBTeX EndNote RefMan