On 2-Connected Simple MCD Graph

Yongbing Shi, Hua Tang, Yincai Tang, and Lingliu Gong
Department of Applied Mathematics,
Shanghai Normal University, Shanghai 200234, P.R. China

Abstract

Let S_n be the set of a simple graph on n vertices in which no two cycles have the same length. A graph G in S_n is called a simple MCD graph if there exists no graph G' in S_n with |E(G')|>|E(G)|. In this paper, by discussing all the natural numbers except for 75 natural numbers, there are exactly 18 natural numbers, for each n of which, there exists a simple MCD graph on n vertices such that it is a 2-connected graph.