A separation property of planar triangulations | Zendy

Diestel Reinhard | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

A separation property of planar triangulations

Author(s) -

Diestel Reinhard

Publication year - 1987

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.3190110108

Subject(s) - chordal graph , combinatorics , mathematics , planar graph , pathwidth , property (philosophy) , class (philosophy) , outerplanar graph , characterization (materials science) , discrete mathematics , planar , indifference graph , triangulation , graph , line graph , computer science , geometry , philosophy , materials science , computer graphics (images) , epistemology , artificial intelligence , nanotechnology

Every planar triangulation G has the property that each induced cycle C of length at least 4 in G separates G , but no proper subgraph of C does. This property is trivially shared by all chordal graphs since these contain no such cycles at all. We ask to what extent maximally planar graphs and chordal graphs are unique with this property — or how much larger the class of graphs is that it determines. The answer is given in the form of a characterization of this class in terms of the simplicial decompositions of its elements. The theory of simplicial decompositions appears to be a very interesting, but still largely unexploited, method of characterization in graph theory, which seems tailor‐made for problems like the one discussed.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research