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 discret ...
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
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 polyg ...
is a triangle.
Examples
In a maximal planar graph, or more generally in everypolyhedral graph
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the Vertex (geometry), vertices and Edge (geometry), edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyh ...
, 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
Aclique-sum
In graph theory, a branch of mathematics, a clique sum (or clique-sum) is a way of combining two graphs by gluing them together at a clique (graph theory), clique, analogous to the connected sum operation in topology. If two graphs ''G'' and ''H'' ...
of two graphs is formed by identifying together two equal-sized cliques
A clique ( AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardle ...
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 i ...
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
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 compone ...
, 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