A closure concept in factor-critical graphs

Tsuyoshi Nishimura

doi:10.1016/S0012-365X(02)00303-5

A closure concept in factor-critical graphs

Tsuyoshi Nishimura

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

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 ∈ N_G(u) ∩ N_G(v), and N_G(x) ⊂ N_G(u) ∪ N_G(v) ∪ {u,v}. Then G is n-factor-critical if and only if G + uv is n-factor-critical.

Original language	English
Pages (from-to)	319-324
Number of pages	6
Journal	Discrete Mathematics
Volume	259
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(02)00303-5
Publication status	Published - 2002 Dec 28

Keywords

1-Factors
Closures
Factor-critical graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(02)00303-5

Cite this

@article{4cd8b0deb0674926bfcb6869eb6c1f06,

title = "A closure concept in factor-critical graphs",

abstract = "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.",

keywords = "1-Factors, Closures, Factor-critical graphs",

author = "Tsuyoshi Nishimura",

year = "2002",

month = dec,

day = "28",

doi = "10.1016/S0012-365X(02)00303-5",

language = "English",

volume = "259",

pages = "319--324",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

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 -

A closure concept in factor-critical graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this