IJPAM: Volume 77, No. 2 (2012)
Zhejiang Industry Polytechnic College
Shaoxing, 312000, P.R. CHINA
Abstract. A negative function of a graph is
a function
such that for every vertex
, the sum of the values of
over the closed neighborhood of
is at most
. A negative function
is maximal if there does
not exist a negative function
,
, for which
for every
. The weight of a negative function is
. The lower against number
of
is the minimum weight of a maximal
negative function on
. In this paper we establish a sharp lower
bound on
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