Search

The median of a graph consists of those vertices which minimize the average distance to all other vertices. It plays an important role in optimization scenarios like facility location problems. Sierpinski graphs are the state graphs of the Switching Tower of Hanoi problem, a variant of the Tower of Hanoi game. They also provide optimum models for interconnection networks. In this study, we present our observations on the median of Sierpinski graphs. We conjecture that the number of median vertices in S 3 n is always 12, if n ≥ 3 , and that they lie around the inner ring of the standard drawing.

The axiomatic study on the interval function, induced pathfunction of a connected graph is a well-known area in metric graph theory. In this paper, we present a new axiom: ( b p ) for any x , y , z ∈ V , R ( x , y ) = { x , y } ⇒ y ∈ R ( x , z ) or x ∈ R ( y , z ) . We study axiom ( b p ) on the interval function and the induced path function of a connected, simple and finite graph. We present axiomatic characterizations of the interval function of bipartite graphs and complete bipartite graphs. We extend the characterization of the interval function of bipartite graphs to arbitrary bipartite graphs including disconnected bipartite graphs. In addition, we present an axiomatic characterization of the interval function of a forest. Finally, we present an axiomatic characterization of the induced path function of a tree or a 4-cycle using the axiom ( b p ) .

The axiomatic study on the interval function, induced path function and all-paths function of a connected graph is a well-known area in metric graph theory and related areas. In this paper, we introduce the following new axiom: (cp) v ∈ R ( u , w ) and v ∈ R ( u , x ) ⇒ w ∈ R ( v , x ) or x ∈ R ( v , w ) , for all distinct u , v , w , x ∈ V . We present characterizations of (claw, paw)-free graphs using axiom (cp) on the standard path transit functions on graphs, namely the interval function, the induced path function, and the all-paths function. We study the underlying graphs of the transit functions which are (claw, paw)-free and Hamiltonian. We present an axiomatic characterization of the interval function on (claw, paw)-free graphs. Furthermore, we obtain an axiomatic characterization of the induced path function on a subclass of (claw, paw)-free graphs.

The center function is defined on a connected graph G, where the input is any finite sequence of vertices of G and the output is the set of all vertices that minimize the maximum distance to the entries of the input. If the input is a sequence containing each vertex of G once, then the output is just the classical center of G. In the axiomatic approach, one wants to establish a set of properties or consensus axioms that characterize the function. We refer to an axiom as a universal axiom if the center function satisfies this axiom on any connected graph. In a previous paper, our focus was on classes of graphs on which we were able to characterize the center function in terms of universal axioms. In this paper, the focus is on classes of graphs on which these universal axioms do not characterize the center function. We introduce non-universal axioms that, together with some universal axioms, provide new characterizations of the center function: on cocktail party graphs, on complete bipartite graphs, and on block graphs.

A median (antimedian) of a profile of vertices on a graph G is a vertex that minimizes (maximizes) the sum of the distances to the elements in the profile. The median (antimedian) function has as output the set of medians (antimedians) of a profile. It is one of the basic models for the location of a desirable (obnoxious) facility in a network. 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 an axiomatic characterization is obtained for the median and antimedian function on complete graphs minus a matching.

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229–236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.

The median of a profile @p=(u"1,...,u"k) of vertices of a graph G is the set of vertices x that minimize the sum of distances from x to the vertices of @p. It is shown that for profiles @p with diameter @q the median set can be computed within an isometric subgraph of G that contains a vertex x of @p and the r-ball around x, where r>[email protected]@q/|@p|. 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.