Generalized \(D\)-graphs for nonzero roots of the matching polynomial. (English) Zbl 1228.05182
Summary: Recently, D. Bauer, H. J. Broersma, A. Morgana and E. Schmeichel [J. Graph Theory 55, No.4, 343–358 (2007; Zbl 1120.05067)] 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 A. Busch, M. Ferrara and N. Kahl [Discrete Appl. Math. 155, No.18, 2487–2495 (2007; Zbl 1247.05186)]. Let \(\theta\) be a real number and \(\mu(G, x)\) be the matching polynomial of a graph \(G\). Let \(\text{mult}(\theta,G)\) be the multiplicity of \(\theta\) as a root of \(\mu(G,x)\). We observe that the notion of \(D\)-graph is implicitly related to \(\theta= 0\). In this paper, we give a natural generalization of the \(D\)-graph of \(G\) for any real number \(\theta\), and denote this new operator by \(D_\theta(G)\), so that \(D_\theta(G)\) coincides with \(D(G)\) when \(\theta=0\). We prove a characterization of maximal \(\theta\)-Tutte sets which are \(\theta\)-analogues of maximal Tutte sets in \(G\).
In particular, we show that for any \(X\subseteq V(G)\), \(|X|> 1\), and any real number \(\theta\), \(\text{mult}(\theta, G\setminus X)= \text{mult}(\theta, G)+|X|\) if and only if \(\text{mult}(\theta, G\setminus uv)= \text{mult}(\theta, G)+ 2\) for any \(u,v\in X\), \(u\neq v\), thus extending the preceding work of D. Bauer et al. [loc. cit.] and A. Busch et al. [loc. cit.] which established the result for the case \(\theta=0\). Subsequently, we show that every maximal \(\theta\)-Tutte set \(X\) is matchable to an independent set \(Y\) in \(G\); moreover, \(D_\theta(G)\) always contains an isomorphic copy of the subgraph induced by \(X\cup Y\). To this end, we introduce another related graph \(S_\theta(G)\) which is a supergraph of \(G\), and prove that \(S_\theta(G)\) and \(G\) have the same Gallai-Edmonds decomposition with respect to \(\theta\). Moreover, we determine the structure of \(D_\theta(G)\) in terms of its Gallai-Edmonds decomposition and prove that \(D_\theta(S_\theta(G))= D_\theta(G)\).
In particular, we show that for any \(X\subseteq V(G)\), \(|X|> 1\), and any real number \(\theta\), \(\text{mult}(\theta, G\setminus X)= \text{mult}(\theta, G)+|X|\) if and only if \(\text{mult}(\theta, G\setminus uv)= \text{mult}(\theta, G)+ 2\) for any \(u,v\in X\), \(u\neq v\), thus extending the preceding work of D. Bauer et al. [loc. cit.] and A. Busch et al. [loc. cit.] which established the result for the case \(\theta=0\). Subsequently, we show that every maximal \(\theta\)-Tutte set \(X\) is matchable to an independent set \(Y\) in \(G\); moreover, \(D_\theta(G)\) always contains an isomorphic copy of the subgraph induced by \(X\cup Y\). To this end, we introduce another related graph \(S_\theta(G)\) which is a supergraph of \(G\), and prove that \(S_\theta(G)\) and \(G\) have the same Gallai-Edmonds decomposition with respect to \(\theta\). Moreover, we determine the structure of \(D_\theta(G)\) in terms of its Gallai-Edmonds decomposition and prove that \(D_\theta(S_\theta(G))= D_\theta(G)\).
MSC:
| 05C31 | Graph polynomials |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Bauer, D.; Broersma, H. J.; Kahl, N.; Schmeichel, E.; Surowiec, T., Tutte sets in graphs II: the complexity of finding maximum Tutte sets, Discrete Appl. Math., 155, 1336-1343 (2007) · Zbl 1119.05086 |
| [2] | Bauer, D.; Broersma, H. J.; Morgana, A.; Schmeichel, E., Tutte sets in graphs I: maximal tutte sets and D-graphs, J. Graph Theory, 55, 343-358 (2007) · Zbl 1120.05067 |
| [3] | Busch, A.; Ferrara, M.; Kahl, N., Generalizing D-graphs, Discrete Appl. Math., 155, 2487-2495 (2007) · Zbl 1247.05186 |
| [4] | Chen, W.; Ku, C. Y., An analogue of the Gallai-Edmonds structure theorem for nonzero roots of the matching polynomial, J. Combin. Theory Ser. B, 100, 119-127 (2010) · Zbl 1209.05183 |
| [5] | Godsil, C. D., Algebraic Combinatorics (1993), Chapman and Hall: Chapman and Hall New York · Zbl 0814.05075 |
| [6] | Godsil, C. D., Algebraic matching theory, Electron. J. Combin., 2, # R8 (1995) · Zbl 0818.05063 |
| [7] | Heilmann, O. J.; Lieb, E. H., Theory of monomer-dimer system, Commun. Math. Phys., 25, 190-232 (1972) · Zbl 0228.05131 |
| [8] | Ku, C. Y.; Wong, K. B., Extensions of barrier sets to nonzero roots of the matching polynomial, Discrete Math., 310, 3544-3550 (2010) · Zbl 1200.05109 |
| [9] | Ku, C. Y.; Wong, K. B., Maximum multiplicity of a root of the matching polynomial of a tree and minimum path cover, Electron. J. Combin., 16, #R81 (2009) · Zbl 1230.05168 |
| [10] | Ku, C. Y.; Wong, K. B., Maximum multiplicity of matching polynomial roots and minimum path cover in general graph, Electron. J. Combin., 18, #P38 (2011) · Zbl 1229.05121 |
| [11] | Lovász, L.; Plummer, M. D., Matching Theory (1986), Elsevier Science Publishers: Elsevier Science Publishers Budapest · Zbl 0618.05001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
