On edge contractible graphs

被引：0

作者：

Lin, Hong ^{[1
]}

Yu, Lin ^{[1
]}

机构：

[1] Jimei Univ, Sch Sci, Xiamen 361021, Peoples R China

来源：

ARS COMBINATORIA | 2017年 / 134卷

关键词：

perfect matching; edge contractible graphs; n-extendable graphs;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a connected graph with a perfect matching on 2n vertices (n >= 2). A graph H is a contraction of G if it can be obtained from G by a sequence of edge contractions. Then G is said to be edge contractible if for any contraction G' of G with vertical bar V(G')vertical bar is even, G' has a perfect matching. In this note, we obtain a sufficient and necessary condition for a graph to be an edge contractible graph.

引用

页码：75 / 79

页数：5

共 8 条

[1]

[Anonymous], 1996, Discuss. Math. Graph Theory

[2]

[Anonymous], 1993, Australas. J. Combin.

[3] Extendability and factor-criticality [J].

Favaron, O .

DISCRETE MATHEMATICS, 2000, 213 (1-3) :115-122

[4]

Favaron O., 1998, Australas. J. Combin, V17, P89

[5]

Lovgsz L., 1986, MATCHING THEORY

[6]

Plummer M.D., 1996, SURV GRAPH THEOR SAN, V116, P3

[7] ON N-EXTENDABLE GRAPHS [J].

PLUMMER, MD .

DISCRETE MATHEMATICS, 1980, 31 (02) :201-210

[8] EXTENDING MATCHINGS IN GRAPHS - A SURVEY [J].

PLUMMER, MD .

DISCRETE MATHEMATICS, 1994, 127 (1-3) :277-292

← 1 →