Generalized D-graphs for nonzero roots of the matching polynomial

Abstract

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) 343358] 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) 24872495]. 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\uv)= 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 GallaiEdmonds decomposition with respect to θ. Moreover, we determine the structure of Dθ(G) in terms of its GallaiEdmonds decomposition and prove that Dθ( Sθ(G))= Dθ(G). © 2011 Elsevier B.V. All rights reserved.