Forbidden subgraphs and the existence of spanning k-trees

Katsuhiro Ota; Takeshi Sugiyama

doi:10.1016/j.disc.2010.08.015

Forbidden subgraphs and the existence of spanning k-trees

Katsuhiro Ota, Takeshi Sugiyama

数理科学科

研究成果: Article › 査読

1 被引用数 (Scopus)

抄録

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.

本文言語	English
ページ（範囲）	3506-3511
ページ数	6
ジャーナル	Discrete Mathematics
巻	310
号	24
DOI	https://doi.org/10.1016/j.disc.2010.08.015
出版ステータス	Published - 2010 12月 28

ASJC Scopus subject areas

理論的コンピュータサイエンス
離散数学と組合せ数学

文献へのアクセス

10.1016/j.disc.2010.08.015

他のファイルとリンク

引用スタイル

@article{4c7f148028624ecebb10afcb123bdfe0,

title = "Forbidden subgraphs and the existence of spanning k-trees",

abstract = "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.",

keywords = "Forbidden subgraph, k-tree",

author = "Katsuhiro Ota and Takeshi Sugiyama",

year = "2010",

month = dec,

day = "28",

doi = "10.1016/j.disc.2010.08.015",

language = "English",

volume = "310",

pages = "3506--3511",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "24",

}

TY - JOUR

T1 - Forbidden subgraphs and the existence of spanning k-trees

AU - Ota, Katsuhiro

AU - Sugiyama, Takeshi

PY - 2010/12/28

Y1 - 2010/12/28

N2 - 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.

AB - 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.

KW - Forbidden subgraph

KW - k-tree

UR - http://www.scopus.com/inward/record.url?scp=77958016183&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77958016183&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2010.08.015

DO - 10.1016/j.disc.2010.08.015

M3 - Article

AN - SCOPUS:77958016183

SN - 0012-365X

VL - 310

SP - 3506

EP - 3511

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 24

ER -

Forbidden subgraphs and the existence of spanning k-trees

抄録

ASJC Scopus subject areas

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル