The number of odd spanning trees in almost multipartite graphs

Abstract

This paper combines the Weighted Matrix-Tree Theorem with Boolean function analysis and the Schur complement decomposition method to study the enumeration of odd spanning trees, in which every vertex has odd degree, in almost multipartite graphs, and derives an explicit formula for the number of labeled odd spanning trees. For the almost complete bipartite graph 𝐾 𝑛 1 , 𝑛 2 − 𝑞 ⁢ 𝐾 2 , with n 1 , n 2 odd and 1 ≤ q ≤ min { n 1 , n 2 }, the formula reads 1 2 𝑛 1 + 𝑛 2 ⁢ ∑ 𝜀 ∈ { ± 1 } 𝑛 1 𝛿 ∈ { ± 1 } 𝑛 2 ( ∏ 𝑛 1 𝑖 = 1 𝜀 𝑖 ⁢ ∏ 𝑛 2 𝑗 = 1 𝛿 𝑗 ) ⁢ d e t ⁡ ( 𝐿 1 1 ⁡ ( 𝜀 , 𝛿 ) ) , where d e t ⁡ ( 𝐿 1 1 ⁡ ( 𝜀 , 𝛿 ) ) = d e t ⁡ ( ̃ 𝐷 𝑈 ) · d e t ⁡ ( d i a g ⁡ ( 𝑆 𝜀 − 𝜎 1 ⁡ ( 𝜀 ) , ⋯ , 𝑆 𝜀 − 𝜎 𝑛 2 ⁡ ( 𝜀 ) ) − 𝑅 ) is the relevant cofactor of the weighted Laplacian matrix of 𝐾 𝑛 1 , 𝑛 2 − 𝑞 ⁢ 𝐾 2 . We then extend the framework to the general k -partite setting with k ≥ 3, considering the almost multipartite graphs 𝐾 𝑛 1 , ⋯ , 𝑛 𝑘 − 𝑞 ⁢ 𝐾 2 . In this setting, we obtain a unified exact counting formula 1 2 𝑁 ⁢ ∑ 𝐱 ∈ { − 1 , 1 } 𝑁 ( ∏ 𝑣 𝑥 𝑣 ) ⁢ d e t ⁡ ( 𝑀 0 ⁡ ( 𝐱 ) − 𝐵 ⁢ 𝑊 ⁡ ( 𝐱 ) ⁢ 𝐵 𝑇 ) , where 𝐵 = [ 𝑏 1 ⋯ 𝑏 𝑞 ] and 𝑊 ⁡ ( 𝐱 ) = d i a g ⁡ ( 𝑥 𝑎 1 ⁢ 𝑥 𝑏 1 , … , 𝑥 𝑎 𝑞 ⁢ 𝑥 𝑏 𝑞 ) .