EUVIMEDEUVIMED entdecken
Crossref

A Generalization of an Ear Decomposition and k‐Trees in Highly Connected Star‐Free Graphs

Shun‐ichi Maezawa, Kenta Ozeki, Masaki Yamamoto, Takamasa Yashima

Journal of Graph Theory · 30.10.2026

DOI: 10.1002/jgt.70153 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 30.10.2026. Verfasst von Shun‐ichi Maezawa und 3 weiteren Autor:innen. Die Arbeit nennt 17 Literaturangaben. Gefördert von: Japan Society for the Promotion of Science.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper, we introduce a generalized version of an ear decomposition, called a ‐spider decomposition, for ‐connected star‐free graphs with . This application enables us to improve a previously known sufficient condition for the existence of a ‐tree in highly connected star‐free graphs, where a ‐tree is a spanning tree in which every vertex is of degree at most . More precisely, we show that every ‐connected ‐free graph has a ‐tree for , thereby improving a classical result of Jackson and Wormald for . Our approach differs from previous studies based on toughness‐type arguments and instead relies on both a ‐spider decomposition and a factor theorem related to Hall's marriage theorem.

Förderung

  • Japan Society for the Promotion of Science

Zitieren

APA

Maezawa, S., Ozeki, K., Yamamoto, M., & Yashima, T. (2026). A Generalization of an Ear Decomposition and k‐Trees in Highly Connected Star‐Free Graphs. Journal of Graph Theory. https://doi.org/10.1002/jgt.70153

Vancouver

Maezawa S, Ozeki K, Yamamoto M, Yashima T. A Generalization of an Ear Decomposition and k‐Trees in Highly Connected Star‐Free Graphs. Journal of Graph Theory. 2026. doi:10.1002/jgt.70153

BibTeX
@article{Maezawa2026,
  author = {Maezawa, Shun‐ichi and Ozeki, Kenta and Yamamoto, Masaki and Yashima, Takamasa},
  title = {A Generalization of an Ear Decomposition and k‐Trees in Highly Connected Star‐Free Graphs},
  journal = {Journal of Graph Theory},
  year = {2026},
  doi = {10.1002/jgt.70153}
}
Kostenlos starten →