Spanning Trees and Domination in Hypercubes

2019/05/30 by Griggs, Jerrold R. · 1 citation
#05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1905.13292

Abstract

Let L(G) denote the maximum number of leaves in any spanning tree of a connected graph G. We show the (known) result that for the n-cube Q_n, L(Q_n) ∼ 2ⁿ = |V(Q_n)| as n→ ∞. Examining this more carefully, consider the minimum size of a connected dominating set of vertices γ_c(Q_n), which is 2ⁿ-L(Q_n) for n≥2. We show that γ_c(Q_n)∼ 2ⁿ/n. We use Hamming codes and an "expansion" method to construct leafy spanning trees in Q_n.

Cited by

• Multiparty equality in the local broadcast model

Related

• Completely independent spanning trees in the hypercube
• New Upper Bounds on the Minimal Domination Numbers of High-Dimensional Hypercubes
• Max-Leaves Spanning Tree is APX-hard for Cubic Graphs
• Multipacking in Hypercubes
• Spanning trees in the square of pseudorandom graphs