A forbidden pair for connected graphs to have spanning k-trees

Shun ichi Maezawa; Kenta Ozeki

doi:10.1002/jgt.22752

A forbidden pair for connected graphs to have spanning k-trees

Shun ichi Maezawa, Kenta Ozeki

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

For an integer (Formula presented.), a (Formula presented.) -tree is a tree with maximum degree at most (Formula presented.). A (Formula presented.) -tree containing all vertices of a graph (Formula presented.) is called a spanning (Formula presented.) -tree of (Formula presented.). In 2010, Ota and Sugiyama gave a forbidden induced subgraph condition for a graph to have a spanning (Formula presented.) -tree and they posed a conjecture that is stronger than their result. In this paper, we solve their conjecture.

Original language	English
Pages (from-to)	509-519
Number of pages	11
Journal	Journal of Graph Theory
Volume	99
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22752
Publication status	Published - Mar 2022

Access to Document

10.1002/jgt.22752

Cite this

@article{53ddb5623e8649bbbd14671011ad7194,

title = "A forbidden pair for connected graphs to have spanning k-trees",

abstract = "For an integer (Formula presented.), a (Formula presented.) -tree is a tree with maximum degree at most (Formula presented.). A (Formula presented.) -tree containing all vertices of a graph (Formula presented.) is called a spanning (Formula presented.) -tree of (Formula presented.). In 2010, Ota and Sugiyama gave a forbidden induced subgraph condition for a graph to have a spanning (Formula presented.) -tree and they posed a conjecture that is stronger than their result. In this paper, we solve their conjecture.",

author = "Maezawa, {Shun ichi} and Kenta Ozeki",

note = "Funding Information: The authors would like to thank the referees for their valuable comments and suggestions. The first author's work (S. Maezawa) was partially supported by JSPS KAKENHI Grant Number JP20J15332 and JSPS KAKENHI Grant Number JP20H05795. The second author's work (K. Ozeki) was partially supported by JSPS KAKENHI Grant Number 18K03391 and JSPS KAKENHI Grant Number JP20H05795. Publisher Copyright: {\textcopyright} 2021 Wiley Periodicals LLC",

year = "2022",

month = mar,

doi = "10.1002/jgt.22752",

language = "English",

volume = "99",

pages = "509--519",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - A forbidden pair for connected graphs to have spanning k-trees

AU - Maezawa, Shun ichi

AU - Ozeki, Kenta

N1 - Funding Information: The authors would like to thank the referees for their valuable comments and suggestions. The first author's work (S. Maezawa) was partially supported by JSPS KAKENHI Grant Number JP20J15332 and JSPS KAKENHI Grant Number JP20H05795. The second author's work (K. Ozeki) was partially supported by JSPS KAKENHI Grant Number 18K03391 and JSPS KAKENHI Grant Number JP20H05795. Publisher Copyright: © 2021 Wiley Periodicals LLC

PY - 2022/3

Y1 - 2022/3

N2 - For an integer (Formula presented.), a (Formula presented.) -tree is a tree with maximum degree at most (Formula presented.). A (Formula presented.) -tree containing all vertices of a graph (Formula presented.) is called a spanning (Formula presented.) -tree of (Formula presented.). In 2010, Ota and Sugiyama gave a forbidden induced subgraph condition for a graph to have a spanning (Formula presented.) -tree and they posed a conjecture that is stronger than their result. In this paper, we solve their conjecture.

AB - For an integer (Formula presented.), a (Formula presented.) -tree is a tree with maximum degree at most (Formula presented.). A (Formula presented.) -tree containing all vertices of a graph (Formula presented.) is called a spanning (Formula presented.) -tree of (Formula presented.). In 2010, Ota and Sugiyama gave a forbidden induced subgraph condition for a graph to have a spanning (Formula presented.) -tree and they posed a conjecture that is stronger than their result. In this paper, we solve their conjecture.

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

U2 - 10.1002/jgt.22752

DO - 10.1002/jgt.22752

M3 - Article

AN - SCOPUS:85116494214

VL - 99

SP - 509

EP - 519

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 3

ER -

A forbidden pair for connected graphs to have spanning k-trees

Abstract

Access to Document

Other files and links

Fingerprint

Cite this