The decay number and the maximum genus of diameter 2 graphs

Abstract

Let zeta (G) (resp. xi (G)) be the minimum number of components (resp. odd size components) of a co-tree of a connected graph G. For every 2-connected graph G of diameter 2, it is known that m(G)greater than or equal to 2n(G) - 5 and xi (G)less than or equal to zeta (G)less than or equal to4. These results define three classes of extremal graphs. In this paper, we prove that they are the same, with the exception of loops added to vertices. (C) 2001 Elsevier Science B.V. All rights reserved. MSC: Primary 05C10; Secondary 05C70.