Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 127–145
Consensus strategies for signed
profiles on graphs
Kannan Balakrishnan
Department of Computer Applications, Cochin University of Science and Technology
Cochin – 682 022, India
Manoj Changat ∗
Department of Futures Studies, University of Kerala, Trivandrum – 695 034, India
Henry Martyn Mulder †
Econometrisch Instituut, Erasmus Universiteit
P. O. Box 1738, 3000 DR Rotterdam, Netherlands
Ajitha R. Subhamathi
Department of Computer Applications, N.S.S. College, Rajakumari, Idukki, Kerala, India
Received 18 October 2011, accepted 28 March 2012, published online 15 June 2012
Abstract
The median problem is a classical problem in Location Theory: one searches for a
location that minimizes the average distance to the sites of the clients. This is for desired
facilities as a distribution center for a set of warehouses. More recently, for obnoxious
facilities, the antimedian was studied. Here one maximizes the average distance to the
clients. In this paper the mixed case is studied. Clients are represented by a profile, which
is a sequence of vertices with repetitions allowed. In a signed profile each element is
provided with a sign from {+,−}. Thus one can take into account whether the client
prefers the facility (with a + sign) or rejects it (with a − sign). The graphs for which all
median sets, or all antimedian sets, are connected are characterized. Various consensus
strategies for signed profiles are studied, amongst which Majority, Plurality and Scarcity.
Hypercubes are the only graphs on which Majority produces the median set for all signed
profiles. Finally, the antimedian sets are found by the Scarcity Strategy on e.g. Hamming
graphs, Johnson graphs and halfcubes.
Keywords: Plurality strategy, median, majority rule, Hamming graph, Johnson graph, halfcube.
Math. Subj. Class.: 05C99, 05C12, 90B80
∗Research work is supported by NBHM/DAE under grant No.2/48(2)/2010/NBHM-R & D
†Research work was carried out when this author visited University of Kerala, under the Erudite Scheme of
the Government of Kerala, January 3–16, 2011
E-mail addresses: bkannan@cusat.ac.in (Kannan Balakrishnan), mchangat@gmail.com (Manoj Changat),
hmmulder@few.eur.nl (Henry Martyn Mulder), ar.subhamathi@gmail.com (Ajitha R. Subhamathi)
Copyright c© 2013 DMFA Slovenije
128 Ars Math. Contemp. 6 (2013) 127–145
1 Introduction
Most of the facility location problems in the literature are concerned with finding locations
for desirable facilities. The goal there is to minimize a distance function between facil-
ities and the demand sites (clients). One way to model this is using a network, see for
instance [23, 24, 17]. In the discrete case one uses graphs, and clients and facilities are to
be positioned on vertices.
One may formulate such location problems also in terms of achieving a consensus
amongst the clients. Thus it becomes a problem in Consensus Theory. This approach
has been fruitful in many other applications, e.g. in social choice theory, clustering, and
mathematical biology, see for instance [7, 16, 15, 22].
From the view point of median consensus the classical result of Goldman [12] is very
interesting: to find the median in a tree, just move to the majority of the clients. In [20], this
majority strategy was formulated for arbitrary graphs. It was proved that majority strategy
finds all medians for any set of clients if and only if the graph is a so-called median graph.
Clients are termed as profiles in the language of graph theory, defined as a sequence of
vertices in which vertices are allowed to repeat.
The class of median graphs comprises that of the trees as well as that of the hypercubes
and grids. It allows a rich structure theory [18, 13, 21] and has many and diverse applica-
tions, see, for. e.g., [14], for median type consensus. In the majority strategy we compare
the two ends of an edge v and w: if we are at v and at least half of the clients are strictly
nearer to w than to v, then we move to w. One could relax the requirement for making a
move as follows: one may move to w if there are at least as many clients closer to w than
to v. Note that in the latter case less than half may actually be closer to w because there are
many clients having equal distance to v andw. This idea of relaxing the majority strategy is
formalized as plurality strategy in [4]. Other consensus strategies known as Condorcet, hill
climbing and Steepest ascent hill climbing strategies were also proposed in [4]. There it is
proved that the plurality, hill climbing and steepest ascent hill climbing strategies starting
at an arbitrary vertex for arbitrary profiles will always return the median set of the profile
if and only if the graph has connected medians.
However just as important are the problems dealing with the location of undesirable or
obnoxious facilities, such as nuclear reactors, garbage dumps or water purification plants,
see [9, 10, 11]. Here the criterion for optimality is maximizing the sum of the distances
from the location of the obnoxious facility to the locations of the clients. The problem is
known as the antimedian problem.
In general any two subgraphs may appear as antimedian and median sets, respectively,
for clients located at all vertices without repetitions, with the distance between them being
arbitrary, see for instance [2]. It is possible that facilities which are undesirable for some
clients may be desirable for some other clients. For example, assume the problem of locat-
ing a beer parlour in a human habitat area. Some of the inhabitants may consider it as a
desirable facility where as some others may consider it as undesirable facility. One way to
formulate such problem is to associate a sign with the clients indicating whether the facility
is desirable or undesirable to the client. In this paper we are concentrating on methods to
solve such problems. For this a more general concept called signed profiles is introduced
and is formally defined in the next section. In Section 3, the equivalence of rational weight
functions and signed profiles are established, and the relationship between the median and
antimedian sets for signed profiles is obtained. In Section 4, various consensus strategies
are formulated, amongst which Majority, Plurality and Scarcity strategy, and it is shown
K. Balakrishnan et al.: Consensus strategies for signed profiles on graphs 129
that all these consensus strategies are pairwise distinct for signed profiles, as it has already
been known for the usual profiles. We show that, for signed profiles, the hypercubes are the
only graphs on which Majority produces the median set for any signed profile in Section 5.
Finally, for Scarcity, we study various classes of graphs, on which this strategy produces
the antimedian set for any signed profile.
2 Preliminaries
Let G = (V,E) be a finite, connected, simple graph with vertex set V and edge set E. The
distance function of G is denoted by d, where d(u, v) is the length of a shortest u, v-path.
We call a subset W of V connected if it induces a connected subgraph in G. The interval
I(u, v) between two vertices u and v consists of all vertices on shortest u, v-paths, that is:
I(u, v) = {x | d(u, x) + d(x, v) = d(u, v)}.
A profile on G is a finite sequence π = (x1, x2, . . . , xk) of vertices of G. The length of π
is the number k = |π|. Note that, π being a sequence, multiple occurrences are allowed.
In this paper we extend the concept of profile: a signed profile is a profile where a sign
from {+,−} is added to each element. We write the sign of element xi as si. Thus a
signed profile is a sequence π = (s1x1, s2x2, . . . , skxk). We call xi an element of π and
si its sign. Note that with this usage, a vertex occurring k times in a profile occurs as k
different elements in a profile. For an element x of π we denote its sign also by sx. For
computational reasons, we identify a sign s also with the number s1 = +1 or −1, and talk
about +1 or −1 as a sign. Thus we can take the sum of signs. As we will see below, a
signed profile with all signs being +1, plays the role of the usual profile without signs. We
call such a profile a positive profile. If all signs are −1, then the profile is negative. Since
all our profiles are signed, we call a signed profile just a profile, and omit the adjective
‘signed’, except in the statements of lemmas and theorems (to avoid confusion with similar
lemmas and theorems in the literature). A profile obtained from π by changing each si by
−si is denoted by −π. The size of a profile π is defined as
‖π‖ =
k∑
i=1
si.
So, for positive profiles we have ‖π‖ = |π|, and for negative profiles we have ‖π‖ = −|π|.
For an edge uv in G, we denote by πuv the subprofile of π consisting of the elements
of π strictly closer to u than to v, and by πvu the subprofile of all elements at equal distance
form u and v. Note that a profile, by definition, has a positive length. However, for sub-
profiles we allow the empty subprofile. For instance, a graph is bipartite if and only if the
subprofile πvu is empty for any edge uv and any profile π.
In the literature we find such concepts as remoteness, median and antimedian of positive
profiles, for e.g., see, [14] and [20]. These are all very natural and the definitions are in
accordance with our intuition. Because the definitions for signed profiles are basically the
same, we use the same terminology here.
The remoteness of a vertex v to a profile π is defined as
D(v, π) =
k∑
i=1
sid(xi, v).
130 Ars Math. Contemp. 6 (2013) 127–145
A permutation of the elements in a profile does not change remoteness. Because we are
only interested in the remoteness to profiles, we will consider two profiles as the same if
they can be obtained from each other by permuting the elements. We write the concatena-
tion of two profiles π and ρ as πρ. Thus, for any edge uv, we can write π = πuvπvuπvu.
A vertex minimizing D(v, π) is called a median of the profile. The set of all medians
of π is the median set of π and is denoted byM(π). A vertex maximizingD(v, π) is called
an antimedian of the profile. The set of all antimedians of π is the antimedian set of π and
is denoted by AM(π). The reader has to keep in mind that the effects of the signs might
just be contra-intuitive. For instance, if π is a negative profile, then a median of π is an
antimedian of the positive profile −π.
A vertex x such that D(x, π) ≤ D(y, π), for all neighbors y of x, is a local median
of π. The set of all local medians is denoted by Mloc(π). If D(x, π) ≥ D(y, π), for all
neighbors y of x, then x is a local antimedian of π. The set of all local antimedians is
denoted by AMloc(π).
Let π = (s1x1, s2x2, . . . , skxk) be a profile, then we have
D(v,−π) =
k∑
i=1
−sid(xi, v) = −
k∑
i=1
sid(xi, v) = −D(v, π).
From this observation we deduce that, by replacing a profile π by its opposite−π, the roles
of (local) medians and (local) antimedians are exchanged. So we have M(π) = AM(−π),
etcetera. We single out one fact that we need in the sequel.
When the profile is of the form (−x,+x) the median set is equal to the antimedian set
and is the entire vertex set of the graph. But this is not the only case when the median
and antimedian set are equal. For example, consider a positive profile π on a hypercube
containing each vertex once. In this case the remoteness is constant and hence the median
and antimedian set are the same and coincide with the entire vertex set of the graph. It can
also be noted that the situation is the same for−π. In general, for such positive and negative
profiles on so called distance balanced graphs both the median sets and antimedian sets
coincide. The case for such positive profiles on the class of distance balanced graphs is
proved in [5]. The same situation holds for some special even profiles (both positive and
negative) in some other class of graphs, see for instance [1].
Lemma 2.1. Let G be a connected graph and π a signed profile on G. Then, for any two
adjacent vertices u, v in G,
‖πuv‖ ≤ ‖πvu‖ if and only if D(u, π) ≥ D(v, π).
Proof. Since uv is an edge in G, we can ignore πvu in the following computation.
D(u, π)−D(v, π) =
=
∑
x∈πuv
sxd(u, x) +
∑
x∈πvu
sxd(u, x)−
∑
x∈πuv
sxd(v, x)−
∑
x∈πvu
sxd(v, x)
=
∑
x∈πuv
sxd(u, x) +
∑
x∈πvu
sxd(u, x)−
∑
x∈πuv
sx(d(u, x) + 1)−∑
x∈πvu
sx(d(u, x)− 1)
= ‖πvu‖ − ‖πuv‖.
K. Balakrishnan et al.: Consensus strategies for signed profiles on graphs 131
From this the assertion follows immediately.
3 Remoteness with respect to arbitrary weight functions
The concept of remoteness function and hence of medians and antimedians can also be
studied with respect to weight functions defined on the vertex set of a graph. This was
studied by Bandelt and Chepoi in [6] for non-negative weight functions in the case of
medians. The equivalence of non-negative weight functions and positive profiles and hence
the corresponding equivalence of the remoteness function and medians of non-negative
weight functions and positive profiles are established in [4].
In this section, we establish that the same conclusion follows for arbitrary weight func-
tions and signed profiles.
A weight function on G is a mapping f from V to the set of real numbers. Note that we
now allow negative weights. We say that f has a local minimum at x ∈ V if f(x) ≤ f(y),
for every y adjacent to x. It has a local maximum if f(x) ≥ f(y), for every y adjacent to
x. The remoteness function with respect to the weight function f is the function Df from
V to the set of real numbers defined as:
Df (v) = D(v, f) =
∑
x∈V
d(v, x)f(x).
Note that Df is a weight function on G as well. A local median of f is a vertex u such
that Df has a local minimum at u. A local antimedian is a vertex at which Df attains a
maximum. The set of all local medians of a weight function f is denoted by Mloc(f). The
set of all local antimedians is denoted by AMloc(f). A median of f is a vertex u such
that Df has a global minimum at u. Similarly, an antimedian of f is a vertex at which
Df attains a maximum. The median set M(f) of f is the set of all medians of f . The
antimedian set AM(f) of f is the set of all anti-medians of f .
Let f be a weight function on a graph G and let −f be the weight function defined in
the obvious way: its value at x is −f(x). Then clearly, we have D(v, f) = −D(v,−f),
for any vertex v in G. In the sequel we make use of the following obvious facts.
Remark 3.1. Let f be an arbitrary weight function defined on the vertex set of a graph
G. Then replacing f with −f interchanges the roles of local maxima (minima) of f with
local minima (maxima) of −f , and hence also interchanges the roles of both local and
global medians (antimedians) of f with local and global antimedians (medians) of −f ,
respectively.
Let π be a profile on G. Then the weight function associated with π is the function fπ
with fπ(x) =
∑
si, where the summation is taken over the occurrences of vertex x. If
x does not occur in π, then we set f(x) = 0. The following lemma follows immediately
from the definitions. Note that, for any integer-valued weight function f , there are infinitely
many profiles having f as their associated weight function.
Lemma 3.2. Let G be a connected graph, and let π be a signed profile with associ-
ated weight function fπ . Then D(v, π) = D(v, fπ), and hence M(fπ) = M(π), and
AM(fπ) = AM(π), and Mloc(fπ) = Mloc(π), and AMloc(fπ) = AMloc(π), for every v
in V .
Let f be a weight function on a connected graph G. For a positive real number t, we
define tf to be the weight function with (tf)(x) = t × f(x). Then we have M(tf) =
132 Ars Math. Contemp. 6 (2013) 127–145
M(f) and Mloc(tf) = Mloc(f). Also we have AM(tf) = AM(f) and AMloc(tf) =
AMloc(f). Finally, Dtf has a strict local minimum (maximum) at a vertex u if and only if
Df has a strict local minimum (maximum) at u. The following lemma is obvious.
Lemma 3.3. Let g be rational weight function on a connected graph G. Then there is a
signed profile π on G such that fπ = tg for some positive integer t.
In other words, antimedians (medians) of signed profiles are exactly antimedians (medi-
ans) of rational weight functions. The same holds for local antimedians (medians). Next
we show that real-valued weight functions may be replaced by rational-valued weight func-
tions, and thus by profiles, when one wants to compute antimedian (median) sets. We only
present the proofs for the antimedian case. This is the one that we need in Sections 4 and 5.
The case for the median sets is similar to that in [4], except that one has to take into account
the signs. The next two Lemma’s are the signed version of Lemma’s 5 and 6 in [4]. The
proofs are easy adaptations of those in [4]. Because they are short and prepare the way for
Proposition 3.6, we include the proofs of the signed versions.
Lemma 3.4. LetG be a connected graph, and let f be a weight function onG such thatDf
has a local maximum at vertex u, which is not a global maximum. Then there is a weight
function g such that Dg has a strict local maximum at u, which is not a global maximum.
Furthermore if f is rational, then g may also be taken as a rational function.
Proof. First note that, for any two vertices x and y, we have d(x, y) < n = |V |. Let
D(u, f) = 1. Let Df have a global maximum at z, that is, D(z, f) =  > 1. Let
2 = − 1. Now define the function g as follows.
g(v) =
{
f(v) if v 6= u
f(u)− 2n if v = u.
Then D(u, g) = D(u, f), because in these sums the values f(u) and g(u) of the functions
at u are multiplied by d(u, u) = 0. For any vertex v adjacent to u, we have
D(v, g) = D(v, f)− 2
n
< D(v, f) ≤ D(u, f) = D(u, g).
So Dg has a strict local maximum at u. Furthermore,
D(z, g) = D(z, f)− d(u, z)2
n
> D(z, f)− 2 = D(u, f) = D(u, g).
So g has a strict local maximum at u that is not a global maximum. Also if f is rational,
then 2 is rational. So g is also rational.
Lemma 3.5. Let G be a connected graph with the property that, for each rational weight
function g, every local maximum of Dg is also a global maximum. Then the same property
holds for any real-valued weight function f on G.
Proof. Assume that for some real-valued weight function f there is a local maximum for
Df , at some vertex u that is not a global maximum. In view of the preceding lemma, we
may assume that Df has a strict local maximum at u. Let Df have a global maximum at z,
and let
1 = min{D(u, f)−D(x, f) | x adjacent to u}, 2 = D(z, f)−D(u, f),
K. Balakrishnan et al.: Consensus strategies for signed profiles on graphs 133
 =
min(1, 2)
n2
.
Now choose a rational weight function g such that g(v) < f(v) and f(v) − g(v) < ,
for all v. Then, for any vertex x adjacent to u, we have D(u, g) > D(u, f) −  × n2 ≥
D(u, f)− 1 ≥ D(x, f) > D(x, g). So u is a local maximum for Dg . Moreover, we have
D(z, g) > D(z, f) −  × n2 ≥ D(z, f) − 2 ≥ D(u, f) > D(u, g). So u is not a global
maximum for Dg , which is a contradiction.
Graphs with connected median sets for non-negative weight functions were character-
ized in [6]. Using an analogous approach, we now are able to characterize graphs with
connected antimedian and median sets for arbitrary weight functions. Before stating the re-
sult, we define basic concepts used in the following lines. A subgraph G of a graph H is an
isometric subgraph if dG(u, v) = dH(u, v) for all vertices u, v in G. We call a subset S of
the vertex set ofG a level set with respect to an integer λ if S = {x ∈ V (G) : Df (x) ≥ λ}.
Proposition 3.6. For a graph G and any arbitrary weight function defined on the vertex
set of G the following conditions are equivalent
(i) AMloc(f) = AM(f) for all weight functions f ;
(ii) all level sets {x : Df (x) ≥ λ} induce isometric subgraphs;
(iii) all antimedian sets AM(f) induce isometric subgraphs;
(iv) all antimedian sets AM(f) are connected.
Proof. The implications (ii)⇒ (iii), (iii)⇒ (iv) are trivial.
Next we prove (iv) ⇒ (i). Let f be a weight function. Assume to the contrary that
there exists a local antimedian z of f that is not an antimedian. Let y be an antimedian.
Amongst such pairs y, z, we may choose y and z such that d(y, z) is as small as possible.
Our aim is to find two vertices u and v with d(u, v) = 2 and a weight function f ′ such that
AM(f ′) = {u, v}. So f ′ does not have a connected antimedian set.
Consider the interval I(y, z). Because of the minimality of d(y, z), we have Df (y) >
Df (x) for all x in I(y, z) distinct from y. Since z is a local antimedian, we have Df (z) ≥
Df (x), for any neighbor x of z, in particular for any neighbor x of z in I(y, z). This
implies that d(y, z) ≥ 2. Hence, going from y to z within I(y, z), we will encounter two
vertices u, v such that d(y, u) = d(y, v) − 2, d(z, u) = d(z, v) + 2, d(u, v) = 2, with the
properties that Df (u) > Df (x) and Df (v) ≥ Df (x), for any common neighbor x of u
and v. Note that these common neighbors of u and v are precisely the vertices in I(u, v)
distinct from u and v.
If there is any common neighbor x of u and v such that Df (v) = Df (x), then we have
Df (y) ≥ Df (u) > Df (v). If Df (v) > Df (x) for all common neighbors of u and v, then
we compare Df (u) and Df (v). If Df (u) ≥ Df (v), then again we have Df (y) > Df (v).
If Df (v) > Df (u), then we have Df (y) > Df (v) > Df (u). In this case we interchange
the names of u and v. In all cases we end up with two vertices u and v at distance 2 with
Df (y) ≥ Df (u) ≥ Df (v) ≥ Df (x),
for all common neighbors x of u and v, such that, additionally,
Df (y) > Df (v) and Df (u) > Df (x),
for all common neighbors x of u and v.
134 Ars Math. Contemp. 6 (2013) 127–145
We set µ1 =
Df (u)−Df (v)
2 . So µ1 ≥ 0, and Df (v) = Df (u) − 2µ1. We set µ2 =
Df (y)−Df (v). Then µ2 ≥ µ1 and µ2 > 0. Note that for any x in V , we have
Df (v) ≥ Df (x)− µ2.
We construct the new weight function f ′ from f as follows
f ′(x) =
 f(x)− (µ1 + µ2) if x = vf(x)− (µ2) if x = u
f(x) otherwise.
Straightforward computation now yields
Df ′(u) = Df (u)− 2(µ1 + µ2)
= Df (v)− 2µ2
= Df ′(v);
and for any vertex x in I(u, v) distinct from u and v:
Df ′(x) = Df (x)− µ1 − 2µ2 < Df (u)− µ1 − 2µ2 = Df ′(u)− µ2 < Df ′(u);
and for any vertex x outside the interval (recall that µ1 ≤ µ2):
Df ′(x) ≤ Df (x)− 3µ2 − µ1 ≤ Df (u)− 2µ2 − µ1 < Df ′(u).
Thus AM(f ′) = {u, v}, and hence the antimedian set of f ′ is not connected. This impos-
sibility proves this implication.
It remains to prove that (i) ⇒ (ii). Let AMloc(f) = AM(f) for all weight functions
f . Assume to the contrary that the level set S = {x |Df (x) ≥ λ} corresponding to λ is not
isometric. Hence there exist two vertices u, v such that no shortest u, v-path lies completely
inside S. Obviously, we can select u, v in S such that Df (x) < λ for any x in I(u, v),
distinct from u and v. Without loss of generality we may assume Df (u) ≤ Df (v). Set
Df (z)−Df (u) = µ1, where z is an antimedian, and set  = min{Df (u)−Df (w) | w ∈
I(u, v)}. Note that, since Df (u) > λ > Df (w), for w in I(u, v), we have  > 0. Let
µ2 =

d(u,v) . Define a weight function f
′ such that
f ′(x) =
 f(x)− µ1 if x = uf(x)− (µ1 + µ2) if x = v
f(x) otherwise.
Straightforward computation now yields
Df ′(v) = Df (v)− d(u, v)µ1
> Df (u)− d(u, v)(µ1 + µ2)
= Df ′(u)
and for any vertex w in I(u, v) distinct from u and v:
Df ′(w) < Df (w)− d(u, v)µ1 ≤ Df (u)− 2 − d(u, v)µ1 =
Df (u)− d(u, v)(µ1 + µ2) = Df ′(u)
K. Balakrishnan et al.: Consensus strategies for signed profiles on graphs 135
and for any other vertex x:
Df ′(x) < Df (x)− (d(u, v) + 1)µ1 < Df (z)− µ1 − d(u, v)µ1 =
Df (u)− d(u, v)µ1 = Df ′(u).
This implies that v is the unique antimedian of f ′, while u is a local antimedian, which is
not an antimedian vertex. This contradicts the assumption, by which the proof is complete.
Above we established the equivalence of real-valued weight functions, rational-valued
weight functions, and signed profiles with respect to medians etcetera. The next theorem is
now an easy consequence of the previous results.
Theorem 3.7. Let G be a connected graph. Then the following conditions are equivalent.
(i) The antimedian set AM(f) is connected, for all weight functions f on G.
(ii) AM(f) = AMloc(f), for all weight functions f on G.
(iii) The median set M(f) is connected, for all weight functions f on G.
(iv) M(f) = Mloc(f), for all weight functions f on G.
(v) AM(f) = AMloc(f), for all rational weight functions f on G.
(vi) AM(π) = AMloc(π), for all signed profiles π on G.
(vii) M(f) = Mloc(f), for all rational weight functions f on G.
(viii) M(π) = Mloc(π), for all signed profiles π on G.
Proof. (i) up to (iv) are equivalent by Proposition 3.6, and Remark 3.1 .
(ii)⇒ (v) follows trivially.
(v)⇒ (ii) follows from Lemma 3.5.
(v) ⇒ (vi): Let π be a signed profile on G. Now consider its associated weight
function fπ . By Lemma 3.2, we have D(v, fπ) = D(v, π). Since Dfπ cannot have any
local maximum that is not a global maximum, Dπ also cannot have any local maximum
that is not a global maximum.
(vi) ⇒ (v): Let g be any rational weight function on G. By Lemma 3.3, there is a
positive integer t and a signed profile π such that fπ = tg. By Lemma 3.2, Dfπ = Dπ ,
and, as observed above, Dfπ has a local maximum that is not a global maximum if and
only if Dg have a local maximum that is not a global maximum. So Dg cannot have a local
maximum that is not a global maximum.
The equivalence of (vii) and (viii) with the other statements follows similarly.
4 Consensus Strategies
If one wants to find the median set of a positive profile in a tree, then there exists a simple
strategy formulated by Goldman [12] already in 1971. It reads as follows. When at vertex
u, consider neighbor v of u. If there is a majority of the profile closer to v than to u, then
move to v. In [20] this Majority Strategy was formulated for arbitrary graphs. There it was
proved that the Majority Strategy produces the median set for any positive profile starting
at any vertex if and only if the graph is a median graph, Theorem 4.1 below. For more
details, we refer the reader to [20, 4]. A connected graph G is called a median graph, if
every triple of vertices in G has a unique median. One of the main reasons underlying
this result is that the structure of median sets is very nice in median graphs. In [4] four
136 Ars Math. Contemp. 6 (2013) 127–145
other related consensus strategies for positive profiles are studied. Antimedian sets are not
so well-structured. So one cannot expect such deep results for signed profiles. But it is
still possible to obtain some nice and unexpected results. Below we present a number of
consensus strategies for signed profiles similar to the Majority Strategy from [18]. They
are analogues of those in [4], but now formulated for signed profiles.
In all the strategies below the input is a connected graph G, a profile π, and an initial
vertex at which the strategy starts. There are two possibilities: one gets stuck at a vertex,
or it is possible to visit vertices more than once. In the latter case the strategy could get
into a loop, so the stopping rule must be more sophisticated here. In all cases, the output
after stopping is the single vertex where one gets stuck or the set of vertices visited at least
twice. Steps 1, 3 and 4(i) below are the same for all strategies, so we list these only in the
first instance. In all other instances we only list Step 2, describing when one moves to a
neighbor, and Step 4(ii), the stopping rule when one does not get stuck.
Majority Strategy
1. Start at the initial vertex.
2. [MoveMS] If we are in u and v is a neighbor of u with ‖πvu‖ ≥ 12‖π‖,
then we move to u.
3. We move only to a vertex already visited if there is no alternative.
4. We stop when
(i) we are stuck at a vertex u or
(ii) [TwiceMS] we have visited vertices at least twice, and
for each vertex u visited at least twice and each neighbor v of u,
either ‖πvu‖ < 12‖π‖ or v is also visited at least twice.
Before presenting the other strategies we quote the main theorem from [20]. This the-
orem has been the motivation for studying such strategies on graphs. It also shows the
special role of median graphs within the Class of All Graphs. Due to the structure theory
of median graphs, the equivalence of (ii) and (iii) on median graphs in the theorem is not
surprising. But otherwise it would not have been something one would expect at first sight.
Theorem 4.1. [Majority Theorem] Let G be a graph. Then the following conditions are
equivalent.
(i) G is a median graph.
(ii) The Majority Strategy produces the median set M(π) from any initial vertex, for each
positive profile π on G.
(iii) The Majority Strategy produces the same set from any initial vertex, for each positive
profile on G.
In the majority strategy one moves towards majority. A slightly different point of view
is to move away from minority. This seems to be the same, but it is not, as we will see
below. This latter strategy is known as the Condorcet Strategy.
Condorcet Strategy
2. [MoveCS] If we are in u and v is a neighbor of u with ‖πuv‖ ≤ 12‖π‖,
then we move to v.
4. (ii) [TwiceCS] we have visited vertices at least twice, and
for each vertex u visited at least twice and each neighbor v of u,
either ‖πuv‖ > 12‖π‖ or v is also visited at least twice.
K. Balakrishnan et al.: Consensus strategies for signed profiles on graphs 137
In non-bipartite graphs the subprofile πvu of π, for an edge uv, is not always empty.
From the viewpoint of voting, one might say that the elements of πvu abstain from voting
when the choice is between u and v. So these may be ignored when the question is whether
to move from u to v. This is the idea behind the Plurality Strategy. Note that on bipartite
graphs Majority and Plurality coincide.
Plurality Strategy
2. [MovePS] If we are in u and v is a neighbor of u with ‖πvu‖ ≥ ‖πuv‖,
then we move to v.
4. (ii) [TwicePS] we have visited vertices at least twice, and
for each vertex u visited at least twice and each neighbor v of u,
either ‖πvu‖ < ‖πuv‖ or v is also visited at least twice.
The next two strategies were introduced to find a (local) minimum based on a heuristic
function in a search graph. They are also known as Hill Climbing and Steepest Ascent Hill
Climbing, respectively.
Ascent Strategy
2. [MoveAS] If we are in u and v is a neighbor of u with D(v, π) ≤ D(u, π),
then we move to v.
4. (ii) [TwiceAS] we have visited vertices at least twice, and
for each vertex u visited at least twice and each neighbor v of u,
either D(v, π) > D(u, π) or v is also visited at least twice.
Steepest Ascent Strategy
2. [MoveSAS] If we are in u and v is a neighbor of u with D(v, π) ≤ D(u, π), and
D(v, π) is minimum among all neighbors of u, then we move to v.
4. (ii) [TwiceSAS] = [TwiceAS].
The next simple Lemma is an analogue of Lemma 1 in [4] for signed profiles with the
same conclusion. Note that the Plurality and Ascent strategy produce the same output for
signed profiles on any connected graph. On bipartite graphs both coincide with Majority.
Lemma 4.2. Let G be a connected graph and π a signed profile on G. Plurality Strategy
makes a move from vertex v to vertex u if and only if D(u, π) ≤ D(v, π).
Proof. The assertion follows immediately from the following computation:
D(v, π)−D(u, π) =
=
∑
x∈πvu
sxd(v, x) +
∑
x∈πuv
sxd(v, x)−
∑
x∈πvu
sxd(u, x)−
∑
x∈πuv
sxd(u, x)
=
∑
x∈πvu
sxd(v, x) +
∑
x∈πuv
sxd(v, x)−
∑
x∈πvu
sx(d(v, x) + 1)−∑
x∈πuv
sx(d(v, x)− 1)
= ‖πuv‖ − ‖πvu‖.
138 Ars Math. Contemp. 6 (2013) 127–145
The various strategies are quite similar. But on general graphs they are all different.
We present some examples to show this. The first example shows that Plurality, Condorcet
and Majority strategies are pairwise distinct. Consider the profile π = (+a,+b,−c,+d,
+e,+f) on the graph shown in Figure 1. We have ‖πuv‖ = 1, ‖πvu‖ = 0, ‖πva‖ =
‖πvb‖ = ‖πvd‖ = ‖πve‖ = 2 ‖πvc‖ = 4, ‖πav‖ = ‖πbv‖ = ‖πdv‖ = ‖πev‖ = 1,
‖πcv‖ = −1, ‖πua‖ = ‖πub‖ = ‖πud‖ = ‖πue‖ = ‖πuf‖ = 3, ‖πuc‖ = 5, ‖πau‖ =
‖πbu‖ = ‖πdu‖ = ‖πeu‖ = ‖πfu‖ = 1, ‖πcu‖ = −1. 
a b c d e 
v u 
 f 
Figure 1: Consensus strategies differing on a graph
Apply all the strategies starting at u. Using Majority we may not move to any of its
neighbors, so we are stuck at u. Thus the outcome of Majority is {u}. Note that we have
‖πux‖ ≤ 12‖π‖, for any neighbor x of u other than c. So, if we use Condorcet, then we can
move to any of its neighbors except c. Note also that from a, b, d and e a move to either u
or v is allowed, but from v we can move only to u. Thus using Condorcet we may move
along u, a, b, d, e, v. Hence the output of the Condorcet Strategy is {u, a, b, d, e, v}. When
we use Plurality, then we can move only to v and we get stuck at v. Hence the output of
Plurality is {v}. Ascent and Steepest Ascent strategies also produce the output {v}.
It is shown in [4] that Steepest Ascent is essentially different from the other strategies
for positive profiles. Note that the other strategies might make a move from u as soon as
they find a neighbor v of u that satisfies the condition for a move, while Steepest Ascent
has to check all neighbors of u before it can make a move. For a comparison of efficiencies
of these strategies, see [3].
The following example shows that the first four strategies might not even find the me-
dian vertex, even if the graph is bipartite. Consider the complete bipartite graph K2,5 with
vertices a, b and 1, 2, 3, 4, 5, where two vertices are adjacent if and only if one is a ‘letter’
and the other is a ‘numeral’. Now take the profile π = (+b,+1,+1,+1,+2,+2,+2,+3,
+3,+3,+4,−5). Then we have D(a, π) = 11, D(b, π) = 9, D(4, π) = 21, D(5, π) = 17
and D(i, π) = 13, for i = 1, 2, 3. Take 1 as initial vertex and assume that we check its
neighbors in alphabetical order. Then Majority, Condorcet, Plurality and Ascent strate-
gies move to a and get stuck there, whereas Steepest Ascent moves to b and thus finds the
median vertex of π.
It was already shown in [4] that Plurality produces the median set for any positive
K. Balakrishnan et al.: Consensus strategies for signed profiles on graphs 139
profile if and only if all median sets in the graph are connected. Hence Plurality produces
the antimedian set for negative profile in such graphs. Moreover the antimedian sets are
connected for all negative profiles in such graphs.
In the case of finding antimedian sets one would want to have the “converse” of the
above strategies, that is, apply the strategy on −π instead of π. Because we are working
with signed profiles these are strategies in their own right. We list them below, with their
appropriate names.
Minority Strategy
Minority applied to π is identical with Majority applied to −π.
Scarcity Strategy
Scarcity applied to π is identical with Plurality applied to −π.
Descent Strategy
Descent applied to π is identical with Ascent applied to −π.
Steepest Descent Strategy
Steepest Descent applied to π is identical with Steepest Ascent applied to −π.
It is interesting to note that Scarcity produces the antimedian set in hypercubes. Recall
that the n-dimensional hypercube Qn, the n-cube for short, has the 0, 1-vectors of length
n as its vertices, two vertices being adjacent if the corresponding vectors differ in exactly
one coordinate. Take any i with 1 ≤ i ≤ n. Let Q0n,i be the (n− 1)-dimensional subcube
consisting of the vertices with a 0 as i-th coordinate, and let Q1n,i be the complementary
subcube consisting of the vertices with a 1 as i-th coordinate. For a profile π, let π0i be the
subprofile of π inQ0n,i, and let π
1
i to the subprofile of π inQ
1
n,i. LetW be the set of vertices
in Qn, for which π has a signed minority in each coordinate. That is, x lies in W if and
only if x has a 0 in the i-th coordinate when ‖π1i ‖ > ‖π0i ‖, and a 1 when ‖π0i ‖ > ‖π1i ‖,
and a 0 or 1 when ‖π0i ‖ = ‖π1i ‖. This is precisely the antimedian set of π. It is also a
subcube of dimension d, where d is the number of coordinates, for which ‖π0i ‖ = ‖π1i ‖.
Proposition 4.3. Scarcity strategy produces the antimedian set on a hypercube for any
signed profile.
Proof. Take any i with 1 ≤ i ≤ n. Take any vertex u in Q0n,i, and let v be its neighbor in
Q1n,i. Then we have πuv = π
0
i and πvu = π
1
i . So, if ‖π0i ‖ ≥ ‖π1i ‖, then we move from
Q0n,i to Q
1
n,i. And if ‖π0i ‖ > ‖π1i ‖, then we never move back to Q0n,i. So Scarcity moves
to the set of vertices W in Qn, for which π has a signed minority in each coordinate. This
is precisely the antimedian set of π.
In general Scarcity will not always produce an antimedian. For example when we use
Scarcity moves in a tree we will always stuck at leaf nodes, as we can see in the following
lines. Consider a tree T with at least three leaves, and a positive profile π of length k on
T . Take any leaf v that occurs less than 12k times in π, and let u be the neighbor of v in T .
Note that d(v, x) = d(u, x) + 1 for any x 6= v in T . Obviously we will move to v from u,
but we will never move back to v using Scarcity. But v need not be the antimedian of π. If
the profile is “close” to u, then obviously antimedian will be at some other leaves far away.
140 Ars Math. Contemp. 6 (2013) 127–145
Next we prove an analogue of the main Theorem (Theorem 8 in [4]) for positive profiles
in the case of signed profiles.
Theorem 4.4. The following are equivalent for a connected graph G.
(i) The Scarcity Strategy produces AM(π) from any initial vertex, for all signed profiles
π on G.
(ii) AM(π) is connected, for all signed profiles π on G.
(iii) AM(π) = AMloc(π), for all signed profiles π on G.
(iv) Descent Strategy produces AM(π) from any initial vertex, for all signed profiles π on
G.
(v) Steepest Descent Strategy produces AM(π) from any initial vertex, for all signed pro-
files π on G.
(vi) Scarcity, Descent, and Steepest Descent Strategy each produce the same set from any
initial vertex, for all signed profiles.
Proof. (i) ⇒ (ii): Suppose the antimedian set is not connected for some profile π. Then
let u and v be two vertices in different components of AM(π). Now, if Scarcity starts
at u, then it cannot reach vertex v, because a move from an antimedian vertex to a non-
antimedian vertex is not possible by Lemma 4.2. So the set computed by Scarcity will not
include u, which is a contradiction.
(ii)⇒ (iii): This follows from Theorem 3.7.
(iii)⇒ (iv): Starting at any vertex, Descent always finds a local maximum. Since this
local maximum is also global, it follows that Descent always reaches an antimedian, and
since the antimedian set is connected, Descent finds all antimedian vertices.
(iv) ⇒ (i): Assume that Descent finds the antimedian set. This means that Descent
will move to an antimedian starting from any vertex and finds all the other antimedians.
The same moves will be made by Scarcity, by Lemma 4.2. Hence Scarcity will compute
the antimedian set correctly.
(iii)⇒ (v) follows similarly as (iii)⇒ (iv).
(v) ⇒ (ii) follows from the fact that Steepest Descent finds a local maximum and
does move from antimedian to antimedian but does not move from an antimedian to a
non-antimedian.
(i)⇒ (vi) is obvious.
(vi)⇒ (i) follows from the fact that, starting from an antimedian, Scarcity can produce
only a set of antimedians which includes the initial vertex. So starting from any vertex
it produces the same set if and only if the produced set is actually AM(π). The same
argument works for Descent and Steepest Descent.
5 The Majority Strategy for Signed Profiles
In this section a characterization for hypercubes is obtained as the graphs for which Ma-
jority always produces the median set for any signed profile. Before stating the result, we
need a few facts from the theory of median graphs as developed in [18]. A median graph
is bipartite, and does not contain K2,3 as induced subgraph. This implies that any two
vertices at distance 2 have either one or two common neighbors. It is proved in [18] that
a graph G is a hypercube if and only if it is a median graph in which any two vertices at
distance 2 have exactly two common neighbors. For any vertex w in a graph G, we write
Ni(w) = {x | d(x,w) = i}, and N>i(w) =
⋃
j>iNj(w).
K. Balakrishnan et al.: Consensus strategies for signed profiles on graphs 141
Proposition 5.1. Let AM be the antimedian function on a median graph G. Then AM(π)
is connected for every signed profile π if and only if G is a hypercube.
Proof. If G is a hypercube, then Proposition 4.3 gives us the required result.
Conversely, let G be a median graph for which the antimedian set is connected, for any
signed profile. Let u and v be two vertices at distance 2, and let w be a common neighbor
of u and v. Due to the above mentioned characterization of hypercubes in [18] we have to
prove that there exists a unique common neighbor of u and v different from w. Consider
the profile π = (+w) of length 1. Note that, for any x in Nj(w), we have Df (x) = j. So
N>0(w) = V − w is a level set with respect to π. Due to Proposition3.6 any level set of π
induces an isometric subgraph. So, within V − w, the vertices u and v have distance 2 as
well, that is, there is a common neighbor z in V − x. Since a median graph is bipartite and
does not contain K2,3, this neighbor is unique.
The next theorem is an analogue of the majority theorem for signed profiles which turns
out to be a new characterization of hypercubes.
Theorem 5.2. A graph G is a hypercube if and only if the Majority Strategy, starting from
any initial vertex, produces the median set for any signed profile on G.
Proof. If G is a hypercube, then, by Proposition 4.3, Scarcity produces the antimedian
set for any signed profile. So, since the hypercube is bipartite, Minority produces the
antimedian set for any signed profile, whence Majority produces the median set for any
signed profile.
Conversely, assume that Majority produces the median set for any signed profile. Then
it also produces the median set for any positive profile. So, by Theorem 4.1, the graph is a
median graph. Hence, by Proposition 5.1, the graph is a hypercube.
6 Graphs for which Scarcity produces the Antimedian Set for any
Signed Profile
In this section we discuss some graph classes for which Scarcity always produces the anti-
median set for any signed profile.
First we consider the Hamming graphs. Let k1, . . . , kn be positive integers, and let V
be the Cartesian product
Πni=1{0, 1, . . . , ki − 1}.
The Hamming graph Hk1,...,kn is the graph with vertex set V , in which two vertices are
joined by an edge if and only if the corresponding vectors differ in exactly one coordinate.
The properties for Hamming graphs needed here probably all belong now to folklore, but
could also be found in [18, 19], where they were characterized for the first time. The set
of vertices in H = Hk1,...,kn having a in the i-th position of the corresponding vector is
denoted as Hak1,...,kn,i, or simply as H
a
i . For a profile π, we denote its subprofile contained
in Hai by π
a
i .
Let π be a profile on H = Hk1,...,kn . Fix a position i, for which ki ≥ 2, and let a
and b be distinct elements in {0, . . . , ki − 1}. Let u be a vertex in Hai , and let v be its
neighbor in Hbi . Then πuv = π
a
i and πvu = π
b
i . Note that, if u is in AM(π), then we have
‖πai ‖ ≤ ‖πbi ‖. This holds for every b in {0, . . . , ki − 1} distinct from a. In this case we
142 Ars Math. Contemp. 6 (2013) 127–145
say that there is a signed minority at a in position i. Clearly, an antimedian vertex in H
is a vertex with a signed minority in each coordinate. Let mi be the number of elements
in {0, . . . , ki − 1} with a signed minority, for i = 1, . . . , n. Then the antimedian set of π
induces a subgraph isomorphic to Hm1,...,mn . Obviously, any antimedian set is connected.
Proposition 6.1. Starting form any vertex Scarcity Strategy produces the antimedian set
on a Hamming graph for any signed profile.
Proof. Let π be a (signed) profile on the Hamming graph H = Hk1,...,kn . Take any i
with 1 ≤ i ≤ n and any vertex u in Hai , and let v be its neighbor in Hbi with b 6= a. If
‖πai ‖ ≥ ‖πbi ‖, then we move from Hai to Hbi . And if ‖πai ‖ > ‖πbi ‖, then we never move
back to Hai . So Scarcity moves to the set of vertices W in H for which π has a signed
minority in each coordinate. This is precisely the antimedian set of π.
Graphs which admit a scale-λ, (λ ≥ 2) embedding into a hypercube is called an `1
graph. The Johnson graphs and half cubes are important classes of `1 graphs which occur
as hosts for isometric embeddings of graphs, [8]. Next we consider the Johnson graphs
followed by half cubes. The Johnson graph Jn,k has as vertices the k-element subsets of
{1, 2, . . . , n}, and two vertices are adjacent if and only if their intersection has size k − 1.
In other words the vertices ‘differ’ in exactly one element. Some special Johnson graphs
are: Jn,1 is the complete graph on n vertices, Jn,2 is the n-triangular graph, and Jn,3 is
n-tetrahedral graph. Since each vertex u in Jn,k corresponds to a k-element subset X of
{1, 2, . . . , n}, we represent u with the vector [u1, . . . , un], where
ui =
{
1; i ∈ X,
0; i 6∈ X
Clearly the total number of 1’s in each vector representation is k. Moreover adjacent ver-
tices differ in two positions. Note that mapping these vectors to the corresponding vectors
in a hypercube Qn corresponds to a so-called scale-2 embedding, that is, two vertices at
distance d in the Johnson graph are mapped onto vertices at distance 2d in the hypercube,
for any two vertices. Since below the antimedian sets in more than one graph will be
considered, we denote the antimedian set of π in G also by AM(π,G), and so forth.
Proposition 6.2. Let G be a Johnson graph. Then M(π) and AM(π) are also Johnson
graphs.
Proof. Assume that G = J(n, k). Consider the scale-2 embedding of G in to the hyper-
cube Qn. Let π be a profile in G, and let M(π,Qn) be isomorphic to Qr. Without loss of
generality we may assume that, for all the vertices u = [u1, . . . , un] in this subcube, the
coordinates at positions r + 1 up to n are all the same, and that in the remaining positions
1, . . . , r values 0 and 1 are taken. Letm be the total number of 1’s, in positions r+1, . . . , n.
We analyze the properties of median sets in G by considering two cases.
Case 1. M(π,Qn) ∩G 6= ∅.
Clearly M(π,G) induces a subgraph isomorphic to Jr,(k−m).
Case 2. M(π,Qn) ∩G = ∅.
In this case we have either m < k − r or m > k. Clearly, if m < k − r, we get a vertex
in G by changing a minimum number of coordinates, say p, from the vertex in M(π,Qn)
having 1s in positions 1, . . . , r.
K. Balakrishnan et al.: Consensus strategies for signed profiles on graphs 143
Similarly, when m > k, we get a vertex in G with a minimum number of changes, by
selecting the vertex with 0’s in positions 1, . . . , r. Since we are looking for a median set in
G, we select the positions, in such a way that the change in remoteness is minimum. Thus
we select p coordinate positions with smaller signed majority values. If the signed majority
values are distinct we get a single vertex in G. Otherwise we make a selection among, say
p′ positions. In this case the subgraph induced by the vertices of G thus obtained will be
isomorphic to Jp′,p.
Since the remoteness is same for all vertices in the median set we get the same result
independent of the vertex selected. Hence we get a subgraph that is a Johnson graph as the
median set.
With similar arguments, by taking the signed minority values at coordinate positions,
we can prove that antimedian sets also induce some Johnson graph. This completes the
proof.
From the above theorem we have the following corollary.
Corollary 6.3. LetG be a Johnson graph. ThenM(π) andAM(π) are connected, for any
signed profile π in G.
From the above Corollary and Theorem 4.4 we have:
Corollary 6.4. Starting from any vertex on a Johnson graph Scarcity strategy produces the
antimedian set for any signed profile.
Next, we consider halfcubes. The vertex set of a halfcube is the subset of the vertices
of the hypercube Qn with an even (respectively, odd) number of ones in their vector rep-
resentation. Two vertices are adjacent when they differ in exactly two positions, see [8].
Halfcubes also admit a scale-2 embedding into the corresponding hypercube.
Theorem 6.5. Let G be a halfcube, then M(π,G) and AM(π,G) are connected for any
signed profile π in G.
Proof. Let Qn be the hypercube of dimension n in which G is scale-2 embedded. Let π
be an arbitrary profile in G and ‖π‖ = k. Note that by applying the Majority rule for the
given profile π of the halfcube embedded into hypercube Qn (looking as the vertices of a
hypercube), we get the median of π in Qn which will be a sub-hypercube, say Qr. We
analyze the property of M(π,G) by considering the following two cases separately.
Case 1. M(π,Qn) is a hypercube Qr of dimension at least one.
Clearly Qr has half vertices in the corresponding halfcube - call this set X . Set X forms
a halfcube in G, hence X is connected. Since the graph G is scale-2 embedded the re-
moteness in G is obtained by dividing the corresponding remoteness in Qn by 2, we get
M(π,G) = X , as we follow the signed Majority rule on π.
Case 2. M(π,Qn) in Qn contains exactly one vertex say x.
If x belongs to G, then clearly M(π,G) = {x} as the case may be and hence we are done.
So assume that x is not in G. Note that x = (x1, . . . , xd) can be obtained from the
signed Majority rule among coordinates of the profile π. Let mi, 1 ≤ mi ≤ n be the
signed majority at each position. Let m = min{m1, . . . ,mn}. Clearly if for any vertex y
obtained by changing any single ith coordinate of x, the remoteness changes by 2mi − k,
where ‖π‖ = k. This change in remoteness is minimum for coordinates having signed
144 Ars Math. Contemp. 6 (2013) 127–145
Majority value m. Hence M(π,G) is precisely the set of vertices obtained from G by
changing any coordinate of x, having minimum signed Majority mi. These vertices are all
adjacent to x, and hence forms a clique in G. Thus M(π,G) is connected for any signed
profile.
With similar arguments and by taking m as maximum(m1, . . . ,mn), where each mi
is signed minority, we can prove that AM(π,G) is also connected for any profile, which
completes the proof.
From the proof of the above theorem, we have the following corollary.
Corollary 6.6. Let G be a halfcube, then M(π,G) and AM(π,G) induce a halfcube in G
or a clique, for any profile π in G.
From Theorem 6.5 and Theorem 4.4 we have:
Corollary 6.7. Starting from any arbitrary vertex in a halfcube Scarcity Strategy always
produce antimedian set for any signed profile
7 Concluding remarks
In this paper, we have proved that the classes of graphs in which the consensus strategies
Scarcity, Descent and Steepest Descent will always produce the antimedians for any arbi-
trary signed profile is precisely the class of graphs with connected antimedians. This class
of graphs is characterized in terms of (local) medians and (local) antimedians of (rational)
weight functions. Also, we proved that, among the median graphs, the hypercubes are pre-
cisely the graphs with connected antimedians for an arbitrary signed profile. Moreover, we
presented some classes on which Scarcity produces the antimedian set for any signed pro-
file. An intriguing question remains: Which classes of graphs have connected antimedians
for arbitrary signed profiles?
References
[1] K. Balakrishnan, B. Brešar, M. Changat, S. Klavžar, M. Kovše and A. R. Subhamathi, On the
remoteness function in median graphs, Discrete Appl. Math. 157 (2009), 3679–3688.
[2] K. Balakrishnan, B. Brešar, M. Changat, S. Klavžar, M. Kovše and A. R. Subhamathi, Si-
multaneous embeddings of graphs as median and antimedian subgraphs, Networks 56 (2010),
90–94.
[3] K. Balakrishnan, M. Changat and H. M. Mulder, Median computation in graphs using consen-
sus strategies, Report EI 2006, Econometrisch Instituut, Erasmus Universiteit, 2006, Rotter-
dam.
[4] K. Balakrishnan, M. Changat and H. M. Mulder, The plurality strategy on graphs, Australsian
J. Combin. 46 (2010), 191–202.
[5] K. Balakrishnan, M. Changat, I. Peterin, S. Špacapan, P. Šparl and A. R. Subhamathi, Strongly
distance-balanced graphs and graph products, Eur. J. Combin. 30 (2009), 1048–1053.
[6] H. J. Bandelt and V. Chepoi, Graphs with connected medians, SIAM J. Discr. Math. 15 (2002),
268–282.
[7] J. P. Barthelemy and B. Monjardet, The median procedure in cluster analysis and social choice
theory, Math. Social Sci. 1 (1981), 235–268.
K. Balakrishnan et al.: Consensus strategies for signed profiles on graphs 145
[8] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer-Verlag,
Berlin, 1989.
[9] P. Cappanera, A survey on obnoxious facility location problems, Technical Report TR-99-11,
University of Pisa, 1999.
[10] P. Cappanera, G. Gallo and F. Maffioli, Discrete facility location and routing of obnoxious
activities, Discrete Appl. Math. 133 (2003), 3–28.
[11] R. L. Church and R. S. Garfinkel, Locating an obnoxious facility on a network, Transportation
science 12 (1978), 107–118.
[12] A. J. Goldman, Optimal center location in simple networks, Transportation Science 5 (1971),
212–221.
[13] S. Klavžar and H. M. Mulder, Median graphs: characterizations, location theory and related
structures, J. Combin. Math. Combin. Comput. 30 (1999), 103–127.
[14] F. R. McMorris, H. M. Mulder and F. S. Roberts, The median procdure on median graphs,
Discrete Appl. Math. 84 (1998), 165–181.
[15] F. R. McMorris, H. M. Mulder and R. V. Vohra, Axiomatic characterization of location func-
tions, in: H. Kaul and H. M. Mulder (eds.), Advances in interdisciplinary discrete applied math-
ematcis, Interdisplinary Mathematical Sciences, Vol. 11, World Scientific, Singapore, 2010,
pp. 71–91.
[16] F. R. McMorris and R. C. Powers, The median procedure in a formal theory of consensus, Siam
J. Discrete Math. 8 (1995), 507–516.
[17] P. B. Mirchandani and R.L. Francis, Discrete Location Theory, Wiley-Interscience, New York,
1990.
[18] H. M. Mulder, The Interval Function of a Graph, Mathematical Centre Tracts 132, Mathema-
tisch Centrum, Amsterdam, 1980.
[19] H.M. Mulder, Interval-regular graphs, Discrete Math. 41 (1982), 253–269.
[20] H. M. Mulder, The Majority Strategy on graphs, Discrete Appl. Math. 80 (1997), 97–105.
[21] H.M. Mulder, Median graphs, A structure theory, in: H. Kaul and H.M. Mulder (eds.), Ad-
vances in interdisciplinary discrete applied mathematcis, Interdisplinary Mathematical Sci-
ences, Vol. 11, World Scientific, Singapore, 2010, pp. 93–125.
[22] R. C. Powers, Consensus centered at majority rule, in: H. Kaul and H.M. Mulder (eds.), Ad-
vances in interdisciplinary discrete applied mathematcis, Interdisplinary Mathematical Sci-
ences, Vol. 11, World Scientific, Singapore, 2010, pp. 149–166.
[23] R. C. Tansel, R. I. Francis and T. J. Lowe, Location on networks: A survey I, Management
Sci. 29 (1983), 482–497.
[24] R. C. Tansel, R. I. Francis and T. J. Lowe, Location on networks: A survey II, Management
Sci. 29 (1983), 498–511.