Establishes the sharp bound a(G)−α(G)≤2μ(G)+1−⌈√(6μ(G))⌉ attained for all μ(G)≥1, plus matching-dependent bounds for forests/bipartite/König-Egerváry graphs and an independent proof of α(G)≥(a(G)+res(G))/Δ(G) for connected G with n≥3.
Maximum and minimum nullity of a tree degree sequence
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The nullity of a graph is the multiplicity of the eigenvalue zero in its adjacency spectrum. In this paper, we give a closed formula for the minimum and maximum nullity among trees with the same degree sequence, using the notion of matching number and annihilation number. Algorithms for constructing such minimum-nullity and maximum-nullity trees are described.
fields
math.CO 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Annihilation, Independence, and Residue: Sharp Matching Bounds for the Annihilation Gap and a TxGraffiti Application
Establishes the sharp bound a(G)−α(G)≤2μ(G)+1−⌈√(6μ(G))⌉ attained for all μ(G)≥1, plus matching-dependent bounds for forests/bipartite/König-Egerváry graphs and an independent proof of α(G)≥(a(G)+res(G))/Δ(G) for connected G with n≥3.