𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chessboard graphs, related designs, and domination parameters

✍ Scribed by Renu Laskar; Charles Wallis

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
162 KB
Volume
76
Category
Article
ISSN
0378-3758

No coin nor oath required. For personal study only.

✦ Synopsis

The graph-theoretic study of combinatorial chessboard problems can be extended to the study of line graphs of graphs of combinatorial designs. In particular, the determination of optimal placements of rooks on a chessboard corresponds to the determination of domination parameters of graphs of block designs. The determination of one such parameter, the independence number, is shown to follow directly from classical results in design theory. Additionally, the domination number of graphs of ΓΏnite projective planes is discussed.

πŸ“œ SIMILAR VOLUMES

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

Bounds related to domination in graphs w
Bounds related to domination in graphs with minimum degree two
✍ Sanchis, Laura A. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 157 KB πŸ‘ 2 views

A dominating set for a graph G = (V, E) is a subset of vertices V βŠ† V such that for all v ∈ V -V there exists some u ∈ V for which {v, u} ∈ E. The domination number of G is the size of its smallest dominating set(s). We show that for almost all connected graphs with minimum degree at least 2 and q e

On equality in an upper bound for domina
On equality in an upper bound for domination parameters of graphs
✍ Favaron, O.; Mynhardt, C. M. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 141 KB πŸ‘ 2 views

We consider the well-known upper bounds Β΅(G) ≀ |V (G)|-βˆ†(G), where βˆ†(G) denotes the maximum degree of G and Β΅(G) the irredundance, domination or independent domination numbers of G and give necessary and sufficient conditions for equality to hold in each case. We also describe specific classes of gr