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
Description:
TAIWANESE JOURNAL OF MATHEMATICS
Vol. 16, No. 5, pp. 1911-1922, October 2012
The median (antimedian) set of a profile π = (u1, . . . , uk) of vertices of a
graphG is the set of vertices x that minimize (maximize) the remoteness i d(x,ui ).
Two algorithms for median graphs G of complexity O(nidim(G)) are designed,
where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other
algorithm which in addition computes antimedian sets and remoteness functions and
works in all partial cubes
Description:
Algorithmica (2010) 57: 207–216
DOI 10.1007/s00453-008-9200-4
Kannan, Balakrishnan; Sandi, Klavzar; Manoj, Changat(Elsevier, December 31, 2007)
[+]
[-]
Abstract:
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.
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