Premium
The connectivity of minimal imperfect graphs
Author(s) -
Sebö András
Publication year - 1996
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/(sici)1097-0118(199609)23:1<77::aid-jgt9>3.0.co;2-h
Subject(s) - mathematics , cardinality (data modeling) , combinatorics , simple (philosophy) , imperfect , algebraic number , discrete mathematics , upper and lower bounds , computer science , mathematical analysis , philosophy , linguistics , epistemology , data mining
We prove that partitionable graphs are 2o − 2‐connected, that this bound is sharp, and prove some structural properties of cutsets of cardinality 2o − 2. The proof of the connectivity result is a simple linear algebraic proof. © 1996 John Wiley & Sons, Inc.