scientific article; zbMATH DE number 1251573
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).
- k-Components, Clusters and Slicings in Graphs
- An inequality for the chromatic number of a graph
- An upper bound for the chromatic number of a graph and its application to timetabling problems
- Four classes of perfectly orderable graphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Polynomially solvable cases for the maximum stable set problem
- Smallest-last ordering and clustering and graph coloring algorithms
- New properties of perfectly orderable graphs and strongly perfect graphs
- Stable sets in two subclasses of banner-free graphs
- Minimum degree algorithms for stability number
- Extending the MAX algorithm for maximum independent set
- New sufficient conditions for \(\alpha\)-redundant vertices
- On sequential heuristic methods for the maximum independent set problem
- A note on -redundant vertices in graphs
- On vertex orderings and the stability number in triangle-free graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4229265)
