
Voting 'Against' in regular and nearly regular graphs
Author(s) -
Changping Wang
Publication year - 2010
Publication title -
applicable analysis and discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.69
H-Index - 26
eISSN - 2406-100X
pISSN - 1452-8630
DOI - 10.2298/aadm100213014w
Subject(s) - mathematics , combinatorics , graph , discrete mathematics , strongly regular graph , pathwidth , line graph
Let $G=(V, E)$ be a graph. A function $f: V(G)o {-1,1}$ is called emph{negative}if ule{-2mm}{0mm}$sumlimits_{vin N[v]}ule{-2mm}{0mm} f(v) le 1$ for every $vin V(G).$A negative function $f$ of a graph $G$ is maximal if there exists no negative function $g$ suchthat $g eq f$ and $g(v)ge f(v)$ for every $vin V.$ The minimum of the values of$sumlimits_{vin V}ule{-1mm}{0mm} f(v),$ taken over all maximal negative functions$f,$ is called the emph{lower against number} and is denoted by $eta_{mathbb{N}}^*(G).$In this paper, we present lower bounds on this number for regular graphs and nearly regulargraphs, and we characterize the graphs attaining those bounds