Strangulated Graph on:
[Wikipedia]
[Google]
[Amazon]
In graph theoretic mathematics, a strangulated graph is a graph in which deleting the edges of any
In graph theoretic mathematics, a strangulated graph is a graph in which deleting the edges of any induced cycle
In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an ...
of length greater than three would disconnect the remaining graph. That is, they are the graphs in which every peripheral cycle
In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygo ...
is a triangle.
Examples
In a maximal planar graph, or more generally in every polyhedral graph, the peripheral cycles are exactly the faces of a planar embedding of the graph, so a polyhedral graph is strangulated if and only if all the faces are triangles, or equivalently it is maximal planar. Every chordal graph is strangulated, because the only induced cycles in chordal graphs are triangles, so there are no longer cycles to delete.Characterization
A clique-sum of two graphs is formed by identifying together two equal-sized cliques in each graph, and then possibly deleting some of the clique edges. For the version of clique-sums relevant to strangulated graphs, the edge deletion step is omitted. A clique-sum of this type between two strangulated graphs results in another strangulated graph, for every long induced cycle in the sum must be confined to one side or the other (otherwise it would have a chord between the vertices at which it crossed from one side of the sum to the other), and the disconnected parts of that side formed by deleting the cycle must remain disconnected in the clique-sum. Every chordal graph can be decomposed in this way into a clique-sum of complete graphs, and every maximal planar graph can be decomposed into a clique-sum of 4-vertex-connected maximal planar graphs. As show, these are the only possible building blocks of strangulated graphs: the strangulated graphs are exactly the graphs that can be formed as clique-sums of complete graphs and maximal planar graphs.See also
*Line perfect graph
In graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle.
A graph is line perfect if and only if each of its biconnected c ...
, a graph in which every odd cycle is a triangle
References
*{{citation , last1 = Seymour , first1 = P. D. , author1-link = Paul Seymour (mathematician) , last2 = Weaver , first2 = R. W. , doi = 10.1002/jgt.3190080206 , issue = 2 , journal = Journal of Graph Theory , mr = 742878 , pages = 241–251 , title = A generalization of chordal graphs , volume = 8 , year = 1984. Graph families Planar graphs