Star subdivisions and connected even factors in the square of a graph

被引：11

作者：

Ekstein, Jan ^{[1
,2
]}

Holub, Premysl ^{[1
,2
]}

Kaiser, Tomas ^{[1
,2
]}

Xiong, Liming ^{[3
,4
,5
]}

Zhang, Shenggui ^{[6
]}

机构：

[1] Charles Univ Prague, Inst Theoret Comp Sci ITI, Plzen 30614, Czech Republic

[2] Univ W Bohemia, Dept Math, Plzen 30614, Czech Republic

[3] Beijing Inst Technol, Coll Math, Beijing 100081, Peoples R China

[4] Jiangxi Normal Univ, Dept Math, Nanchang, Peoples R China

[5] Qinghai Univ Nationalities, Dept Math, Hsiing, Peoples R China

[6] NW Polytech Univ, Dept Appl Math, Xian 710072, Shaanxi, Peoples R China

来源：

DISCRETE MATHEMATICS | 2012年 / 312卷 / 17期

关键词：

Square of a graph; Connected even factor; S(K1.2s+1); CYCLES;

D O I：

10.1016/j.disc.2011.09.004

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For any positive integer s, a [2. 2s]-factor in a graph G is a connected even factor with maximum degree at most 2s. We prove that if every induced S(K1.2s+1) in a graph G has at least three edges in a block of degree at most 2, then G(2) has a [2. 2s]-factor. This extends the results of Hendry and Vogler [5] and Abderrezzak etal. (1991)[1]. (C) 2012 Published by Elsevier B.V.

引用

页码：2574 / 2578

页数：5

共 6 条

[1] Induced S(K1,3) and hamiltonian cycles in the square of a graph [J].

Abderrezzak, ME ;

Flandrin, E ;

Ryjácek, Z .

DISCRETE MATHEMATICS, 1999, 207 (1-3) :263-269

[2]

Bondy J. A., 1976, Graduate Texts in Mathematics, V290

[3]

Fleischner H., 1974, Journal of Combinatorial Theory, Series B, V16, P29, DOI 10.1016/0095-8956(74)90091-4

[4] FORBIDDEN SUBGRAPHS AND HAMILTONIAN PROPERTIES IN THE SQUARE OF A CONNECTED GRAPH [J].

GOULD, RJ ;

JACOBSON, MS .

JOURNAL OF GRAPH THEORY, 1984, 8 (01) :147-154

[5] THE SQUARE OF A CONNECTED S(K1,3)-FREE GRAPH IS VERTEX PANCYCLIC [J].

HENDRY, G ;

VOGLER, W .

JOURNAL OF GRAPH THEORY, 1985, 9 (04) :535-537

[6] CHVATAL-ERDOS CONDITIONS FOR PATHS AND CYCLES IN GRAPHS AND DIGRAPHS - A SURVEY [J].

JACKSON, B ;

ORDAZ, O .

DISCRETE MATHEMATICS, 1990, 84 (03) :241-254

← 1 →