熊玮，张启慧

(新疆大学 数学与系统科学学院，新疆 乌鲁木齐 830046)

0 引言

令G是一个简单无向图，用V(G)和E(G)分别表示图G的顶点集和边集.经过G的每条边的迹称为G的Euler迹，G的环游是指经过G的每条边至少一次的闭途径.欧拉环游是指经过每条边恰好一次的环游，包含欧拉环游的图称为欧拉图，欧拉图的度能被2整除.包含所有点的欧拉子图称为欧拉生成子图.例如文献[1]研究了Hamilton图的生成子图问题.若一个图不是欧拉的，也不含有生成欧拉子图，则考虑它是否可以加边成欧拉图，即欧拉生成母图.例如文献[2]研究了欧拉母图的树数条件.类似于欧拉生成母图的研究，我们首次研究度能被3整除的生成母图.

本文研究的内容是一般图以及树图是否存在度能被3整除的生成母图.随着图阶数的增加，每个图的度能被3整除的生成母图不唯一，所以研究增加边数最少满足要求的生成母图很有意义，即最优生成母图的构造.

1 各图类度能被3整除的生成母图

图G的顶点v的度记为dG(v).称G′是G的生成母图，如果V(G′)=V(G)，E(G′)⊇E(G).若H是G的子图，G中H的补图是指子图G−E(H)，记为H(G).包含G的每个顶点的路称为G的Hamilton路，G的Hamilton圈是指包含G的每个顶点的圈，包含Hamilton圈的图称为Hamilton图.未给出的术语见文献[3].

定义1一个图G的能被3整除的最优生成母图是指图G加最少的边得到的度能被3整除的生成母图，以下简称为最优母图.

定义2定义符号[d(v)]3，用来表示将顶点v的度增加至和d(v)最相近且大于d(v)的3的倍数.

定理[3]1设G为任意无向图，|E(G)|=ε，则

命题……