Block duplicate graphs and a hierarchy of chordal graphs
type: Item
instance of: scholarly article
title: Block duplicate graphs and a hierarchy of chordal graphs
zbMATH Open document ID: 1011.05051
DOI: 10.1016/S0166-218X(01)00330-4
author: Martin Charles Golumbic
author: Uri N. Peled
published in: Discrete Applied Mathematics
publication date: 2002-12-02T00:00:00Z
review text: All graphs considered in this paper are undirected, simple, and finite ones. It is known that a clique is an inclusion-maximal complete subgraph and that a block graph \(B\) is a graph whose blocks are cliques. Also it is well known that a graph is a block graph iff it is chordal and diamond-free. In the author's investigations the diamond, gem, arrow, jewel and crown are used, which are special chordal graphs; therefore they are also illustrated in the paper. A cut-vertex is a vertex whose removal increases the number of connected components of the graph, and two vertices of a graph are called true twins when they are adjacent and every other vertex is adjacent to both or to none of them. Then a block duplicate (BD) graph is a graph obtained by adding zero or more true twins to each vertex of a block graph \(B\), and if each cut-vertex belonging to three or more blocks in \(B\) receives at most one true twin, then the resulting graph is called a restricted block duplicate (RBD) graph. In the paper the structure of BD and RBD graphs is investigated and they are characterized by forbidden induced subgraphs. The authors get the following results: A graph is BD iff it is chordal and gem- and arrow-free (Theorem 1). A graph is RBD iff it is chordal and gem-, arrow- and jewel-free (Theorem 2). And additionally they give a survey on a hierarchy of special classes of chordal graphs.
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1839080
zbMATH Keywords: clique
zbMATH Keywords: block graph
zbMATH Keywords: true twins
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Distance-hereditary graphs
cites work: A sufficient condition for a matrix to be totally unimodular
cites work: Structural properties and recognition of restricted and strongly unimodular matrices
cites work: Characterizations of strongly chordal graphs
cites work: Q3328583
cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
cites work: Neighborhood perfect graphs
cites work: Restricted unimodular chordal graphs
description: scientific article; zbMATH DE number 1839080