Strongly distance-balanced graphs and graph products

A graph G is strongly distance-balanced if for every edge uv of G and every i 0 the number of vertices x with d.x; u/ D d.x; v/ 1 D i equals the number of vertices y with d.y; v/ D d.y; u/ 1 D i. It is proved that the strong product of graphs is strongly distance-balanced if and only if both factors are strongly distance-balanced. It is also proved that connected components of the direct product of two bipartite graphs are strongly distancebalanced if and only if both factors are strongly distance-balanced. Additionally, a new characterization of distance-balanced graphs and an algorithm of time complexity O.mn/ for their recognition, wheremis the number of edges and n the number of vertices of the graph in question, are given

Axiomatic Characterization of the Antimedian Function on Paths and Hypercubes

An antimedian of a pro le = (x1; x2; : : : ; xk) of vertices of a graph G is a vertex maximizing the sum of the distances to the elements of the pro le. The antimedian function is de ned on the set of all pro les on G and has as output the set of antimedians of a pro le. It is a typical location function for nding a location for an obnoxious facility. The `converse' of the antimedian function is the median function, where the distance sum is minimized. The median function is well studied. For instance it has been characterized axiomatically by three simple axioms on median graphs. The median function behaves nicely on many classes of graphs. In contrast the antimedian function does not have a nice behavior on most classes. So a nice axiomatic characterization may not be expected. In this paper such a characterization is obtained for the two classes of graphs on which the antimedian is well-behaved: paths and hypercubes.

Simultaneous Embeddings Of Graphs As Median And Antimedian Subgraphs

The distance DG(v) of a vertex v in an undirected graph G is the sum of the distances between v and all other vertices of G. The set of vertices in G with maximum (minimum) distance is the antimedian (median) set of a graph G. It is proved that for arbitrary graphs G and J and a positive integer r 2, there exists a connected graph H such that G is the antimedian and J the median subgraphs of H, respectively, and that dH(G, J) = r. When both G and J are connected, G and J can in addition be made convex subgraphs of H.

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.

Almost Self-Centered Median And Chordal Graphs

Almost self-centered graphs were recently introduced as the graphs with exactly two non-central vertices. In this paper we characterize almost selfcentered graphs among median graphs and among chordal graphs. In the first case P4 and the graphs obtained from hypercubes by attaching to them a single leaf are the only such graphs. Among chordal graph the variety of almost self-centered graph is much richer, despite the fact that their diameter is at most 3. We also discuss almost self-centered graphs among partial cubes and among k-chordal graphs, classes of graphs that generalize median and chordal graphs, respectively. Characterizations of almost self-centered graphs among these two classes seem elusive

The median function on graphs with bounded profiles

The median of a profile = (u1, . . . , uk ) of vertices of a graph G is the set of vertices x that minimize the sum of distances from x to the vertices of . It is shown that for profiles with diameter the median set can be computed within an isometric subgraph of G that contains a vertex x of and the r -ball around x, where r > 2 − 1 − 2 /| |. The median index of a graph and r -joins of graphs are introduced and it is shown that r -joins preserve the property of having a large median index. Consensus strategies are also briefly discussed on a graph with bounded profiles.

On the generalized obnoxious center problem: antimedian subsets

The set of vertices that maximize (minimize) the remoteness is the antimedian (median) set of the profile. It is proved that for an arbitrary graph G and S V (G) it can be decided in polynomial time whether S is the antimedian set of some profile. Graphs in which every antimedian set is connected are also considered.

Equal opportunity networks, distance-balanced graphs, and Wiener game

Given a graph G and a set X ⊆ V(G), the relative Wiener index of X in G is defined as WX (G) = {u,v}∈X 2  dG(u, v) . The graphs G (of even order) in which for every partition V(G) = V1 +V2 of the vertex set V(G) such that |V1| = |V2| we haveWV1 (G) = WV2 (G) are called equal opportunity graphs. In this note we prove that a graph G of even order is an equal opportunity graph if and only if it is a distance-balanced graph. The latter graphs are known by several characteristic properties, for instance, they are precisely the graphs G in which all vertices u ∈ V(G) have the same total distance DG(u) = v∈V(G) dG(u, v). Some related problems are posed along the way, and the so-called Wiener game is introduced.

Betweenness Centrality in Some Classes of Graphs

There are several centrality measures that have been introduced and studied for real world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest path between them. In this paper we present betweenness centrality of some important classes of graphs.

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

Morphological filtering on hypergraphs

The focus of this article 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 hyper edge set of a hypergraph H, 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 H. Afterward, we propose several new openings, closings, granulometries and alternate sequential filters acting (i) on the subsets of the vertex and hyperedge set of H and (ii) on the subhypergraphs of a hypergraph

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

Fair Sets of Some Classes of Graphs

Given a non empty set S of vertices of a graph, the partiality of a vertex with respect to S is the di erence between maximum and minimum of the distances of the vertex to the vertices of S. The vertices with minimum partiality constitute the fair center of the set. Any vertex set which is the fair center of some set of vertices is called a fair set. In this paper we prove that the induced subgraph of any fair set is connected in the case of trees and characterise block graphs as the class of chordal graphs for which the induced subgraph of all fair sets are connected. The fair sets of Kn, Km;n, Kn e, wheel graphs, odd cycles and symmetric even graphs are identi ed. The fair sets of the Cartesian product graphs are also discussed

Consensus strategies for signed profiles on graphs

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 f+; g. 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

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