No label defined (Q4229265)

The graphs \(G\) considered are finite and simple. A set \(S\) of pairwise nonadjacent vertices in a graph is called a stable set and the problem of finding a maximum set \(S\) in \(G\) (stability) is discussed. For a given ordering \(v_1,\dots,v_n\) of the vertices of \(G\) such a set \(S\) can be found by a here described greedy algorithm and an ordering is called \(\alpha\)-ordering if this greedy algorithm yields a maximum stable set from \(v_1,\dots,v_n\). The problem of finding an \(\alpha\)-ordering in an arbitrary graph is NP-hard in general, but it is also possible to compute \(\alpha\)-orderings in polynomial time for some special classes of graphs. Special vertex orderings can be studied and classes of graphs can be characterized for which those orderings are \(\alpha\)-orderings. In the present paper, in five different cases conditions on vertex orderings are imposed and it is investigated when an ordering satisfying each of these conditions is an \(\alpha\)-ordering. For example, three of these orderings satisfying some conditions are given here: (1) The ordering when restricted to each induced subgraph remains an \(\alpha\)-ordering (Condition 1). (2) The ordering \(v_1,\dots, v_n\) such that \(i< j\) only if \(\text{deg}(v_i)\leq \text{deg}(v_j)\) holds for the degrees (Condition 2). (3) For every induced subgraph \(H\) of \(G\), every ordering satisfying Condition 2 is an \(\alpha\)-ordering (Condition 4). For these examples, the authors get the following results: (i) Condition 1 holds only for triangulated graphs. Their vertices can be ordered \(v_1,\dots, v_n\) such that, for each \(i\), vertex \(v_i\) is simplicial in the graph induced by \(\{v_i,\dots, v_n\}\); \(v_i\) is called simplicial vertex if the graph induced by its neighbors is a complete graph (Theorem 2.1). (ii) The problem of determining if, for a given graph, every ordering satisfying Condition 2 is an \(\alpha\)-ordering is co-NP-hard (Theorem 2.2). (iii) A graph \(G\) satisfies Condition 4 iff it contains as induced subgraph none of six subgraphs given by a figure (Theorem 3.1). From the extensive proof of Theorem 3.1, the authors also obtain (by their forbidden graph characterizations) the two previously known results that the stability number for the class of graphs characterized by the above-mentioned forbidden induced subgraphs can be obtained in polynomial time (Theorems 3.2 and 3.3).