Forbidden subgraphs and the existence of spanning k-trees

被引：1

作者：

Ota, Katsuhiro ^{[2
]}

Sugiyama, Takeshi ^{[1
]}

机构：

[1] Univ Tsukuba, Grad Sch Business Sci, Bunkyo Ku, Tokyo 1120012, Japan

[2] Keio Univ, Dept Math, Kohoku Ku, Yokohama, Kanagawa 2238522, Japan

来源：

DISCRETE MATHEMATICS | 2010年 / 310卷 / 24期

关键词：

Forbidden subgraph; k-tree;

D O I：

10.1016/j.disc.2010.08.015

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A k-tree of a graph is a subtree with maximum degree at most k. Though forbidden subgraphs are a major tool to find a hamiltonian cycle or a hamiltonian path, there are only a few results using the condition on forbidden subgraphs to find a spanning k-tree for k >= 3. In this paper, we give a sufficient condition using the condition on forbidden subgraphs for a graph G to have a spanning k-tree. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：3506 / 3511

页数：6