IJPAM: Volume 77, No. 2 (2012)

LOWER AGAINST NUMBER IN GRAPHS

Weiliang Zhao
Zhejiang Industry Polytechnic College
Shaoxing, 312000, P.R. CHINA


Abstract. A negative function of a graph $G=(V,E)$ is a function $f: V\rightarrow\{-1, +1\}$ such that for every vertex $v$, the sum of the values of $f$ over the closed neighborhood of $v$ is at most $1$. A negative function $f$ is maximal if there does not exist a negative function $g$, $f\neq g$, for which $g(v)\geq f(v)$ for every $v\in V$. The weight of a negative function is $w(f)=\sum _{v\in V(G)}f(v)$. The lower against number $\beta_{N}^{*}(G)$ of $G$ is the minimum weight of a maximal negative function on $G$. In this paper we establish a sharp lower bound on $\beta_{N}^{*}(G)$ for general graphs. Our result generalizes previous results for regular graphs and nearly regular graphs with minimum degree being even.

Received: August 17, 2011

AMS Subject Classification: 05C69

Key Words and Phrases: lower bounds, negative function, lower against number

Download paper from here.


Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2012
Volume: 77
Issue: 2