On a relationship between Hadwiger and stability numbers
It was proved that the inequality \(\eta\) (G)(2\(\alpha\) (G)-1)\(\geq n(G)\) holds for any graph G, where \(\eta\) (G) is the Hadwiger number of G, \(\alpha\) (G) is the stability number of G, and n(G) is the number of vertices, and it was conjectured that the inequality \(\eta\) (G)\(\cdot \alpha (G)\geq n(G)\) holds for any graph G. In this note, the authors prove that the equality holds in the first inequality if and only if G is a complete graph, and that the second inequality holds for any graph if and only if the inequality \(\eta\) (G)\(\cdot \alpha (G)\geq n(G)-C\) holds for any graph G and any given constant C. Two new parameters related to it are also defined and discussed.
scientific article; zbMATH DE number 4021192