Count internal stability number

The set SMX is called internally stable in the graph ( X, Γ ) if no two of its vertices are adjacent. Number a (G) = called the number of internal stability.

Pic.10

For example, for a symmetric graph in Fig.10, one can construct several maximal internally stable sets (for example, {X ₀ X ₅ X ₆ X ₈ }) and a (G) = 4.

Examples of his search are the problem of placing 8 queens on a chessboard (a symmetric graph with 64 vertices; 92 solutions - 76 were found by Gauss) (Fig. 11) - a problem of 15 girls who can be taken for a walk in threes where each pair does not fall more than once, - a (G) = 35 with C ³ ₁₅ = 455 triples

It can be shown that a (G) × g (G) i | X |; a (GґH) i a (G) × a (H) .

Figure 11	Fig.12

The apparatus of internal stability, in particular, is used in solving the problem of noise-free signal transmission (the Shannon problem on the information capacity of multiple signals [1]).