zbMATH — the first resource for mathematics

Signed domination of graphs and \((0,1)\)-matrices. (English) Zbl 1232.05157
Brualdi, Richard A. (ed.) et al., Combinatorics and graphs. Selected papers based on the presentations at the 20th anniversary conference of IPM on combinatorics, Tehran, Iran, May 15–21, 2009. Dedicated to Reza Khosrovshahi on the occasion of his 70th birthday. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4865-4/pbk). Contemporary Mathematics 531, 19-42 (2010).
Summary: We briefly review known results about the signed edge domination number of graphs. In the case of bipartite graphs, the signed edge domination number can be viewed in terms of its bi-adjacency matrix. This motivates the introduction of the signed domination number of a \((0,1)\)-matrix. We investigate the signed domination number for various classes of \((0,1)\)-matrices, in particular for regular and semi-regular matrices.
A conjectured upper bound for the signed edge domination of a graph of order \(n\) leads to the conjecture that the signed domination number of an \(m\) by \(n\) \((0,1)\)-matrix is bounded above by \(m+n- 1\), and this conjecture is the focus of much of our work. We also determine a lower bound on the signed edge domination number of regular graphs and characterize the case of equality.
For the entire collection see [Zbl 1202.05003].

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C22 Signed and weighted graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)