On the minimum leaf number of cubic graphs

DOI10.1016/J.DISC.2019.06.005zbMATH Open1419.05045arXiv1806.04451OpenAlexW2963661095WikidataQ127576600 ScholiaQ127576600MaRDI QIDQ2324488FDOQ2324488

Authors: Jan Goedgebeur, Kenta Ozeki, Gábor Wiener, Nico Van Cleemput 

Publication date: 11 September 2019

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The emph{minimum leaf number} $hboxml(G)$ of a connected graph $G$ is defined as the minimum number of leaves of the spanning trees of $G$. We present new results concerning the minimum leaf number of cubic graphs: we show that if $G$ is a connected cubic graph of order $n$, then $mathrmml(G)leqfracn6+frac13$, improving on the best known result in [Inf. Process. Lett. 105 (2008) 164-169] and proving the conjecture in [Electron. J. Graph Theory and Applications 5 (2017) 207-211]. We further prove that if $G$ is also 2-connected, then $mathrmml(G)leqfracn6.53$, improving on the best known bound in [Math. Program., Ser. A 144 (2014) 227-245]. We also present new conjectures concerning the minimum leaf number of several types of cubic graphs and examples showing that the bounds of the conjectures are best possible.

Full work available at URL: https://arxiv.org/abs/1806.04451

Recommendations

• Spanning trees with many leaves in cubic graphs
• A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Cubic graphs with minimum number of spanning trees.
• On minimum leaf spanning trees and a criticality notion
• Minimum degree, leaf number and traceability.

zbMATH Keywords

spanning treecubicminimum leaf numbernon-traceable

Mathematics Subject Classification ID

Trees (05C05) Combinatorial optimization (90C27) Connectivity (05C40)

Cites Work

• Practical graph isomorphism. II.
• Generation of cubic graphs
• Graph theory with applications
• Title not available (Why is that?)
• Paths, Stars and the Number Three
• The smallest 2-connected cubic bipartite planar nonhamiltonian graph
• The traveling salesman problem on cubic and subcubic graphs
• Approximating Graphic TSP by Matchings
• On finding spanning trees with few leaves
• On non-traceable, non-hypotraceable, arachnoid graphs
• On Hamiltonian Circuits
• A class of Hamiltonian polytopes
• Three small cubic graphs with interesting hamiltonian properties
• The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
• Title not available (Why is that?)
• Covering 2-connected 3-regular graphs with disjoint paths
• On the 2-factors of bicubic graphs
• The smallest cubic multigraphs with prescribed bipartite, block, Hamiltonian and planar properties
• A note on the path cover number of regular graphs
• Leaf-critical and leaf-stable graphs
• Spanning \(k\)-ended trees of 3-regular connected graphs

Cited In (8)

• A note on connected domination number and leaf number
• Cubic graphs with minimum number of spanning trees.
• Induced path factors of regular graphs
• Spanning trees with many leaves in cubic graphs
• Scatter search for the minimum leaf spanning tree problem
• The decycling number of a line graph
• The color number of cubic graphs having a spanning tree with a bounded number of leaves
• Cubic leaves

Uses Software

• nauty
• Traces
• snarkhunter

This page was built for publication: On the minimum leaf number of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2324488)