On 2-Connected Non-GPP Simple MCD Graphs

Yong-Bing Shi,Yin-Cai Tang, and Li Xu
Department of Applied Mathematics, Shanghai Normal University,
Shanghai 200234,
P.R.China

Abstract    
Let S_n be the set of simple graphs on n vertices in which no two cycles have the same length. A graph G in S_n is called a simple maximum cycle-distributed graph (simple MCD graph) if there exists no graph G' in S_n with |E(G')|>|E(G)|. A path P in G is called a simple path of G if, for each interior vertex v of P, d_G(v)=2. A planar graph G is called a generalized polygon path(GPP) if G* formed by the following method is a path: corresponding to each interior face f of ( is a plane graph of G) there is a vertex f* of G*; two vertices f* and g* are adjacent in G* if and only if the boundaries of the corresponding interior faces of intersect a simple path of . In this paper, we proved that there exists a simple MCD graph on n vertices such that it is a 2-connected graph being not a GPP if and only if n {10,11,14,15,16,21,22}.