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 Kp − e, Kp,q forP > 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.

Clique Irreducibility and Clique Vertex Irreducibility of Graphs

A graphs G is clique irreducible if every clique in G of size at least two,has an edge which does not lie in any other clique of G and is clique reducible if it is not clique irreducible. A graph G is clique vertex irreducible if every clique in G has a vertex which does not lie in any other clique of G and clique vertex reducible if it is not clique vertex irreducible. The clique vertex irreducibility and clique irreducibility of graphs which are non-complete extended p-sums (NEPS) of two graphs are studied. We prove that if G(c) has at least two non-trivial components then G is clique vertex reducible and if it has at least three non-trivial components then G is clique reducible. The cographs and the distance hereditary graphs which are clique vertex irreducible and clique irreducible are also recursively characterized.

On the remoteness function in median graphs

A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x 2 V.G/ the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and m edges, decides in O.mlog n/ time whether G is a median graph with geodetic number 2

Mathematical Morphology on Hypergraphs Using Vertex-Hyperedge Correspondence

The focus of this paper is to develop computationally efficient mathematical morphology operators on hypergraphs. To this aim we consider lattice structures on hypergraphs on which we build morphological operators. We develop a pair of dual adjunctions between the vertex set and the hyperedge set of a hypergraph , by defining a vertex-hyperedge correspondence. This allows us to recover the classical notion of a dilation/erosion of a subset of vertices and to extend it to subhypergraphs of . This paper also studies the concept of morphological adjunction on hypergraphs for which both the input and the output are hypergraphs

On The Center Sets and Center Numbers of Some Graph Classes

For a set S of vertices and the vertex v in a connected graph G, max x2S d(x, v) is called the S-eccentricity of v in G. The set of vertices with minimum S-eccentricity is called the S-center of G. Any set A of vertices of G such that A is an S-center for some set S of vertices of G is called a center set. We identify the center sets of certain classes of graphs namely, Block graphs, Km,n, Kn −e, wheel graphs, odd cycles and symmetric even graphs and enumerate them for many of these graph classes. We also introduce the concept of center number which is defined as the number of distinct center sets of a graph and determine the center number of some graph classes

Median graphs, the remoteness function, periphery transversals, and geodetic number two

A periphery transversal of a median graph G is introduced as a set of vertices that meets all the peripheral subgraphs of G. Using this concept, median graphs with geodetic number 2 are characterized in two ways. They are precisely the median graphs that contain a periphery transversal of order 2 as well as the median graphs for which there exists a profile such that the remoteness function is constant on G. Moreover, an algorithm is presented that decides in O(mlog n) time whether a given graph G with n vertices and m edges is a median graph with geodetic number 2. Several additional structural properties of the remoteness function on hypercubes and median graphs are obtained and some problems listed