Intersection models of weakly chordal graphs |
| |
Authors: | Martin Charles Golumbic Michal Stern |
| |
Affiliation: | Caesarea Rothschild Institute, University of Haifa, Haifa, Israel |
| |
Abstract: | We first present new structural properties of a two-pair in various graphs. A two-pair is used in a well-known characterization of weakly chordal graphs. Based on these properties, we prove the main theorem: a graph G is a weakly chordal ()-free graph if and only if G is an edge intersection graph of subtrees on a tree with maximum degree 4. This characterizes the so called [4, 4, 2] graphs. The proof of the theorem constructively finds the representation. Thus, we obtain an algorithm to construct an edge intersection model of subtrees on a tree with maximum degree 4 for such a given graph. This is a recognition algorithm for [4, 4, 2] graphs. |
| |
Keywords: | Weakly chordal graph Edge intersection graph of subtrees on a tree |
本文献已被 ScienceDirect 等数据库收录! |
|