关于非广义多边形路的2连通简单MCD图  

On 2-connected Simple MCD-graphs Being not Generalized Polygon Paths

作　　者：施永兵[1] 

机构地区：[1]上海师范大学数学科学学院,上海200234

出　　处：《上海师范大学学报（自然科学版）》2000年第4期9-12,共4页Journal of Shanghai Normal University(Natural Sciences)

摘　　要：令 Sn 是具有 n个顶点没有两个等长圈的简单图的集合 .若 Sn 中不存在图 G′使|E(G′) |>|E(G) |,则称图 G是简单 MCD图 .若简单 MCD图 G是 2连通的 ,则称 G是 2连通简单 MCD图 .若 G中一条路 P的每个内点 v都有 d G(v) =2 ,则称 P为 G的简单路 .一个 2连通可平面图 G称为广义多边形路 ,如果用下述方法得到图 G*是路 :对应于 G的每个内部面 f (G是G的平图 )有一个 G*的顶点 f * ,G*的两个顶点 f*和 g*在 G*中相邻当且仅当 G中相应的两个内部面的边界交于一条 G的简单路 .作者证明了下述结果 :当且仅当 n∈ {1 0 ,1 1 ,1 4,1 5,1 6,2 1 ,2 2 }时 ,存在 n个顶点的非广义多边形路的 2连通简单 MCD图 .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 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 if G~* formed by the following method is a path Corresponding to each interior face f of ( is a plane graph 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 on a simple path of . We prove that there exists a 2-connected simple MCD-graph on n vertices being not a generalized polygon path if and only if n∈{10,11,14,15,16,21,22}.

关 键 词：圈 MCD图 连通简单图 非广义多边形路 

分 类 号：O157.5[理学—数学]