TY - JOUR
T1 - A closure concept in factor-critical graphs
AU - Nishimura, Tsuyoshi
PY - 2002/12/28
Y1 - 2002/12/28
N2 - A graph G is called n-factor-critical if the removal of every set of n vertices results in a graph with a 1-factor. We prove the following theorem: Let G be a graph and let x be a locally n-connected vertex. Let {μ, v} be a pair of vertices in V(G) - {x} such that uv E(G), x ∈ NG(u) ∩ NG(v), and NG(x) ⊂ NG(u) ∪ NG(v) ∪ {u,v}. Then G is n-factor-critical if and only if G + uv is n-factor-critical.
AB - A graph G is called n-factor-critical if the removal of every set of n vertices results in a graph with a 1-factor. We prove the following theorem: Let G be a graph and let x be a locally n-connected vertex. Let {μ, v} be a pair of vertices in V(G) - {x} such that uv E(G), x ∈ NG(u) ∩ NG(v), and NG(x) ⊂ NG(u) ∪ NG(v) ∪ {u,v}. Then G is n-factor-critical if and only if G + uv is n-factor-critical.
KW - 1-Factors
KW - Closures
KW - Factor-critical graphs
UR - http://www.scopus.com/inward/record.url?scp=33845790755&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33845790755&partnerID=8YFLogxK
U2 - 10.1016/S0012-365X(02)00303-5
DO - 10.1016/S0012-365X(02)00303-5
M3 - Article
AN - SCOPUS:33845790755
SN - 0012-365X
VL - 259
SP - 319
EP - 324
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
ER -