The external stability number of the graph

The set TMX is called externally stable in the graph ( X, Γ ) if for each vertex of xpt there exists at least one image in the set T. The number b (G) = called the number of external stability.

Examples: how many queens can be put (fig.12) or other figures, so that all the board fields are under attack (5 queens, 8 rooks or elephants, 12 horses), how many observers to put at the intersections of streets, so that all crossroads are supervised.

There is a fairly simple algorithm for finding the minimum externally stable set. For the graph G = (X, D) (see Fig. 13a), we construct the graph ( X, , D ), where the mapping D of the set X to so that if y = x or y is a prototype of x (yql ^-1 x) (fig. 13b).

Next steps:

1. remove from ( x, , D ) vertices of x such that Dx M Dу for y№x (here we remove c, d, f ) and edges outgoing from them;
2. if there is a "hanging edge" ( x, ), include x in the sought-for set T and delete this vertex and its images (here a and FROM a and D are excluded from the graph, and Dа = { };
   
   Fig. 13
3. repeat the preceding paragraphs until the impossibility of further reduction is found;
4. one of the remaining vertices (for example, b ) is included in the set T and we exclude its images Db = { };
5. repeat the preceding paragraphs and get either T = ( a, b, e ) or T = ( a, b, g ).

Let be - some graph. Subset of vertices called a set of external stability if
one)
2)

The power of the minimal set of external stability is called the number of external stability of the graph. . In order to find all the sets of external stability of the graph, it is necessary to find all the covers of the modified graph adjacency matrix. The modification is to add a single main diagonal.

Example

External stability sets: