Generalized -graphs for nonzero roots of the matching polynomial

Recently, Bauer et al. [D. Bauer, H.J. Broersma, A. Morgana, E. Schmeichel, Tutte sets in graphs I: maximal Tutte sets and D -graphs, J. Graph Theory 55 (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. [A. Busch, M. Ferrara, N. Kahl, Generalizing D -graphs, Discrete Appl. Math. 155 (2007) 2487–2495]. Let θ be a real number and μ ( G , x ) be the matching polynomial of a graph G . Let mult ( θ , 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 θ -analogues of maximal Tutte sets in G . In particular, we show that for any X ⊆ V ( G ) , | X | > 1 , and any real number θ , mult ( θ , G ∖ X ) = mult ( θ , G ) + | X | if and only if mult ( θ , G ∖ u v ) = mult ( θ , G ) + 2 for any u , v ∈ X , u ≠ v , thus extending the preceding work of Bauer et al. (2007) [2] and Busch et al. (2007) [3] which established the result for the case θ = 0 . Subsequently, we show that every maximal θ -Tutte set X is matchable to an independent set Y in G ; moreover, D θ ( G ) always contains an isomorphic copy of the subgraph induced by X ∪ Y . To this end, we introduce another related graph S θ ( G ) which is a supergraph of G , and prove that S θ ( G ) and G have the same Gallai–Edmonds decomposition with respect to θ . Moreover, we determine the structure of D θ ( G ) in terms of its Gallai–Edmonds decomposition and prove that D θ ( S θ ( G ) ) = D θ ( G ) .