On a relationship between Hadwiger and stability numbers (Q1092928)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a relationship between Hadwiger and stability numbers |
scientific article |
Statements
On a relationship between Hadwiger and stability numbers (English)
0 references
1987
0 references
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.
0 references
Hadwiger number
0 references
stability number
0 references