Connected [a, b]-factors in K1,n-free graphs containing an [a, b]-factor

被引：4

作者：

Tokuda, T ^{[1
]}

机构：

[1] Keio Univ, Fac Sci & Technol, Dept Math, Kohoku Ku, Yokohama, Kanagawa 223, Japan

来源：

DISCRETE MATHEMATICS | 1999年 / 207卷 / 1-3期

关键词：

graph; factor; connected factor; K-1; K-n-free;

D O I：

10.1016/S0012-365X(99)00113-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph G is called K-1,K-n-free if G has no induced subgraph isomorphic to K-1,K-n. Let n, a, and b be integers with n greater than or equal to 3, a greater than or equal to 1, and b greater than or equal to a(n - 2) + 2. We prove that every connected K-1,K-n-free graph G has a connected [a,b]-factor if G contains an [a,b]-factor. This result is sharp in the sense that there exists a connected K-l,K-n-free graph which has an [a,b]-factor but no connected [a,b]-factor for b less than or equal to a(n - 2) + 1. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：293 / 298

页数：6