Template-Type: ReDIF-Paper 1.0
Author-Name: Laskar, R.C.
Author-Name-Last: Laskar
Author-Name-First: R.C.
Author-Name: Mulder, H.M.
Author-Name-Last: Mulder
Author-Name-First: Martyn
Author-Name: Novick, B.
Author-Name-Last: Novick
Author-Name-First: Beth
Title: Maximal outerplanar graphs as chordal graphs, path-neighborhood graphs, and triangle graphs
Abstract: 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.
Creation-Date: 2011-06-07
File-URL: https://repub.eur.nl/pub/23560/EI2011-16.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI 2011-16
Keywords: chordal graph, elimination ordering, maximal outerplanar graph, path-neighborhood graph, triangle graph
Handle: RePEc:ems:eureir:23560