2009/09/29 by Cheng Yeaw Ku, Ku, Cheng Yeaw, Kok Bin Wong +1
Computer Science · Mathematics · #05C31 #05C70 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Polynomial and algebraic computation #math.CO #msc:05C31 #msc:05C70
paper · pdf · doi:10.48550/arxiv.0909.5266
22 pages
arxiv created 2009/09/29 · openalex publication_date 2009/09/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recently, Bauer et al. (J Graph Theory 55(4) (2007), 343--358) introduced a graph operator D(G), called the D-graph of G, which has been useful in investigating the structural aspects of maximal Tutte sets in G with a perfect matching. Among other results, they proved a characterization of maximal Tutte sets in terms of maximal independent sets in the graph D(G) and maximal extreme sets in G. This was later extended to graphs without perfect matchings by Busch et al. (Discrete Appl. Math. 155 (2007), 2487--2495). Let θ be a real number and μ(G,x) be the matching polynomial of a graph G. Let \textnormalmult (θ, G) be the multiplicity of θ as a root of μ(G,x). We observe that the notion of D-graph is implicitly related to θ=0. In this paper, we give a natural generalization of the D-graph of G for any real number θ, and denote this new operator by Dθ(G), so that Dθ(G) coincides with D(G) when θ=0. We prove a characterization of maximal θ-Tutte sets which are θ-analogue of maximal Tutte sets in G. In particular, we show that for any X ⊆ V(G), |X|>1, and any real number θ, \m(θ, G ∖ X)=\m(θ, G)+|X| if and only if \m(θ, G ∖ uv)=\m(θ, G)+2 for any u, v ∈ X, u \not = v, thus extending the preceding work of Bauer et al. and Busch et al. which established the result for the case θ=0.