跳到主要导航 跳到搜索 跳到主要内容

Two Classes of Simple MCD Graphs

  • Yong Bing Shi*
  • , Yin Cai Tang
  • , Hua Tang
  • , Ling Liu Gong
  • , Li Xu
  • *此作品的通讯作者
  • Shanghai Normal University

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

摘要

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.

源语言英语
主期刊名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
页177-188
页数12
DOI
出版状态已出版 - 2007
活动7th China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory, CJCDGCGT 2005 - Xi'an, 中国
期限: 22 11月 2005 → 24 11月 2005

丛书

姓名Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
卷4381 LNCS
ISSN(印刷版)0302-9743
ISSN(电子版)1611-3349

会议

会议7th China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory, CJCDGCGT 2005
国家/地区中国
市Xi'an
时期22/11/05 → 24/11/05

学术指纹

探究 'Two Classes of Simple MCD Graphs' 的科研主题。它们共同构成独一无二的学术指纹。

引用此