Characterization of \(Z_m\)-well-covered graphs for some classes of graphs (Q5936038)

A graph be denoted by \(G=(V,E)\). From the neighbourhood \(N(v)\) in \(G\) of \(v\in V\) there follows \(N[v]=N(v) \cup\{v\}\). A set \(I\subseteq V\) is called independent if no two vertices of \(I\) are adjacent. A graph \(G\) is well covered if all maximal independent sets of \(G\) have the same cardinality, especially is \(G Z_m\)-well-covered if \(|I_1|\equiv|I_2|\pmod m\) for all maximal independent sets \(I_1\) and \(I_2\) in \(V\). A vertex \(v\) is simplicial if it appears in exactly one clique of the graph \(G\), and a clique containing at least one such simplicial vertex of \(G\) is called a simplex of \(G\). \(G\) is a called a simplicial graph if every vertex of \(G\) is a simplicial vertex or is adjacent to a simplicial vertex of \(G\). \(G\) is called a chordal graph if every cycle of \(G\) of length four or more has a chord, and \(G\) is called a circular arc graph if it is the intersection graph of arcs on a circle.NEWLINENEWLINENEWLINEIn present paper \(Z_m\)-well-covered graphs are characterized in these three classes by the following four theorems. Theorem 1. If for each \(g\in V(G)\) there is \(\ell\in N\) such that \(g\) belongs to exactly \((m\ell+1)\) simplices, then \(G\) is a \(Z_m\)-well-covered graph. Theorem 2. If \(G\) is a \(Z_m\)-well-covered simplicial graph, then for each \(g\in V(G)\) there is \(\ell\in N\) such that \(g\) belongs to exactly \((m\ell+1)\) simplices. Theorem 3. \(G\) is a simplicial graph, if \(G\) is a chordal \(Z_m\)-well-covered graph. Theorem 4. Let \(G\) be a circular arc graph that is not complete. Then \(G\setminus N[v]\) is a \(Z_m\)-well-covered graph for all \(v\in V(G)\) if and only if \(G\) is a \(Z_m\)-well-covered graph.NEWLINENEWLINENEWLINEIt is known that the recognition problem of well-covered graphs (and of \(Z_m\)-well-covered graphs) in general is Co-NP-complete, but for some classes of graphs it is already polynomial (examples are given in the paper).