z-logo
open-access-imgOpen Access
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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here