Clique neighborhoods and nearly chordal graphs
type: Item
instance of: scholarly article
title: Clique neighborhoods and nearly chordal graphs
zbMATH Open document ID: 0880.05073
DOI: 10.1016/S0012-365X(96)00028-3
author: Terry A. McKee
published in: Discrete Mathematics
publication date: 1998-01-19T00:00:00Z
review text: The families of maximal complete subgraphs (max-cliques) and of minimal vertex separators are studied. The second family consists of minimal vertex sets \(S\) for which there exist vertices \(u\), \(v\) such that every \(u,v\)-path contains a vertex in \(S\). It is a fundamental concept for the characterization of chordal graphs (the ``1-ekachordal'' graphs). Let \(k_i(G)\) denote the number of \(i\)-cliques contained in a graph \(G\) (hence \(k_1(G)\) is the number of vertices and \(k_2(G)\) the number of edges of \(G\)). Let \(\text{comp }G\) denote the number of components in \(G\) and \(\text{char }G\) the (Euler) characteristic \(k_1(G)- k_2(G)+ k_3(G)-\cdots\). Further, the (clique) neighborhood \(N(Q)\) of a complete subgraph \(Q\) of a graph \(G\) is defined to be the subgraph induced by those vertices that are adjacent to every vertex of \(Q\). By using this concept, the two above-mentioned families are generalized to three families \({\mathfrak C}_1\), \({\mathfrak C}_2\), and \({\mathfrak C}_3\). When a neighborhood separator of \(G\) is defined to be a complete subgraph \(Q\) such that \(N(Q)\) is disconnected, then \({\mathfrak C}_2= {\mathfrak C}_2(G)\) is defined to be the multiset (a set with possibly repeated elements) consisting of all neighborhood separators of \(G\), with the multiplicity of \(Q\in{\mathfrak C}_2\) equal to \(\text{comp }N(Q)- 1\). Let \({\mathfrak C}_3= {\mathfrak C}_3(G)\) be the multiset consisting of all complete subgraphs \(Q\) of \(G\) for which \(\text{comp }N(Q)> \text{char }N(Q)\), with the multiplicity of \(Q\in{\mathfrak C}_3\) equal to \(\text{comp }N(Q)-\text{char } N(Q)\). \({\mathfrak C}_1= {\mathfrak C}_1(G)\) is the family of all max-cliques of \(G\). In the case of chordal graphs, \({\mathfrak C}_2\) is the family of minimal vertex separators, and \({\mathfrak C}_3= {\mathfrak C}_1=\varnothing\). The author investigates the so-called 2-ekachordal graph \(G\) which is an intersection graph of a family \(\{H_v\mid…
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1047087
zbMATH Keywords: characterization
zbMATH Keywords: neighborhood separator
zbMATH Keywords: intersection graph
zbMATH Keywords: chordal graph
zbMATH Keywords: clique intersection condition
zbMATH Keywords: clique cover condition
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Q4288578
cites work: Q3328583
cites work: Representation of smooth surfaces by graphs. Transformations of graphs which do not change the Euler characteristic of graphs
cites work: Q4309133
cites work: Q4337344
cites work: Q4173395
cites work: The generating polynomial and Euler characteristic of intersection graphs
description: scientific article; zbMATH DE number 1047087