๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Domination and irredundance in the queens' graph

โœ Scribed by A.P Burger; E.J Cockayne; C.M Mynhardt

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
1020 KB
Volume
163
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

The vertices of the queem;' graph {~, are the squares of an n ร— n chessboard and two squares are adjacent ifa queen placed on one covers the other. It is shown that the domination num;~'r of Q. is at most 31n/54 + O(1), that Q. possesses minimal dominating sets of cardina~tty 5n/2 -O(l) and that the cardinality of any irredundant set of vertices of Q, (n/> 9) is at most L6n +6-8x/n + ~ +1].

๐Ÿ“œ SIMILAR VOLUMES

Stability, domination and irredundance i
Stability, domination and irredundance in a graph
โœ Odile Favaron ๐Ÿ“‚ Article ๐Ÿ“… 1986 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 441 KB

In a graph G, a set X is called a stable set if any two vertices of X are nonadjacent. A set X is called a dominating set if every vertex of V-X is joined to at least one vertex of X. A set Xis called an irredundant set if every vertex of X, not isolated in X, has at least one proper neighbor, that

Graph-theoretic parameters concerning do
Graph-theoretic parameters concerning domination, independence, and irredundance
โœ B. Bollobรกs; E. J. Cockayne ๐Ÿ“‚ Article ๐Ÿ“… 1979 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 402 KB

## Abstract A vertex __x__ in a subset __X__ of vertices of an undericted graph is __redundant__ if its closed neighbourhood is contained in the union of closed neighborhoods of vertices of __X__ โ€“ {__x__}. In the context of a communications network, this means that any vertex that may receive comm

Chordal graphs and upper irredundance, u
Chordal graphs and upper irredundance, upper domination and independence
โœ Michael S. Jacobson; Ken Peters ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 648 KB

In this paper we consider the following parameters: IR(G), the upper irredundance number, which is the order of the largest maximal irredundant set, I'(G), the upper domination number, which is the order of the largest minimal dominating set and /3(G), the independence number, which is the order of

The sequence of upper and lower dominati
The sequence of upper and lower domination, independence and irredundance numbers of a graph
โœ E.J. Cockayne; C.M. Mynhardt ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 803 KB

Necessary and sufficient conditions are established for the existence of a graph whose upper and lower domination, independence and irredundance numbers are six given positive integers. This result shows that the only relationships between these six parameters which hold for all graphs and which do

The ratio of the irredundance number and
The ratio of the irredundance number and the domination number for block-cactus graphs
โœ Zverovich, V. E. ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 96 KB ๐Ÿ‘ 2 views

Let ฮณ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43-56] and Bollobรกs and Cock- ayne [J. Graph Theory (1979) 241-249] proved independently that ฮณ(G) < 2ir(G) for