Advanced search
1 file | 390.67 KB Add to list

On minimum leaf spanning trees and a criticality notion

(2020) Discrete Mathematics. 343(7). p.1-8
Author
Organization
Abstract
The minimum leaf number of a connected non-hamiltonian graph G is the number of leaves of a spanning tree of G with the fewest leaves among all spanning trees of G. Based on this quantity, Wiener introduced leaf-stable and leaf-critical graphs, concepts which generalise hypotraceability and hypohamiltonicity. In this article, we present new methods to construct leaf-stable and leaf-critical graphs and study their properties. Furthermore, we improve several bounds related to these families of graphs. These extend previous results of Horton, Thomassen, and Wiener.
Keywords
Theoretical Computer Science, Discrete Mathematics and Combinatorics

Downloads

  • 1-s2.0-S0012365X20300765-main.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 390.67 KB

Citation

Please use this url to cite or link to this publication:

MLA
Ozeki, Kenta, et al. “On Minimum Leaf Spanning Trees and a Criticality Notion.” Discrete Mathematics, vol. 343, no. 7, 2020, pp. 1–8.
APA
Ozeki, K., Wiener, G., & Zamfirescu, C. (2020). On minimum leaf spanning trees and a criticality notion. Discrete Mathematics, 343(7), 1–8.
Chicago author-date
Ozeki, Kenta, Gábor Wiener, and Carol Zamfirescu. 2020. “On Minimum Leaf Spanning Trees and a Criticality Notion.” Discrete Mathematics 343 (7): 1–8.
Chicago author-date (all authors)
Ozeki, Kenta, Gábor Wiener, and Carol Zamfirescu. 2020. “On Minimum Leaf Spanning Trees and a Criticality Notion.” Discrete Mathematics 343 (7): 1–8.
Vancouver
1.
Ozeki K, Wiener G, Zamfirescu C. On minimum leaf spanning trees and a criticality notion. Discrete Mathematics. 2020;343(7):1–8.
IEEE
[1]
K. Ozeki, G. Wiener, and C. Zamfirescu, “On minimum leaf spanning trees and a criticality notion,” Discrete Mathematics, vol. 343, no. 7, pp. 1–8, 2020.
@article{8655120,
  abstract     = {The minimum leaf number of a connected non-hamiltonian graph G is the number of leaves of a spanning tree of G with the fewest leaves among all spanning trees of G. Based on this quantity, Wiener introduced leaf-stable and leaf-critical graphs, concepts which generalise hypotraceability and hypohamiltonicity. In this article, we present new methods to construct leaf-stable and leaf-critical graphs and study their properties. Furthermore, we improve several bounds related to these families of graphs. These extend previous results of Horton, Thomassen, and Wiener.},
  articleno    = {111884},
  author       = {Ozeki, Kenta and Wiener, Gábor and Zamfirescu, Carol},
  issn         = {0012-365X},
  journal      = {Discrete Mathematics},
  keywords     = {Theoretical Computer Science,Discrete Mathematics and Combinatorics},
  language     = {eng},
  number       = {7},
  pages        = {111884:1--111884:8},
  title        = {On minimum leaf spanning trees and a criticality notion},
  url          = {http://dx.doi.org/10.1016/j.disc.2020.111884},
  volume       = {343},
  year         = {2020},
}

Altmetric
View in Altmetric