IMCS/Publications/CSJM/Issues/CSJM v.5, n.3 (15), 1997/

On graphs G of diameter two with f(G)J|V(G)|+D-d+1

Authors: A. Postaru


It is known that for any graph G there exists a graph H whose median is isomorphic to G: Med H @ G. For any graph G, let f(G) denote the minimal number of vertices of a connected graph H satisfying Med H @ G. It is known that if G of diameter two has n vertices and minimal (maximal) degree d(D) then f(G) і n+D-d. We constructed a wide class of graphs G of diameter two for which f(G) Ј n+D-d+1.

Andrei Postaru,
Department of
Mathematics and Cybernetics,
Moldova State University,
60, Mateevici str., Kishinev,


Adobe PDF document0.16 Mb