Maximum induced matchings of random cubic graphs

DOI10.1016/S0377-0427(01)00457-5zbMath1001.05093OpenAlexW2088411760MaRDI QIDQ1612292

Nicholas C. Wormald, Michele Zito, William Duckworth

Publication date: 22 August 2002

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-0427(01)00457-5

zbMATH Keywords

random graphsmatchings

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Unnamed Item, Induced matchings in subcubic graphs without short cycles, Unnamed Item, Analysis of greedy algorithms on graphs with bounded degrees, Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem, Brambles and independent packings in chordal graphs, Independent packings in structured graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Irredundancy in circular arc graphs
• On induced matchings
• Induced matchings in bipartite graphs
• Problems and results in combinatorial analysis and graph theory
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Maximum induced matchings in graphs
• On the approximability of the maximum induced matching problem
• New results on induced matchings
• Minimum independent dominating sets of random cubic graphs