Can I read Lower Bound on the Minus-domination Number on EtoBox?
Lower Bound on the Minus-domination Number by Jiřı́ Matoušek is a Computer Science article available to read on EtoBox.
What is Lower Bound on the Minus-domination Number about?
For a graph G, a function f : V (G) → {-1; 0; +1} is called a minus-dominating function of G if the closed neighborhood of each vertex of G contains strictly more 1's than -1's. The minus-domination number -(G) of G, as deÿned by Henning and Slater, is the minimum, over all minus-dominating functions f of G, of v∈V (G) f(v). As observed by F uredi and Mubayi, a well-known probabilistic bound for the size of a transversal of a set system implies that -(G) = O((n=r) log r) for any graph G on n vertices of minimum degree r. We prove that there exist r-regular multigraphs G on n vertices, in which each vertex has at least r=2 distinct neighbors, and such that -(G)¿c(n=r) log r for some constant c ¿ 0. (For a multigraph, the closed neighborhood of a vertex is considered as a multiset in the deÿnition of a minus-dominating function.
Who reads Lower Bound on the Minus-domination Number?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Jiřı́ Matoušek
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0012-365X)
- Published
- 2001
- Language
- EN
- Field
- Computer Science (Physical Sciences)