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