𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Lower bounds on the minus domination and k-subdomination numbers

✍ Scribed by Liying Kang; Hong Qiao; Erfang Shan; Dingzhu Du

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
118 KB
Volume
296
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

A three-valued function f deΓΏned on the vertex set of a graph G = (V; E), f : V β†’ {-1; 0; 1} is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. That is, for every

consists of v and all vertices adjacent to v. The weight of a minus function is f(V ) = v∈V f(v). The minus domination number of a graph G, denoted by -(G), equals the minimum weight of a minus dominating function of G. In this paper, sharp lower bounds on minus domination of a bipartite graph are given. Thus, we prove a conjecture proposed by Dunbar et al. (Discrete Math. 199 (1999) 35), and we give a lower bound on ks (G) of a graph G.

πŸ“œ SIMILAR VOLUMES

Further results on the lower bounds of m
Further results on the lower bounds of mean color numbers
✍ F. M. Dong πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 181 KB πŸ‘ 1 views

Let G be a graph with n vertices. The mean color number of G, denoted by (G), is the average number of colors used in all n-colorings of G. This paper proves that (G) ! (Q), where Q is any 2-tree with n vertices and G is any graph whose vertex set has an ordering x 1 ,x 2 , . . . ,x n such that x i

A lower bound on the number of spanning
A lower bound on the number of spanning trees with k end-vertices
✍ Katherine Heinrich; Guizhen Liu πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 286 KB πŸ‘ 1 views

If a graph G with cycle rank p contains both spanning trees with rn and with n end-vertices, rn < n, then G has at least 2p spanning trees with k end-vertices for each integer k, rn < k < n. Moreover, the lower bound of 2p is best possible. [ l ] and Schuster [4] independently proved that such span

A constructive approach for the lower bo
A constructive approach for the lower bounds on the Ramsey numbers R (s, t)
✍ Xu Xiaodong; Xie Zheng; StanisΕ‚aw P. Radziszowski πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 89 KB πŸ‘ 1 views

## Abstract Graph __G__ is a (__k__, __p__)‐graph if __G__ does not contain a complete graph on __k__ vertices __K__~__k__~, nor an independent set of order __p__. Given a (__k__, __p__)‐graph __G__ and a (__k__, __q__)‐graph __H__, such that __G__ and __H__ contain an induced subgraph isomorphic t