Edge clique graphs and some classes of chordal graphs (Q5957745)

Let \(G= (V,E)\) be an undirected graph. The edge clique graph \(K_e(G)\) of \(G\) is the graph whose vertices are the edges of \(G\), two vertices being adjacent in \(K_e(G)\) when the corresponding edges of \(G\) belong to the same clique (\(S\subseteq V(G)\) is a clique when \(S\) induces a complete subgraph in \(G\)). In the present paper, characterizations relative to edge clique graphs and to the following subclasses of chordal graphs are described and so the authors show which of these graphs are edge clique graphs: (1) \(G\) is a starlike graph when there exists a partition \(C,D_1,\dots, D_s\) of its vertices, such that \(C\) is a maximal clique and, for all \(u\in D_i\), \(v\in D_j\), \(i\neq j\), \(uv\not\in E(G)\), while if \(i=j\), \(N[u]= N[v]\). Let \(G_1,\dots, G_t\), \(t\geq 1\), be the so-called edge components of \(G\) which are maximal subgraphs with certain properties (definition is given in the paper). Then \(G\) is called a generalized starlike graph when one of the components is starlike, while the others are complete subgraphs. (2) A starlike-threshold graph \(G\) is a starlike graph admitting an ordering of its maximal cliques \(C,C_1,\dots, C_s\), such that \(C\cap C_i\subseteq C\cap C_{i+1}\). (In an analogous manner one gets the concept of generalized starlike-threshold graph.) (3) A split graph \(G\) is one whose vertices can be partitioned into a clique and an independent set. And \(G\) is a generalized split graph when one of the edge components \(G_i\) is split, while all the others consist of a single edge. Already known is the following necessary condition for a graph \(H\) to be the edge clique graph \(K_e(G)\) of some graph \(G\): All its maximal cliques and intersections of maximal cliques ought to be triangular. The authors get the following results: (a) The necessary condition given above is also sufficient for starlike-threshold graphs (Theorem 4). (b) Let \(H= K_e(G)\). Then \(G\) is a generalized (i) starlike graph iff \(H\) is a starlike graph (Theorem 2); (ii) starlike-threshold graph iff \(H\) is a starlike-threshold graph (Theorem 3); (iii) split graph iff \(H\) is a singular starlike graph (Theorem 5); (iv) threshold graph iff \(H\) is a singular starlike-threshold graph (Theorem 7, which is a consequence of the theorems above). (c) Finally, in Theorem 6 its proved which split graphs \(H\) are edge clique graphs: \(H\) is an edge clique graph iff it consists of a triangular clique, together with zero or more additional isolated vertices.