# Median Sets and Median Number of a Graph

Authors: R. Ram Kumar; B. Kannan
Journal: ISRN Discrete Mathematics
 (2012)

---

## Abstract

Aprofile is a finite sequence of vertices of a graph. The set of all vertices of the graph which minimises the sum of the distances to the vertices of the profile is the median of the profile. Any subset of the vertex set such that it is the median of some profile is called a median set. The number of median sets of a graph is defined to be the median number of the graph. In this paper, we identify the median sets of various classes of graphs such as Kp−e, Kp,q for P>2, and wheel graph and so forth. The median numbers of these graphs and hypercubes are found out, and an upper bound for the median number of even cycles is established. We also express the median number of a product graph in terms of the median number of their factors.


---

## Body

## 1. Introduction

We consider only nonempty finite simple undirected connected graphs. For the graphG, V(G), and E(G) denote its vertex set and edge set, respectively. When the underlying graph is obvious, we will use V and E for V(G) and E(G), respectively. A finite sequence of vertices π=(v1,…,vk)∈Vk is called a profile. For the profile π=(v1,…vk) and x∈V, the remotenessD(x,π) is ∑1≤i≤n‍d(x,vi) [1]. The set of all vertices x for which D(x,π) is minimum is the median of π in G and is denoted by M(π). A set S such that S=M(π) for some profile π is called a Median set of G. The IntervalI(u,v) between vertices u and v of G consists of all vertices which lie in some shortest path between u and v. The number of intervals of a graph G is denoted by in  (G). The HypercubeQn is the graph with vertex set {0,1}n, two vertices being adjacent if they differ exactly in one coordinate. A Subcube of the hypercube Qn is an induced subgraph of Qn, isomorphic to Qm for some m≤n. A graph G is a Median graph if, for every (x,y,z)∈V3, I(x,y)∩I(y,z)∩I(x,z) contains a unique vertex, see Avann [2]. Trees, hypercubes, and grid graphs are all median graphs. For further references concerning median graphs, see Mulder and Schrijver [3], Mulder [4], and Bandelt and Hedlíková [5]. The graph on p vertices formed by joining all the vertices of a (p-1)-cycle to a vertex is a wheel graph and is denoted by Wp. The vertex which is joined to all the vertices of the (p-1)-cycle is the universal vertex. The Cartesian productG□H of two graphs G and H has vertex set V(G)×V(H), two vertices (u,v) and (x,y) being adjacent if either u=x and vy∈E(H) or ux∈E(G) and v=y. The eccentricitye(u) of a vertex u is maxv∈V(G)d(u,v). A vertex v is an eccentric vertex of u if e(u)=d(u,v). Graph products form a well-studied area in graph theory, see [6, 7]. The problem of finding the median of a profile is very much significant in location theory, particularly in efficiency-oriented model [8], as it corresponds to finding the most desirable service point for a group of customers when the minimisation of the total cost is a primary objective. Here we use profiles of vertices instead of a set of vertices which gives us the liberty to repeat a vertex any number of times. This makes the problem more relevant in location theory as it enables us to assign different weights to different customers. The problem of finding the median of a profile has been thoroughly investigated by many authors; see [9–14]. The objective of this paper is to identify median sets of some classes of graphs and to enumerate them.


## 2. Median Number

On the set of all profiles onV, V*=⋃k∈Z‍Vk, we define a relation M by π1Mπ2 if M(π1)=M(π2). This is an equivalence relation. This equivalence relation gives a partition of the whole set of profiles. The number of equivalence classes in this partition is defined as the Median number of graph G and is denoted by mn(G). That is, it is the number of distinct median sets in G.Proposition 2.1.
For any graphG=(V,E) on p vertices, in(G)≤mn(G)≤2p-1.Proof.
The upper bound is obvious as it is the number of nonempty subsets of the vertex set. For everyv∈V, v is a median set of the profile (v). For every u,v∈V, the set I(u,v) is the median set of the profile (u,v). Therefore in(G)≤mn(G)≤2p-1.Proposition 2.2.
m
n
(
K
p
)
=
2
p
-
1, where Kp is the complete graph on p vertices.Proof.
InKp, each nonempty subset of the vertex set is a median set, namely, of the profile formed by taking all the elements of the set exactly once. Therefore the number of distinct median sets is the number of nonempty subsets of V which is 2p-1.Proposition 2.3.
Ife is an edge of Kp,  p≥3, mn(Kp-e)=2p-2p-2.Proof.
Lete=(u,v)∈E. For every vertex set S such that {u,v}⊈S, there exists a profile which has S as its median set, namely, the profile formed by taking the vertices of S exactly once. Let π be a profile which does not simultaneously contain u and v. Then M(π) is a subset of the set of vertices corresponding to the profile π and hence does not contain u and v. Now, let π be profile which contains both u and v. Then if u or v is repeated more than the other in the profile, then D(u,π)≠D(v,π) and so they cannot appear together in the M(π). Assume that π contains both u and v where both are repeated the same number of times. Let the profile be (x1,…,xk,u,…,u︸mtimes,v,…,v︸mtimes), m≥1. For xi, 1≤i≤k, D(xi,π)≤k-1+2m. Also, D(u,π)=k+2m and D(v,π)=k+2m. Therefore M(π) does not contains both u and v. Now the profile (u,v) has V as its median set. Hence V is the only median set which contains both u and v. Therefore the class of all median sets of the graph consists of V and all subsets of V which do not simultaneously contain u and v. Hence,
(2.1)mn(Kp-e)=(p1)+(p2)-(p-20)+(p3)-(p-21)+⋯+(pp-1)-(p-2p-3)+(pp)=2p-1-(2p-2-1)=2p-2p-2.Proposition 2.4 (Bandelt and Barthélémy [10]).
LetG=(V,E) be a median graph. For any profile π in G the median set is an interval I(u,v) in G.Proposition 2.5.
The median number of a treeT on p vertices is (p2)+p.Proof.
SinceT is a median graph, by the above proposition all median sets are intervals. As observed in the proof of Proposition 2.1, all intervals are median sets. Therefore, class of median sets of T is precisely the class of intervals of T which is the class of all paths in T. Hence the median number is the number of distinct paths in T which is (p2)+p.Proposition 2.6 (Imrich and Klavžar [6]).
LetQr be a hypercube. Then, for any pair of vertices u,v∈Qr the subgraph induced by the interval I(u,v) is a hypercube of dimension d(u,v).Theorem 2.7.
For the hypercubeQr, mn(Qr)=3rProof.
SinceQr is a median graph, by Propositions 2.4 and 2.6, every median set of Qr is a subcube. Also in any graph G,  I(u,v) is the median set of the profile (u,v), where u,v∈V(G). Thus in a hypercube every subcube is a median set. Therefore, the median sets of Qr are precisely the induced subcubes. So the Median number of Qr is the number of subcubes of Qr. Every vertex of Qr contains r coordinates where each coordinate is either 0 or 1. Keeping k co-ordinates fixed and varying 0 and 1 over the other r-k positions, we get a subcube of dimension r-k. By varying 0's and 1's over these k positions we get 2k such subcubes. The k positions, to be fixed can be chosen in (rk) ways. So the total number of subcubes of dimension r-k is 2k×(rk). Therefore the total number of subcubes of Qr is ∑0≤k≤r‍(rk)×2k=3r.Theorem 2.8.
For the wheel graphWp,  p≥6, mn(Wp)=(p2+3p-2)/2.Proof.
Let{v1,v2,…,vp-1,vp} be the vertex set of Wp with vp as the universal vertex, and let Cp-1 be the cycle v1,v2,…,vp-1,v1. Each singleton set {vi},  1≤i≤p-1, is a median set. The sets {vi,vj}, where vi and vj are adjacent, are also median sets. The profile (vi,vi+(p-1)1,vp), 1≤i≤p-1 (+p-1 means addition modulo p-1) has {vi,vi+(p-1)1,vp} as median set. The set {vi,vi+(p-1)1,vi+p-12,vp} is the median set of the profile (vi,vi+(p-1)2). Let π=(x1,x2,…,xk) be a profile of Wp which contains the universal vertex vp. Then since π contains the vertex vp, D(vp,π)≤k-1. If some vi, 1≤i≤p-1, belongs to M(π), then D(vi,π)≤k-1 and this implies xj=vi at least for some j. Also, the number of xj's with d(vi,xj)=2 is less than the number of repetitions of vi in π. Let vk be such that d(vk,vi)=2. Then vk belongs to M(π) that implies number of repetitions of vk is greater than the number of repetitions of vi in the profile π. But these two statements are contradictory. Thus for a profile which contains the universal vertex the median set cannot contain two vertices which are at distance 2. Hence the only possible median sets for such a profile are (i)
sets of type{vi,vi+(p-1)1},(ii)
sets of type{vi,vp},(iii)
sets of type{vi,vi+(p-1)1,vp}.
Now, letπ=(x1,…,xk) be a profile which does not contain vp. Then D(vp,π)=k. If some vi, 1≤i≤p-1, belongs to M(π), then D(vi,π)≤k. Let vj be such that vj∈M(π) and d(vi,vj)=2. Then D(vj,π)≤k. since D(vi,π)≤k, the number of zeroes in {d(vi,x1),…,d(vi,xk}≥ number of twos in {d(vi,x1),…,d(vi,xk}. Similarly, number of zeroes in {d(vj,x1),…,d(vj,xk}≥ number of twos in {d(vj,x1),…,d(vj,xk}.
Thus, number of repetitions ofvi in π = number of repetitions of vj in π.
Now, letdCp-1(vi,vj)=2. Without loss of generality, we may assume that j=i+(p-1)2. If some vertex other than vi,vi+(p-1)1,vi+(p-1)2 belongs to π, then D(vi,π)=D(vj,π)>D(vp,π). If vi+(p-1)1∈π, then D(vi+(p-1)1,π)<D(vi,π). Therefore π can only be (vi,…,vi,vj,…,vj), where vi and vj are repeated the same number of times. Since j=i+(p-1)2, we have D(vi,π)=D(vj,π)=D(vp,π)=D(vi+(p-1)1,π) and for all other x∈V, D(x,π)>k. Hence M(π)={vi,vi+(p-1)1,vi+(p-1)2,vp}. If dCp-1(vi,vj)≠2 then some vertex other than vi and vj that belong to π will contradict the fact that vi and vj belong to M(π). Therefore, in this case also π=(vi,…,vi,vj,…,vj), where vi and vj are repeated the same number of times. Here D(vi,π)=k, D(vj,π)=k, D(vp,π)=k and for all other x∈V,  D(x,π)>k. In other words, M(π)={vi,vj,vp}.
Hence the only median sets are(1)
{vi},1≤i≤p,(2)
{vi,vi+(p-1)1},1≤i≤p-1,(3)
{vi,vp},1≤i≤p-1,(4)
{vi,vp,vi+(p-1)1},1≤i≤p-1,(5)
{vi,vj,vp}1≤i,j≤p-1,(i-j)mod(p-1)≥3 (since p≥6, such vertices do exist),(6)
{vi,vi+(p-1)1,vi+(p-1)2,vp},1≤i≤p-1.
Thus,mn(Wp)=p+p-1+p-1+p-1+((p-1)(p-6))/2+p-1=(p2+3p-2)/2.Theorem 2.9.
m
n
(
K
p
,
q
)
=
2
p
+
q
-
1, where Kp,q is the complete bipartite graph with p≤q,  p>2.Proof.
Let(X,Y) be a bipartition of Kp,q with |X|=p and |Y|=q. Let X={x1,…,xp} and Y={y1,…,yq}. Let A be a k-element subset of X with k≤p. Without loss of generality, we may assume that A={x1,…,xk}.
Ifk<q, take π=(x1,…,xk,y1,…,yq). For each xi, 1≤i≤k, D(xi,π)=2(k-1)+q. For each xi, k+1≤i≤p, D(xi,π)=2k+q. For each yi, 1≤i≤q, D(yi,π)=2(q-1)+k. Therefore, A={x1,…,xk}=M(π).
Ifk=q, then π=(y1,…,yq) has median set A={x1,…,xk}. Therefore, every subset of X is a median set.
Now, letB⊆Y with B={y1,…,yk}.
Ifk<p then as in the previous case π=(x1,…,xp,y1,…,yk) has median set B.
Now, letk≥p and let π be the profile (x1,…x1,…,xp,…xp,y1,…,yk), where each xi is repeated the same number of times, (say) r.
For eachyi, 1≤i≤k, D(yi,π)=2(k-1)+pr, for each yi, k+1≤i≤q, D(yi,π)=2k+pr, and for each xi, 1≤i≤q, D(xi,π)=2r(p-1)+k. Moreover, 2(k-1)+pr<2r(p-1)+k⇔k-2<(p-2)r⇔r>((k-2)/(p-2))(p>2). That is, if each xi is repeated r times where r>(k-2)/(p-2), then M(π)=B.
Now, letC={x1,…,xk,y1,…,yr}, 1≤k≤p, 1≤r≤q.
Takeπ=(x1,…,x1,…,xk,…,xk,y1,…,y1,…,yr,…,yr), where each xi is repeated sx times and yi is repeated sy times.
For eachxi, 1≤i≤k, D(xi,π)=2(k-1)sx+rsy, for each yi, 1≤i≤r, D(yi,π)=2(r-1)sy+ksx, for each xi, k+1≤i≤p, D(xi,π)=2ksx+rsy, and for each yi, r+1≤i≤q, D(yi,π)=2rsy+ksx. Any xi, k+1≤i≤p or yi, r+1≤i≤q cannot be in M(π).
Now2(k-1)sx+rsy=2(r-1)sy+ksx⇔(k-2)sx=(r-2)sy. Hence for any sx and sy such that (k-2)sx=(r-2)sy, the profile (x1,…x1,…,xk,…,xk,y1,…,y1,…,yr,…,yr), where each xi is repeated sx times and yi is repeated sy times, has C as its median. Therefore, every nonempty subset of X∪Y is a median set. Hence, mn(Kp,q)=2p+q-1.Lemma 2.10.
Letπ1 and π2 be profiles in the graphs G1 and G2, respectively. If M(π1)=M1 and M(π2)=M2, then π1×π2 is a profile in the graph G1□G2 with M(π1×π2)=M1×M2.Proof.
Letπ1=(u1,u2,…,um),  π2=(v1,v2,…,vn), and M=M(π1×π2).
Considerπ1×π2=((u1,v1),…,(u1,vn),…,(um,v1),…,(um,vn)).
If(x1,y1),(x2,y2)∈V(G1□G2), then dG1□G2((x1,y1),(x2,y2))=dG1(x1,y1)+dG2(x2,y2), see [9]. For any(x,y)∈V(G1□G2), D((x,y),π1×π2) = n∑1≤i≤m‍d(x,ui)+m∑1≤i≤n‍d(y,vi).
Let(a,b)∈M1×M2, that is, a∈M1 and b∈M2. Then,(2.2)∑1≤i≤md(a,ui)≤∑1≤i≤md(x,ui),∀x∈V(G1),∑1≤i≤nd(b,vi)≤∑1≤i≤nd(y,vi),∀y∈V(G2).
Therefore,
(2.3)n∑1≤i≤m‍d(a,ui)+m∑21≤i≤n‍d(b,vi)≤n∑1≤i≤m‍d(x,ui)+m∑1≤i≤n‍d(y,vi),∀(x,y)∈V(G1□G2).
Hence, D((a,b),π1×π2)≤D((x,y),π1×π2), for all (x,y)∈V(G1□G2).
Thus,(a,b)∈M1×M2⇒(a,b)∈M or M1×M2⊆M.
Now, let(a,b)∈M(2.4)D((a,b),π1×π2)=n∑1≤i≤md(a,ui)+m∑1≤i≤nd(b,vi)≤n∑1≤i≤md(x,ui)+m∑1≤i≤nd(y,vi),∀(x,y)∈V(G1×G2).
If for some x'∈V(G1),
(2.5)∑1≤i≤md(x',ui)<∑1≤i≤md(a,ui),thenn∑1≤i≤md(x',ui)+m∑1≤i≤nd(b,vi)<n∑1≤i≤md(a,ui)+m∑1≤i≤nd(b,vi).
This contradicts (a,b)∈M=M(π1×π2).
Therefore(2.6)∑1≤i≤md(a,ui)≤∑1≤i≤md(x,ui),∀x∈V(G1),∑1≤i≤md(b,vi)≤∑1≤i≤md(y,ui),∀y∈V(G2).
Hence, a∈M1 and b∈M2 or (a,b)∈M1×M2. That is, M=M1×M2.Theorem 2.11.
m
n
(
G
1
□
G
2
)
=
m
n
(
G
1
)
×
m
n
(
G
2
).Proof.
By the above lemma the product of median sets ofG1 and G2 is again a median set of G1□G2. Now, let M be a median set of G1□G2, with M=M(π), where π=((u1,v1),…,(uk,vk)). Let π1=(u1,…,uk), π2=(v1,…,vk), M1=M(π1), and M2=M(π2). Let (a,b)∈M.
We have(2.7)∑1≤i≤kd(a,ui)+∑1≤i≤kd(b,vi)≤∑1≤i≤kd(x,ui)+∑1≤i≤kd(y,vi),∀x∈V(G1),∀y∈V(G2),∴k∑1≤i≤kd(a,ui)+k∑1≤i≤md(b,vi)≤k∑1≤i≤kd(x,ui)+k∑1≤i≤md(y,vi),∀(x,y)∈V(G1□G2).
In other words, D((a,b),π1×π2)≤D((x,y),π1×π2), for all (x,y)∈V(G1□G2).
∴
(
a
,
b
)
∈
M
(
π
1
×
π
2
) or M⊆M(π1×π2).
Let(a,b)∈M(π1×π2). Then D((a,b),π1×π2)≤D((x,y),π1×π2), for all x∈V(G1), for  all y∈V(G2).
That is(2.8)k∑1≤i≤kd(a,ui)+k∑1≤i≤kd(b,vi)≤k∑1≤i≤kd(x,ui)+k∑1≤i≤kd(y,vi),∀x∈V(G1),∀y∈V(G2),∑1≤i≤kd(a,ui)+∑1≤i≤kd(b,vi)≤∑1≤i≤kd(x,ui)+∑1≤i≤kd(y,vi),∀x∈V(G1),∀y∈V(G2),∴∑1≤i≤kd((a,b),(ui,vi))≤∑1≤i≤kd((x,y),(ui,vi)),∀(x,y)∈V(G1□G2).
Therefore, (a,b)∈M which implies M(π1×π2)⊆M or M=M(π1×π2)=M(π1)×M(π2). Thus, the class of all median sets of G1□G2 is the same as the class of all Cartesian products of median sets of G1 and G2.
Hence,mn(G1□G2)=mn(G1)×mn(G2).The above theorem can be used to find the median number of various classes of graphs. The first of the following corollaries gives another technique to find out the Median number of a hypercube.Corollary 2.12.
IfG1,…,Gk are k graphs, then mn(G1□⋯□Gk)=mn(G1)×⋯×mn(Gk).Corollary 2.13.
For the hypercubeQr,  mn(Qr)=3r.Proof.
SinceQr=K2□⋯□K2︸rtimes, mn(Qr)=mn(K2)×⋯×mn(K2)︸rtimes=3×⋯×3︸rtimes=3r.Corollary 2.14.
IfG is the Grid graph Pr□Ps,  mn(G)=((r2)+r)×((s2)+s).Corollary 2.15.
IfG is the Hamming graph Kp1□Kp2□⋯□Kpr, mn(G)=(2p1-1)×(2p2-1)×⋯×(2pr-1).Lemma 2.16.
The only median set of the cycleC2r which contains a vertex and its eccentric vertex is V.Proof.
Leta and b be two eccentric vertices of the cycle C2r which belongs to M(π) where π=(x1,…,xk). Let D(a,π)=D(b,π)=s. Then
(2.9)D(a,π)+D(b,π)=d(a,x1)+⋯+d(a,xk)+d(b,x1)+⋯+d(b,xk)=d(a,x1)+d(b,x1)+⋯+d(a,xk)+d(b,xk)=d(a,b)+⋯+d(a,b)︸ktimes=kr.
Hence 2s=kr. Now, suppose M(π)≠V. Then there exists an x∈V such that D(x,π)>s. That is, d(x,v1)+⋯+d(x,vk)>s. Let y be the eccentric vertex of x. d(y,v1)+⋯+d(y,vk)≥s. Therefore, d(x,v1)+⋯+d(x,vk)+d(y,v1)+⋯+d(y,vk)>2s. That is, d(x,y)+⋯+d(x,y) (k times) >2s or kr>2s, a contradiction. Therefore, any set distinct from V which is a median set cannot contain two eccentric vertices. Also, M((a,b))=V, since a and b are diametrical and I(a,b)=V. Hence the only median set of C2r which contains a vertex and its eccentric vertex is V.Theorem 2.17.
For the even cycleC2r, mn(C2r)≤3r.Proof.
LetV be the vertex set of C2r with V={v1,…,v2r}. Let A= {S:S⊆V and S does not contain any pair of eccentric vertices}. By the above lemma, the set of all median sets is a subset of A∪{V}. Hence mn(C2r)≤|A|+1. Let Bi={vi,vi+r}, 1≤i≤r. Now A consists of all subsets of V which does not simultaneously contain both the elements from the same Bi, 1≤i≤r. The number of ways of choosing a k-element subset of V so that it belongs to A is the product of the number of ways of choosing kBi's from the rBi's and the number of ways of choosing one element from each of these chosen Bi's. That is, (rk)×2k. Therefore |A|=∑k=1r‍(rk)×2k. Hence mn(C2r)≤(∑1≤k≤r‍(rk)×2k)+1=∑0≤k≤r‍(rk)×2k = 3r.


## 3.  Conclusion

In this paper, we could identify the median set of certain classes of graphs and evaluate their median numbers. Identifying the median sets of more classes of graphs and finding their median numbers will be interesting and challenging. Another possibility is the realisation problem; given a number of finding a graph whose median number is that number.



---

*Source: 583671-2012-11-21.xml*