Clique neighborhoods and nearly chordal graphs (Q1363699)

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 v\) a vertex of \(G\}\) of induced subgraphs of a host \(K_4\)-free chordal graph \(H\) such that a given clique intersection condition and a given clique cover condition hold. Section 2 shows that \({\mathfrak C}_2\) and \({\mathfrak C}_3\) play an important role for these graphs, and in Theorems 1 and 2 the meaning of \({\mathfrak C}_2\) and \({\mathfrak C}_3\) for 2-ekachordal graphs \(G\) is described. It is also shown that for such graphs \(G\) we have: (a) \(\text{char }G= \text{comp }G\) (Theorem 3), and (b) \(c_1(G)- c_2(G)+ c_3(G)=\text{comp }G\) with \(c_i=|{\mathfrak C}_i(G)|\) for \(1\leq i\leq 3\) (Theorem 4). In Section 3, the role of \({\mathfrak C}_1\), \({\mathfrak C}_2\) and \({\mathfrak C}_3\) for general graphs \(G\) is investigated. The author gets the following results: (a) Every graph \(G\) satisfies \(c_1(G)- c_2(G)\leq\text{comp } G\), with equality iff \(G\) is chordal (Theorem 5). (b) Every graph \(G\) satisfies \(\text{char }G\leq c_2(G)- c_2(G)+ c_3(G)\) (Theorem 6). (c) A necessary and sufficient condition for the equality in Theorem 6 is given (Theorem 7). From this follows that the equality holds for (at least) all 2-ekachordal graphs, all \(K_4\)-free graphs, and all planar graphs (Corollary 2).