Edge-matching graph contractions and their interlacing properties. (English) Zbl 1459.05178
Summary: For a given graph \(\mathcal{G}\) of order \(n\) with \(m\) edges, and a real symmetric matrix associated to the graph, \(M(\mathcal{G})\in\mathbb{R}^{n\times n}\), the interlacing graph reduction problem is to find a graph \(\mathcal{G}_r\) of order \(r<n\) such that the eigenvalues of \(M(\mathcal{G}_r)\) interlace the eigenvalues of \(M(\mathcal{G})\). Graph contractions over partitions of the vertices are widely used as a combinatorial graph reduction tool. In this study, we derive a graph reduction interlacing theorem based on subspace mappings and the minmax theory. We then define a class of edge-matching graph contractions and show how two types of edge-matching contractions provide Laplacian and normalized Laplacian interlacing. An \(\mathcal{O}(mn)\) algorithm is provided for finding a normalized Laplacian interlacing contraction and an \(\mathcal{O}(n^2+nm)\) algorithm is provided for finding a Laplacian interlacing contraction.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05A18 | Partitions of sets |
| 05C05 | Trees |
| 05C38 | Paths and cycles |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 06A06 | Partial orders, general |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
References:
| [1] | Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226, 593-616 (1995) · Zbl 0831.05044 |
| [2] | Wu, B.-F.; Shao, J.-Y.; Liu, Y., Interlacing eigenvalues on some operations of graphs, Linear Algebra Appl., 430, 4, 1140-1150 (2009) · Zbl 1226.05172 |
| [3] | Chen, G.; Davis, G.; Hall, F.; Li, Z.; Patel, K.; Stewart, M., An interlacing result on normalized Laplacians, SIAM J. Discrete Math., 18, 2, 353-361 (2004) · Zbl 1079.05054 |
| [4] | Schaeffer, S. E., Graph clustering, Comput. Sci. Rev., 1, 1, 27-64 (2007) · Zbl 1302.68237 |
| [5] | Newman, M. E.; Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. A, 69, 2, Article 026113 pp. (2004) |
| [6] | Ng, A. Y.; Jordan, M. I.; Weiss, Y., On spectral clustering: analysis and an algorithm, (Advances in Neural Information Processing Systems (2002)), 849-856 |
| [7] | Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer · Zbl 0968.05002 |
| [8] | Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslov. Math. J., 25, 4, 619-633 (1975) · Zbl 0437.15004 |
| [9] | Bellman, R., Introduction to Matrix Analysis, vol. 19 (1997), SIAM · Zbl 0872.15003 |
| [10] | Godsil, C. D., Compact graphs and equitable partitions, Linear Algebra Appl., 255, 1-3, 259-266 (1997) · Zbl 0872.05033 |
| [11] | Wilf, H., Generatingfunctionology (1994), Academic Press Inc: Academic Press Inc New York · Zbl 0831.05001 |
| [12] | Horn, R. A.; Johnson, C. R., Matrix Analysis (1991), Cambridge University Press: Cambridge University Press New York, NY · Zbl 0729.15001 |
| [13] | Chong, K. W.; Lam, T. W., Finding connected components in o (log n log log n) time on the EREW PRAM, J. Algorithms, 18, 3, 378-402 (1995) · Zbl 0834.68089 |
| [14] | Minty, G., A simple algorithm for listing all the trees of a graph, IEEE Trans. Circuit Theory, 12, 1, 120 (1965) |
| [15] | Winter, P., An algorithm for the enumeration of spanning trees, BIT Numer. Math., 26, 1, 44-62 (1986) · Zbl 0602.68054 |
| [16] | Rockafellar, R. T., Network Flows and Monotropic Optimization (1984), Wiley-Interscience, no. 1-237 · Zbl 0596.90055 |
| [17] | Elezovic, N., Asymptotic expansions of central binomial coefficients and Catalan numbers, J. Integer Seq., 17, 2, Article 14.2.1 pp. (2014) · Zbl 1317.11023 |
| [18] | Chung, F. R.; Graham, F. C., Spectral Graph Theory, vol. 92 (1997), American Mathematical Soc. · Zbl 0867.05046 |
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.
