Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.disc.2011.07.004
DC FieldValue
dc.titleGeneralized D-graphs for nonzero roots of the matching polynomial
dc.contributor.authorKu, C.Y.
dc.contributor.authorWong, K.B.
dc.date.accessioned2014-10-28T02:35:55Z
dc.date.available2014-10-28T02:35:55Z
dc.date.issued2011-10-28
dc.identifier.citationKu, 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. https://doi.org/10.1016/j.disc.2011.07.004
dc.identifier.issn0012365X
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/103327
dc.description.abstractRecently, 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.disc.2011.07.004
dc.sourceScopus
dc.subjectD-graphs
dc.subjectExtreme sets
dc.subjectGallaiEdmonds decomposition
dc.subjectMatching polynomial
dc.subjectTutte sets
dc.typeArticle
dc.contributor.departmentMATHEMATICS
dc.description.doi10.1016/j.disc.2011.07.004
dc.description.sourcetitleDiscrete Mathematics
dc.description.volume311
dc.description.issue20
dc.description.page2174-2186
dc.description.codenDSMHA
dc.identifier.isiut000295202100011
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

4
checked on Jan 23, 2023

WEB OF SCIENCETM
Citations

3
checked on Jan 23, 2023

Page view(s)

145
checked on Jan 26, 2023

Google ScholarTM

Check

Altmetric


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