Maximal Induced Matchings in Triangle‐Free Graphs | Zendy

Basavaraju Manu | Zendy; Heggernes Pinar | Zendy; van ′t Hof Pim | Zendy; Saei Reza | Zendy; Villanger Yngve | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Maximal Induced Matchings in Triangle‐Free Graphs

Author(s) -

Basavaraju Manu,

Heggernes Pinar,

van ′t Hof Pim,

Saei Reza,

Villanger Yngve

Publication year - 2016

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.21994

Subject(s) - combinatorics , mathematics , factor critical graph , bipartite graph , induced subgraph , distance hereditary graph , vertex (graph theory) , discrete mathematics , disjoint sets , complete bipartite graph , matching (statistics) , line graph , graph , graph power , statistics

An induced matching in a graph is a set of edges whose endpoints induce a 1‐regular subgraph. It is known that every n ‐vertex graph has at most 10 n / 5 ≈ 1 . 5849 nmaximal induced matchings, and this bound is the best possible. We prove that every n ‐vertex triangle‐free graph has at most 3 n / 3 ≈ 1 . 4423 nmaximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K 3, 3 . Our result implies that all maximal induced matchings in an n ‐vertex triangle‐free graph can be listed in time O ( 1 . 4423 n ) , yielding the fastest known algorithm for finding a maximum induced matching in a triangle‐free graph.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research