graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, 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 Horst Sachs (27 March 1927 – 25 April 2016) was a German mathematician, an expert in graph theory, a recipient of the Euler Medal (2000). He earned the degree of Doctor of Science (Dr. rer. nat.) from the Martin-Luther-Universität Halle- ...

, who used them in an expansion of the

characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...

of the

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...

of graphs. A similar expansion using Sachs subgraphs is also possible for permanental polynomials of graphs. Sachs subgraphs and the polynomials calculated with their aid have been applied in chemical graph theory, for instance as part of a test for the existence of non-bonding orbitals in

hydrocarbon In organic chemistry, a hydrocarbon is an organic compound consisting entirely of hydrogen and carbon. Hydrocarbons are examples of group 14 hydrides. Hydrocarbons are generally colourless and hydrophobic, and their odors are usually weak or ...

structures. A spanning Sachs subgraph, also called a -factor, is a Sachs subgraph in which every vertex of the given graph is incident to an edge of the subgraph. The union of two

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

s 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.

References

{{reflist, refs= {{citation , last1 = Aaghabali , first1 = M. , last2 = Akbari , first2 = S. , last3 = Tajfirouz , first3 = Z. , doi = 10.1080/03081087.2016.1179710 , issue = 1 , journal = Linear and Multilinear Algebra , mr = 3575888 , pages = 204–209 , title = Order of the largest Sachs subgraphs in graphs , volume = 65 , year = 2017, s2cid = 124186154 {{citation , last1 = Li , first1 = Wei , last2 = Liu , first2 = Shunyi , last3 = Wu , first3 = Tingzeng , last4 = Zhang , first4 = Heping , contribution = On the permanental polynomials of graphs , mr = 3790914 , pages = 101–121 , publisher = CRC Press , location = Boca Raton, Florida , series = Discrete Mathematics and its Applications , title = Graph Polynomials , year = 2017 {{citation , last = Sachs , first = Horst , authorlink = Horst Sachs , journal = Publicationes Mathematicae Debrecen , language = de , mr = 172271 , pages = 119–134 , title = Beziehungen zwischen den in einem Graphen enthaltenen Kreisen und seinem charakteristischen Polynom , volume = 11 , year = 1964 {{citation , last1 = Tyutyulkov , first1 = N. , last2 = Dietz , first2 = F. , last3 = Müllen , first3 = K. , last4 = Baumgarten , first4 = M. , last5 = Karabunarliev , first5 = S. , date = September 1993 , doi = 10.1007/bf01128522 , issue = 4 , journal = Theoretica Chimica Acta , pages = 353–367 , title = Structure and properties of non-classical polymers , volume = 86 {{citation , last1 = Wagner , first1 = Stephan , last2 = Wang , first2 = Hua , isbn = 978-1-138-32508-1 , mr = 3837106 , page = 215 , publisher = CRC Press , location = Boca Raton, Florida , series = Discrete Mathematics and its Applications , title = Introduction to Chemical Graph Theory , year = 2019 {{citation , last1 = Yang , first1 = Yujun , last2 = Ye , first2 = Dong , doi = 10.1007/s00493-016-3502-y , issue = 5 , journal = Combinatorica , mr = 3884787 , pages = 1251–1263 , title = Inverses of bipartite graphs , volume = 38 , year = 2018, arxiv = 1611.06535 , s2cid = 54465291 Graph theory objects