Block duplicate graphs and a hierarchy of chordal graphs (Q1850116)

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.