Edge clique graphs and some classes of chordal graphs

DOI10.1016/S0012-365X(00)00403-9MaRDI QIDQ5957745zbMATH OpenOpenAlexWikidataFDO

Authors Márcia R. Cerioli, Jayme L. Szwarcfiter

Publication date 17 November 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(00)00403-9

zbMATH Keywords

characterizations chordal graphs edge clique graph split graph starlike graph threshold graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Review text

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:NEWLINENEWLINENEWLINE(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]\).NEWLINENEWLINENEWLINELet \(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.NEWLINENEWLINENEWLINE(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.)NEWLINENEWLINENEWLINE(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.NEWLINENEWLINENEWLINEAlready 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.NEWLINENEWLINENEWLINEThe 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.

Recommendations

Cited in

(11)

This page was built for publication: Edge clique graphs and some classes of chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5957745)