Premium
Matching cutsets in graphs
Author(s) -
Moshi Augustine M.
Publication year - 1989
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.3190130502
Subject(s) - combinatorics , mathematics , matching (statistics) , undirected graph , graph , degree (music) , chordal graph , indifference graph , discrete mathematics , statistics , physics , acoustics
Let G = ( V,E ) be an undirected graph. A subset F of E is a matching cutset of G if no two edges of F are incident with the same point, and G‐F has more components than G . Chv́atal [2] proved that it is NP‐complete to recognize graphs with a matching cutset even if the input is restricted to graphs with maximum degree 4. We prove the following: (a) Every connected graph with maximum degree ⩽3 and on more than 7 points has a matching cutset. (In particular, there are precisely two connected cubic graphs without a matching cutset). (b) Line graphs with a matching cutset can be recognized in O (| E |) time. (c) Graphs without a chordless circuit of length 5 or more that have a matching cutset can be recognized in O (| V || E | 3 ) time.