Maximal outerplanar graphs as chordal graphs, path-neighborhood graphs, and triangle graphs
2011-06-07
Research Paper
pp 1-12.
This publication is part of collection
| Related Files |
|---|
View PDF Version
(EI2011-16.pdf, 0.2MB) |
Maximal outerplanar graphs are characterized using three different classes of graphs. A path-neighborhood graph is a connected graph in which every neighborhood induces a path. The triangle graph $T(G)$ has the triangles of the graph $G$ as its vertices, two of these being adjacent whenever as triangles in $G$ they share an edge. A graph is edge-triangular if every edge is in at least one triangle. The main results can be summarized as follows: the class of maximal outerplanar graphs is precisely the intersection of any of the two following classes: the chordal graphs, the path-neighborhood graphs, the edge-triangular graphs having a tree as triangle graph.
Keywords
Automatically Extracted Terms
- graph
- outerplanar
- outerplanar graph
- triangle
- outerplanar graphs
- vertex
- g − v
- chordal
- vertice
- class
- simplicial
- graph g
- theorem
- path-neighborhood graph
- path-neighborhood
- elimination
- chordal graphs
- neighborhood
- degree
- edge-triangular
