In graph theory, a Sachs subgraph of a given graph is a subgraph in which all connected components are either single edges or cycles. These subgraphs are named after Horst Sachs, who used them in an expansion of the characteristic polynomial of the adjacency matrix of graphs.[1] A similar expansion using Sachs subgraphs is also possible for permanental polynomials of graphs.[2] Sachs subgraphs and the polynomials calculated with their aid have been applied in chemical graph theory,[3] for instance as part of a test for the existence of non-bonding orbitals in hydrocarbon structures.[4]
A spanning Sachs subgraph, also called a {1,2}-factor, is a Sachs subgraph in which every vertex of the given graph is incident to an edge of the subgraph.[5] The union of two perfect matchings is always a bipartite spanning Sachs subgraph, but in general Sachs subgraphs are not restricted to being bipartite. Some authors use the term "Sachs subgraph" to mean only spanning Sachs subgraphs.[6]
References
edit- ^ Sachs, Horst (1964), "Beziehungen zwischen den in einem Graphen enthaltenen Kreisen und seinem charakteristischen Polynom", Publicationes Mathematicae Debrecen (in German), 11: 119–134, MR 0172271
- ^ Li, Wei; Liu, Shunyi; Wu, Tingzeng; Zhang, Heping (2017), "On the permanental polynomials of graphs", Graph Polynomials, Discrete Mathematics and its Applications, Boca Raton, Florida: CRC Press, pp. 101–121, MR 3790914
- ^ Wagner, Stephan; Wang, Hua (2019), Introduction to Chemical Graph Theory, Discrete Mathematics and its Applications, Boca Raton, Florida: CRC Press, p. 215, ISBN 978-1-138-32508-1, MR 3837106
- ^ Tyutyulkov, N.; Dietz, F.; Müllen, K.; Baumgarten, M.; Karabunarliev, S. (September 1993), "Structure and properties of non-classical polymers", Theoretica Chimica Acta, 86 (4): 353–367, doi:10.1007/bf01128522
- ^ Aaghabali, M.; Akbari, S.; Tajfirouz, Z. (2017), "Order of the largest Sachs subgraphs in graphs", Linear and Multilinear Algebra, 65 (1): 204–209, doi:10.1080/03081087.2016.1179710, MR 3575888, S2CID 124186154
- ^ Yang, Yujun; Ye, Dong (2018), "Inverses of bipartite graphs", Combinatorica, 38 (5): 1251–1263, arXiv:1611.06535, doi:10.1007/s00493-016-3502-y, MR 3884787, S2CID 54465291