fccjxxw.com
非常超级学习网 学习超级帮手
当前位置:首页 >> 建筑/土木 >>

Euler生成子图极大边数的一些结果与问题


Euler 生成子图极大边数的一些结果与问题
李登信 李宵民 (重庆工商大学数学与统计学院,重庆 400067) 用 O (G ) 表示图 G 的奇顶点组成的集合, O (G ) = φ 的图称为偶图 ;连通的 偶图称为欧拉图。 G 存在欧拉生成子图, 图 则称 G 是超欧拉图 (supereulerian) 。 我们常用 SL 表示全体超欧拉图组成的集合。 早在 1983 年,Bermond,Jackson,Jaeger 等人得到了如下结果: 定理 每个 2-边连通图 G 都存在偶子图 H ,使得 | E(H ) | 2 ≥ 。[1] | E (G ) | 3

关于 Euler 生成子图的极大边数问题, P. A. Catlin 注意到 3-正则图的情 形,曾经猜想:若 G 是超欧拉图,则 G 存在一个欧拉生成子图 H ,使得 | E(H ) | 2 ≥ 。 [2] | E (G ) | 3 1995 年,赖虹建(Hong-Jian Lai) 、陈志宏(Zhi-Hong Chen)等人提出如 下公开问题[3] 问题 1 决定 L = min max{
G∈SL ?{ K1 }

| E(H ) | : H是G的一个Euler生成子图} | E (G ) |
2 。在文献[4]中,我们提出猜想: 3

2001 年,我们在[3]中给出例子说明 L < 猜想 1 设 G 是简单图,则 L = 问题 2 得

3 。 5 是否存在超欧拉图 G ,G 有一个极大(边数最多)欧拉生成子图 H ,使

| E(H ) | 3 = ? | E (G ) | 5

1 关于 L 的一些结果 ,若存在一个极大欧拉生成子图 H,使得 定理 1 对于简单图图 G(非欧拉图) * |E(H)|/|E(G)|=α,则一定存在图 G ,使得|E(H*)|/|E(G*)|<α,其中 H*为 G*的 极大欧拉生成子图。 (2003 年,[5]) 定理 1 说明: L 不可达到。 定理 2 设 G 是超欧拉图, O(G ) 表示图 G 的奇顶点组成的集合, | O(G ) |= 2k 。
2 。 3

下列每一个断言成立: (2005 年,[6]) (1) 若 k ≤ 3 , G 是简单图,则 L =

(2) 若 k ≥ 4 , G 是简单图,则 L ≤ (3) 若 G 允许有重边,则 L = 定理 3
1 。 2

3 。 5

设 G 是有 n 个点的简单图, G ∈ SL 。如果 δ (G ) ≥

n ? 1 (b ∈ {4, 5}) ,且 b

3 。 (2006 年,[7]) 5 对于超欧拉图有下列著名定理[8]: 定理 4 若图 G 含两棵边不相交的生成树,则 G 是超欧拉图。 我们曾提出如下问题: 猜想 2:设 G 是简单图,G 含两棵边不相交的生成树,则 G 存在一个欧拉生成子 n > 4b ,则 L ≥

图 H ,使得

| E(H ) | 2 ≥ 。 | E (G ) | 3

的任若 | V (G ) |= 4 ,G 含两棵边不相交的生成树,则 G = K 4 。增加一个点 v , 设 u, w 是 K 4 意两个点,增加两条边 vu, vw ,于是得到 5 个点的含两棵边不相交的 生成树的图,记为 G5 。类似地可得 6 个点的含两棵边不相交的生成树的图 G6 , 如此类推可得 n 个点的含两棵边不相交的生成树的图 G n 。参见图 1。

图 1 G n 的构成 设 F1 = {Gi | i ≥ 4} 。 在构造 G n 的过程中,用 u i , wi 表示 Gi 中的两个点, vi +1 表示在 Gi 中增加的一 个点,即
Gi +1 = Gi U {vi +1u i , vi +1 wi } , u i , wi ∈ V (Gi ), vi +1 ? V (Gi ), i ≥ 4 , G4 = K 4 。

若在构造 G n 的过程中,用 u i , wi 表示 Gi 中的两个相邻点, vi +1 表示在 Gi 中增 加的一个点,则得到 F1 的一个子集 F2 。即
F2 = {Gi | i ≥ 4, }

其中, Gi +1 = Gi U {vi +1u i , vi +1 wi } , u i wi ∈ E (Gi ), G4 = K 4 。

2

我们得到下列结果: 定理 5 若图 G ∈ F2 ,则 L ≥ 猜想 3
2 。 3 2 若图 G ∈ F1 ,则 L ≥ 。 3

2 用收缩方法来估计 L 设 H 是 G 的子图,图 G 关于子图 H 的收缩定义为:在 G 中,把 H 的点收缩为 一个点 v H ,去掉 H 的边,得到 G 关于子图 H 的收缩,记为 G 因为欧拉图的收缩仍为欧拉图,下列结论是显然的。 定理 6 设 H 是图 G 的子图,G 是超欧拉图,则 G 设 X 是 G 的子图, G L X = min max{ 因为图 G 问题。 问题 3 设 G 是超欧拉图,X 是 G 的子图, G X ≠ K 1 。当 X 满足什么条件时,由 X ≠ K 1 。令 H 也是超欧拉图。 H 。

| E(K ) | | K是G / X的欧拉生成子图} | E (G / X ) | 比图 G 简单,自然想到:可否用 L X 来估计 L ?于是我们有下列

X

L X ≥ a 可推出 L ≥ a ?这里 a 为给定的常数。
为了研究问题 2,我们引入下列定义: 定义 1 设 G 是超欧拉图, 是 G 的子图,G ≠ K 1 ,a 为给定的常数。 L X ≥ a X 若 X 可推出 L ≥ a ,则称子图 X 是 G 的一个 a —子图。 设 H 是图 G 的子图,我们用 H ? ke 表示去掉 H 中的任意 k 条边而得到的图。 对于 a —子图,我们得到一些结果。 2 定理 7 完全图 K n (n ≥ 3) 、完全二分图 K n, n (n ≥ 3) 是 —子图。 3 3 定理 8 K 4 ? e 是 —子图。 5 2 定理 9 K 5 ? 2e 是 —子图。 3 3 定理 10 K n, n ? e 是 —子图。 5 2 3 问题 4 决定 m,n 使 K n ? me 是 —子图或 —子图。 3 5 显然,确定更多的 a —子图,对于估计 Euler 生成子图的极大边数是有意义的。

3

参考文献 [1] Bermond,Jackson,and Jaeger, J.Combinatorial Theory,Ser.B35(1983) 297-308 [2] H.-J. Lai, Lecture Note on Supereulerian Graphs and Related Topics, 1996. [3] Z.-H. Chen, H.-J. Lai, Reduction techniques for supereulerian graphs and related topics-an update, in: Ku Tung-Hsin(Ed), Combinatorics and Graph Teory’95, World Scientific, ingapore, London, 1995, pp.53-69. [4] Dengxin Li, Deying Li, Jingzhong Mao, On maximum number of edges in a spanning eulerian subgraph, Discrete Mathematics 272(2004) 299-302. [5] 李霄民,李登信, 探索极大欧拉生成子图的一种方法,工程数学学报,21 (2004)1018-1020 [6] Dengxin Li,The Maximum Number of Edges of a Spanning Eulerian Subgraph in a Graph,Ars Combinatoris,(accepted ) to appear. [7] 李登信,关于 Euler 生成子图极大边数的一个注记,重庆工商大学学报(自 科版) ,2006,20(1) :1-5 [8] P. A. Catlin, A reduction method to find spanning eulerian subgraphs, J. of Graph Theory, Vol.12,No.1,29-24.

On Maximum Number of Edges in a Spanning Eulerian Subgraph Li Dengxin Li Xiaomin
(Chongqing Technology and Business University, Chongqing 400067)

4


更多相关文章:

非常超级学习网 fccjxxw.com

copyright ©right 2010-2021。
非常超级学习网内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图