Strangulated Graph on:
[Wikipedia]
[Google]
[Amazon]
In graph theoretic mathematics, a strangulated graph is a
In graph theoretic mathematics, a strangulated graph is a graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
in which deleting the edges of any induced cycle of length greater than three would disconnect the remaining graph. That is, they are the graphs in which every peripheral cycle is a triangle.
Examples
In amaximal planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cros ...
, or more generally in every polyhedral graph
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-con ...
, 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
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...
is strangulated, because the only induced cycles in chordal graphs are triangles, so there are no longer cycles to delete.
Characterization
Aclique-sum
In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs ''G'' and ''H'' each contain cliques of equal size, th ...
of two graphs is formed by identifying together two equal-sized cliques
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
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 graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
s, 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, a graph in which every odd cycle is a triangleReferences
*{{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