Characterization of \(Z_m\)-well-covered graphs for some classes of graphs (Q5936038): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q126648983 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(00)00247-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2037821860 / rank | |||
Normal rank |
Latest revision as of 11:25, 30 July 2024
scientific article; zbMATH DE number 1612898
Language | Label | Description | Also known as |
---|---|---|---|
English | Characterization of \(Z_m\)-well-covered graphs for some classes of graphs |
scientific article; zbMATH DE number 1612898 |
Statements
Characterization of \(Z_m\)-well-covered graphs for some classes of graphs (English)
0 references
30 June 2002
0 references
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. In 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. It 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).
0 references
simplicial graph
0 references
chordal graph
0 references
circular arc graph
0 references