Contractibility techniques as a closure concept

被引:9
作者
Ryjácek, Z
Schelp, RH
机构
[1] Univ W Bohemia, Dept Math, Plzen 30614, Czech Republic
[2] Charles Univ, Inst Theoret Comp Sci, ITI, Plzen 30614, Czech Republic
[3] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA
关键词
closure; contractible graph; collapsible graph; line graph; claw-free graph; hamiltonian graph; circumference;
D O I
10.1002/jgt.10103
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We introduce a closure concept in the class of line graphs and claw-free graphs based on contractibility of certain subgraphs in the line graph preimage. The closure can be considered as a common generalization and strengthening of the reduction techniques of Catlin and Veldman and of the closure concept introduced by the first author. We show that the closure is uniquely determined and the closure operation preserves the circumference of the graph. (C) 2003 Wiley Periodicals, Inc.
引用
收藏
页码:37 / 48
页数:12
相关论文
共 7 条
[1]  
Beineke LW, 1970, J COMB THEORY, V9, P129, DOI 10.1016/S0021-9800(70)80019-9
[2]  
Bondy J.A., 2008, GRAD TEXTS MATH
[3]   Strengthening the closure concept in claw-free graphs [J].
Broersma, H ;
Ryjácek, Z .
DISCRETE MATHEMATICS, 2001, 233 (1-3) :55-63
[4]   A REDUCTION METHOD TO FIND SPANNING EULERIAN SUBGRAPHS [J].
CATLIN, PA .
JOURNAL OF GRAPH THEORY, 1988, 12 (01) :29-44
[5]  
Harary F., 1965, CANAD MATH B, V8, P701, DOI DOI 10.4153/CMB-1965-051-3
[6]   On a closure concept in claw-free graphs [J].
Ryjacek, Z .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 70 (02) :217-224
[7]   ON DOMINATING AND SPANNING CIRCUITS IN GRAPHS [J].
VELDMAN, HJ .
DISCRETE MATHEMATICS, 1994, 124 (1-3) :229-239