Oriented hypergraphic matrix-tree type theorems and bidirected minors via Boolean order ideals. (English) Zbl 1416.05179
Summary: Restrictions of incidence preserving path maps produce oriented hypergraphic all minors matrix-tree theorems for Laplacian and adjacency matrices. The images of these maps produce a locally signed graphic, incidence generalization, of cycle covers and basic figures that correspond to incidence-\(k\)-forests. When restricted to bidirected graphs, the natural partial ordering of maps results in disjoint signed Boolean lattices whose minor calculations correspond to principal order ideals. As an application, (1) the determinant formula of a signed graphic Laplacian is reclaimed and shown to be determined by the maximal positive-circle-free elements, and (2) spanning trees are equivalent to single-element order ideals.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C65 | Hypergraphs |
| 05C22 | Signed and weighted graphs |
| 05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |
References:
| [1] | Belardo, F.; Simić, S., On the Laplacian coefficients of signed graphs, Linear Algebra Appl., 475, 94-113 (2015) · Zbl 1312.05078 · doi:10.1016/j.laa.2015.02.007 |
| [2] | Berge, C.: Hypergraphs, North-Holland Mathematical Library, vol. 45. North-Holland Publishing Co., Amsterdam (1989). Combinatorics of finite sets (Transl: French) · Zbl 0674.05001 |
| [3] | Bronski, JC; DeVille, L., Spectral theory for dynamics on graphs containing attractive and repulsive interactions, SIAM J. Appl. Math., 74, 1, 83-105 (2014) · Zbl 1332.05086 · doi:10.1137/130913973 |
| [4] | Chaiken, S., A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebr. Discrete Methods, 3, 3, 319-329 (1982) · Zbl 0495.05018 · doi:10.1137/0603033 |
| [5] | Chaiken, S.; Kleitman, D., Matrix tree theorems, J. Comb. Theory Ser. A, 24, 3, 377-381 (1978) · Zbl 0376.05032 · doi:10.1016/0097-3165(78)90067-5 |
| [6] | Chen, G., Liu, V., Robinson, E., Rusnak, L.J., Wang, K.: A characterization of oriented hypergraphic Laplacian and adjacency matrix coefficients. arXiv:1704.03599 [math.CO] (2017) · Zbl 1394.05070 |
| [7] | Chen, V.; Rao, A.; Rusnak, L.; Yang, A., A characterization of oriented hypergraphic balance via signed weak walks, Linear Algebra Appl., 485, 442-453 (2015) · Zbl 1322.05087 · doi:10.1016/j.laa.2015.08.001 |
| [8] | Chung, FRK; Langlands, RP, A combinatorial Laplacian with vertex weights, J. Comb. Theory Ser. A, 75, 2, 316-327 (1996) · Zbl 0866.05039 · doi:10.1006/jcta.1996.0080 |
| [9] | Conforti, M.; Cornuéjols, G.; Rao, MR, Decomposition of balanced matrices, J. Comb. Theory Ser. B, 77, 2, 292406 (1999) · Zbl 1023.05025 · doi:10.1006/jctb.1999.1932 |
| [10] | Conforti, M.; Cornuéjols, G.; Vušković, K., Balanced matrices, Discrete Math., 306, 19-20, 2411-2437 (2006) · Zbl 1102.05013 · doi:10.1016/j.disc.2005.12.033 |
| [11] | Cvetkovic, D.; Doob, M.; Sachs, H., Spectra of Graphs: Theory and Applications (1998), Oxford: Oxford Science Publications, Oxford · Zbl 0824.05046 |
| [12] | Edmonds, J., Johnson, E.L.: Matching: a well-solved class of integer linear programs. In: Combinatorial Structures and Their Applications (Proc. Calgary Internat., Calgary, Alta., 1969), pp. 89-92. Gordon and Breach, New York (1970) · Zbl 0258.90032 |
| [13] | Fulkerson, D.; Hoffman, A.; Oppenheim, R., On balanced matrices, Math. Program. Study, 1, 120-132 (1974) · Zbl 0357.90038 · doi:10.1007/BFb0121244 |
| [14] | Graovac, A.; Gutman, I.; Trinajstić, N.; Živković, T., Graph theory and molecular orbitals, Theoret. Chimica Acta, 26, 1, 67-78 (1972) · doi:10.1007/BF00527654 |
| [15] | Grilliette, W.; Seacrest, D.; Seacrest, T., On blow-ups and injectivity of quivers, Electron. J. Comb., 20, 2, 40 (2013) · Zbl 1266.05099 |
| [16] | Levine, L., Sandpile groups and spanning trees of directed line graphs, J. Comb. Theory Ser. A, 118, 2, 350-364 (2011) · Zbl 1292.05135 · doi:10.1016/j.jcta.2010.04.001 |
| [17] | Reff, N., Spectral properties of complex unit gain graphs, Linear Algebra Appl., 436, 9, 3165-3176 (2012) · Zbl 1241.05085 · doi:10.1016/j.laa.2011.10.021 |
| [18] | Reff, N.; Rusnak, L., An oriented hypergraphic approach to algebraic graph theory, Linear Algebra Appl., 437, 9, 2262-2270 (2012) · Zbl 1247.05164 · doi:10.1016/j.laa.2012.06.011 |
| [19] | Rusnak, L., Oriented hypergraphs: introduction and balance, Electron. J. Comb., 20, 3, 48 (2013) · Zbl 1295.05169 |
| [20] | Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency, Vol. A-C, Algorithms and Combinatorics (2004), Berlin: Springer, Berlin · Zbl 1072.90030 |
| [21] | Shi, CJ, A signed hypergraph model of the constrained via minimization problem, Microelectron. J., 23, 7, 533-542 (1992) · doi:10.1016/0026-2692(92)90064-8 |
| [22] | Shi, CJ; Brzozowski, JA, A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis, Discrete Appl. Math., 90, 1-3, 223-243 (1999) · Zbl 0913.68104 · doi:10.1016/S0166-218X(98)00092-4 |
| [23] | Tutte, W.T.: Graph Theory, Encyclopedia of Mathematics and Its Applications, vol. 21. Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, With a foreword by C. St. J. A, Nash-Williams (1984) · Zbl 0554.05001 |
| [24] | Wang, Y.; Gope, D.; Jandhyala, V.; Shi, CJ, Generalized Kirchoff’s current and voltage law formulation for coupled circuit-electromagnetic simulation with surface integral equations, IEEE Trans. Microwave Theory Tech., 52, 7, 1673-1682 (2004) · doi:10.1109/TMTT.2004.830482 |
| [25] | Zaslavsky, T., Signed graphs, Discrete Appl. Math., 4, 1, 47-74 (1982) · Zbl 0476.05080 · doi:10.1016/0166-218X(82)90033-6 |
| [26] | Zaslavsky, T., Orientation of signed graphs, Eur. J. Combin., 12, 4, 361-375 (1991) · Zbl 0761.05095 · doi:10.1016/S0195-6698(13)80118-7 |
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.
