Please use this identifier to cite or link to this item:
Title: Generalized D-graphs for nonzero roots of the matching polynomial
Authors: Ku, C.Y. 
Wong, K.B.
Keywords: D-graphs
Extreme sets
GallaiEdmonds decomposition
Matching polynomial
Tutte sets
Issue Date: 28-Oct-2011
Citation: Ku, C.Y., Wong, K.B. (2011-10-28). Generalized D-graphs for nonzero roots of the matching polynomial. Discrete Mathematics 311 (20) : 2174-2186. ScholarBank@NUS Repository.
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.
Source Title: Discrete Mathematics
ISSN: 0012365X
DOI: 10.1016/j.disc.2011.07.004
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.