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
1995808019 70941519 2052665499 1993437988
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). A set L@?V(G) of a graph G=(V,E) is a liar's dominating set if (1) for all v@?V(G), |N"G[v]@?L|>=2 and (2) for every pair u,v@?V(G) of distinct vertices, |(N"G[u]@?N"G[v])@?L|>=3. A graph G=(V,E) admits a liar's dominating set if each of its connected component has at least three vertices. Given a graph G=(V,E) and an integer K, the liar's domination decision problem (LR-DOMDP) is to decide whether G has a liar's dominating set of cardinality at most K. Slater [P.J. Slater, Liar's Domination, Networks, 54(2) (2009) 70-74] proved that the LR-DOMDP is NP-complete for general graphs. Subsequently, Roden and Slater [M.L. Roden and P.J. Slater, Liar's domination in graphs, Discrete Math., 309(19) (2009) 5884-5890] showed a more general family of problems to each be NP-complete for bipartite graphs. Besides this result, no other algorithmic result for the liar's dominating set problem is available in the literature. In this paper, we first strengthen the complexity result of the LR-DOMDP by showing that this problem remains NP-complete for split graphs and hence for chordal graphs. Finally, we propose a linear time algorithm for computing a minimum cardinality liar's dominating set in a tree. Let G=(V,E) be a graph without isolated vertices and having at least 3 vertices. A set L@?V(G) is a liar@?s dominating set if (1) |N"G[v]@?L|>=2 for all v@?V(G), and (2) |(N"G[u]@?N"G[v])@?L|>=3 for every pair u,v@?V(G) of distinct vertices in G, where N"G[x]= y@?V|xy@?E @? x is the closed neighborhood of x in G. Given a graph G and a positive integer k, the liar@?s domination problem is to check whether G has a liar@?s dominating set of size at most k. The liar@?s domination problem is known to be NP-complete for general graphs. In this paper, we propose a linear time algorithm for computing a minimum cardinality liar@?s dominating set in a proper interval graph. We also strengthen the NP-completeness result of liar@?s domination problem for general graphs by proving that the problem remains NP-complete even for undirected path graphs which is a super class of proper interval graphs.