Median Sets and Median Number of a Graph

A profile 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 , for , 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. 1. Introduction We consider only nonempty finite simple undirected connected graphs. For the graph , , and denote its vertex set and edge set, respectively. When the underlying graph is obvious, we will use and for and , respectively. A finite sequence of vertices is called a profile. For the profile and , the remoteness is [1]. The set of all vertices for which is minimum is the median of in and is denoted by . A set such that for some profile is called a Median set of . The Interval between vertices and of consists of all vertices which lie in some shortest path between and . The number of intervals of a graph is denoted by in . The Hypercube is the graph with vertex set , two vertices being adjacent if they differ exactly in one coordinate. A Subcube of the hypercube is an induced subgraph of , isomorphic to for some . A graph is a Median graph if, for every , 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 vertices formed by joining all the vertices of a -cycle to a vertex is a wheel graph and is denoted by . The vertex which is joined to all the vertices of the -cycle is the universal vertex. The Cartesian product of two graphs and has vertex set , two vertices and being adjacent if either and or and . The eccentricity of a vertex is . A vertex is an eccentric vertex of if . 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