Subgraph trees in graph theory

DOI10.1016/S0012-365X(03)00161-4MaRDI QIDQ1406544zbMATH OpenOpenAlexFDO

Authors Terry A. McKee

Publication date 4 September 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(03)00161-4

zbMATH Keywords

chordal bipartite graphschordal graphsclique treesdistance-hereditary graphsouterplanar graphsstrongly chordal graphssubgraph trees

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Review text

This survey paper discusses in detail the common sort of tree structures determined by selected induced subgraphs. This approach has been useful to study chordal graphs. Generalized clique trees selected, for example, by vertex neighbourhoods made it possible to extend concepts and results from chordal graphs to other graph classes, like---slightly surprisingly---outerplanar graphs. After outlining these concepts, special emphasis to strongly chordal graphs is given.

Recommendations

• Strong clique trees, neighborhood trees, and strongly chordal graphs
• Tree-structured graphs
• scientific article; zbMATH DE number 1011066
• scientific article; zbMATH DE number 554762
• Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs

Cites work

• A characterisation of rigid circuit graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A characterization of totally balanced hypergraphs
• Characterizations of strongly chordal graphs
• Complement reducible graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• Determinantal formulae for matrix completions associated with chordal graphs
• Distance-hereditary graphs
• Dually Chordal Graphs
• Graph Classes: A Survey
• Graphs whose neighborhoods have no special cycles
• Homogeneously orderable graphs
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 653261 (Why is no real title available?)
• scientific article; zbMATH DE number 1501961 (Why is no real title available?)
• scientific article; zbMATH DE number 751126 (Why is no real title available?)
• Hypergraphs with cyclomatic number zero, triangulated graphs, and an inequality
• Incidence graphs of biacyclic hypergraphs
• Induced cycle structure and outerplanarity
• Perfect Elimination and Chordal Bipartite Graphs
• Power of Natural Semijoins
• Representations of chordal graphs as subtrees of a tree
• Representing triangulated graphs in stars
• Strong clique trees, neighborhood trees, and strongly chordal graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The leafage of a chordal graph
• Topics in Intersection Graph Theory

Cited in

(7)

• Regular vines with strongly chordal pattern of (conditional) independence
• Maxclique and unit disk characterizations of strongly chordal graphs
• Junction trees of general graphs
• scientific article; zbMATH DE number 4145922 (Why is no real title available?)
• Algorithms on Subtree Filament Graphs
• Tree-structured graphs
• Graphs that have separator tree representations

This page was built for publication: Subgraph trees in graph theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1406544)