We commence the study of domination in the incidence graphs of combinatorial designs. Let @math be a combinatorial design and denote by @math the domination number of the incidence (Levy) graph of @math . We obtain a number of results about the domination numbers of various kinds of designs. For instance, a finite projective plane of order @math , which is a symmetric @math -design, has @math . We also show that for any symmetric @math -design it holds that @math . We study at depth the domination numbers of Steiner systems and in particular of Steiner triple systems. We show that a @math has @math and also obtain a number of upper bounds. The tantalizing conjecture that all Steiner triple systems on @math vertices have the same domination number is proposed and is verified up to @math . The structure of minimal dominating sets is also investigated, both for its own sake and as a tool in deriving lower bounds on @math . Finally, a number of open questions are proposed.
Laskar and Wallis in @cite_8 have obtained some results about the domination number of the line graph of @math , motivated by combinatorial chessboard problems. However, the domination number of @math itself was not considered by them. The recent thesis of H ' e ger @cite_4 is probably closeset in spirit to the present work: H ' e ger constructs dominating sets of a particular form in projective planes.
@cite_4 @cite_8
2064550979 1995808019
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 finite projective planes is discussed. Introduction (S.T. Hedetniemi, R.C. Laskar). Theoretical. Chessboard Domination Problems (E.J. Cockayne). On the Queen Domination Problem (C.M. Grinstead, B. Hahne, D. Van Stone). Recent Problems and Results About Kernels in Directed Graphs (C. Berge, P. Duchet). Critical Concepts in Domination (D.P. Summer). The Bondage Number of a Graph (J.F. ). Chordal Graphs and Upper Irredundance, Upper Domination and Independence (M.S. Jacobson and K. Peters). Regular Totally Domatically Full Graphs (B. Zelinka). Domatically Critical and Domatically Full Graphs (D. Rall). On Generalised Minimal Domination Parameters for Paths (B. Bollobas, E.J. Cockayne, C.M. Mynhardt). New Models. Dominating Cliques in Graphs (M.B. Cozzens, L.L. Kelleher). Covering all Cliques of Graph (Z. Tuza). Factor Domination in Graphs (R.C. Brigham, R. Dutton). The Least Point Covering and Domination Numbers of a Graph (E. Sampathkumar). Algorithmic. Dominating Sets in Perfect Graphs (D.G. Corneil, L.K. Stewart). Unit Disk Graphs (B.N. Clark, C.J. Colbourn, D.S. Johnson). Permutation Graphs: Connected Domination and Steiner Trees (C.J. Colbourn, L.K. Stewart). The Discipline Number of a Graph (V. Chvatal, W.J. Cook). Best Location of Service Centers in a Tree-Like Network under Budget Constraints (J. McHugh, Y. Perl). Dominating Cycles in Halin Graphs (M. Skowronska, M.M. Syslo). Finding Dominating Cliques Efficiently, in Strongly Chordal Graphs and Undirected Path Graphs (D. Kratsch). On Minimum Dominating Sets with Minimum Intersection (D.L. Grinstead, P.J. Slater). Bibliography. Bibliography on Domination in Graphs and Some Basic Definitions of Domination Parameters (S.T. Hedetniemi, R.C. Laskar). Let @math be a 3-uniform hypergraph of order @math and size @math , and let @math be a subset of vertices of @math . The set @math is a strong transversal in @math if @math contains at least two vertices from every edge of @math . The strong transversal number @math of @math is the minimum size of a strong transversal in @math . We show that @math , and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph @math of order @math and size @math that achieves equality in this bound. A set @math of vertices in a graph @math is a double total dominating set of @math if every vertex of @math is adjacent to at least two vertices in @math . The minimum cardinality of a double total dominating set of @math is the double total domination number @math of @math . Let @math be a connected graph of order @math with minimum degree at least three. As an application of our hypergraph results, we show that @math with equality if and only if @math is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if @math is not the Heawood graph, we show that @math , while if @math is a cubic graph different from the Heawood graph, we show that @math , and this bound is sharp. A set @math is weakly convex in @math if for any two vertices @math there exists an @math --geodesic such that all of its vertices belong to @math . A set @math is a weakly convex dominating set if @math is weakly convex and dominating. The weakly convex domination number @math of a graph @math equals the minimum cardinality of a weakly convex dominating set in @math . The weakly convex domination subdivision number sd @math is the minimum number of edges that must be subdivided (each edge in @math can be subdivided at most once) in order to increase the weakly convex domination number. In this paper we initiate the study of weakly convex domination subdivision number and we establish upper bounds for it.