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