TY - GEN
T1 - Two Classes of Simple MCD Graphs
AU - Shi, Yong Bing
AU - Tang, Yin Cai
AU - Tang, Hua
AU - Gong, Ling Liu
AU - Xu, Li
PY - 2007
Y1 - 2007
N2 - 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 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 intersection of the boundaries of the corresponding interior faces of is a simple path of . In this paper, we prove 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}. We also prove that, 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.
AB - 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 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 intersection of the boundaries of the corresponding interior faces of is a simple path of . In this paper, we prove 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}. We also prove that, 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.
UR - https://www.scopus.com/pages/publications/49949091479
U2 - 10.1007/978-3-540-70666-3_19
DO - 10.1007/978-3-540-70666-3_19
M3 - 会议稿件
AN - SCOPUS:49949091479
SN - 3540706658
SN - 9783540706656
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 177
EP - 188
BT - Discrete Geometry, Combinatorics and Graph Theory 7th China-Japan Conference, CJCDGCGT 2005, Tianjin, China, November 18-20, 2005, Xi'an, China, November 22-24, 2005, Revised Selected Papers
T2 - 7th China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory, CJCDGCGT 2005
Y2 - 22 November 2005 through 24 November 2005
ER -