Gallai-type theorems and domination parameters (Q1356464)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Gallai-type theorems and domination parameters |
scientific article |
Statements
Gallai-type theorems and domination parameters (English)
0 references
7 October 1997
0 references
If \(\gamma(G)\) and \(\Delta(G)\) denote the domination number and maximum degree (respectively) of a graph \(G\) of order \(n\), then it is known that \(\gamma(G)\leq n-\Delta(G)\). Those connected bipartite graphs which achieve this bound are characterised, and two conditions are furnished in the general case which are necessary if \(\gamma(G)+ \Delta(G)=n\), and sufficient to achieve \(n-1\leq \gamma(G)+ \Delta(G)\leq n\). Similar relations are investigated for the independent domination number, irredundance number, and upper irredundance number.
0 references
domination number
0 references
irredundance
0 references