On the minimum leaf number of cubic graphs

DOI10.1016/J.DISC.2019.06.005MaRDI QIDQ2324488zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

spanning treecubicminimum leaf numbernon-traceable

Mathematics Subject Classification ID

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

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.

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.

Cites work

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

Cited in

(8)

• Cubic leaves
• 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

Describes a project that uses

Uses Software

• snarkhunter
• Traces
• nauty

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)