关于几乎唯一泛圈图  

On Almost Uniquely Pancyclic Graphs

作　　者：施永兵[1] 徐莉[1] 陈晓卿[1] 王敏[1] 

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

出　　处：《数学进展》2006年第5期563-569,共7页Advances in Mathematics（China）

基　　金：上海市教委科技发展基金(04DB25).

摘　　要：设G是阶为n的简单Hamilton图．若存在m（3≤m〈n）使对每个l∈{3，4，…，n}-{m}，G恰有一个长为l的圈且不含长为m的圈，则称G是几乎唯一泛圈图．用Гκ表示具看n＋κ条边和恰有互1（κ＋1）（κ＋2）个圈的简单H图的集合．用Г^＊κ表示具有n＋κ条边恰有2^κ＋κ个圈的简单外可平面H图的集合．本文确定了^-Гκ和Г^＊κ中所有几乎唯一泛圈图，并证明这些图都是简单MCD图．本文还构造了50个含有同胚于K4的子图的几乎唯一泛圈图，并提出了若干问题和猜想．Let G be a simple Hamilton graphs with n vertices. If there exists m（3 ≤ m 〈 n） such that G contains exactly one cycle of length l for every l∈ {3, 4,… n} - {m} and contains no cycle of length of m, then G is called almost uniquely pancyclic graph. Let ^-Гκ denote the set of simple Hamilton graphs with n ＋ κ edges and 1/2（κ ＋ 1）（κ ＋ 2） cycles. Let Г^＊κ denote the set of simple outplanar Hamilton graphs with n ＋ κ edges and （2^κ ＋κ） cycles. In this paper all almost uniquely pancyclic graphs in ^Гκand Г^＊κ are determined and it is proved that they are all simple MCD graphs. Fifty almost uniquely pancyclic graphs containing a subgraph homeomorphic to K4 are constructed, and three problems and one conjecture are posed.

关 键 词：圈 几乎唯一泛圈图 简单MCD图 

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