ＤＯＩ：１０．１９３９２／ｊ．ｃｎｋｉ．１６７１⁃７３４１．２０２３１１００６包含所有固定阶数ｋ树的一类图翟冬阳曾德炎三亚学院理工学院海南三亚５７２０２２摘要：图Ｇ是ｋ树当且仅当Ｇ是一个顶点数为ｋ＋１的完全图，或者在图Ｇ中能找到度为ｋ的点ｖ，使得与ｖ相邻的ｋ个点构成的点集为团，且Ｇ＼ｖ也是一个ｋ树。设Ｇ是一个顶点数为ｎ的ｋ树，其中ｎ＝ｐｋ＋ｐ＋１，ｐ⩾２。本文构造了一类新的图包含Ｇ作为子图。关键词：ｋ树；完全图；子图中图分类号：Ｏ１５７．５文献标识码：Ａ一、介绍本文所研究的图都是简单图。在本文中，一个图的阶数是指这个图的顶点的个数。我们用Ｐｍ、Ｋｍ和Ｋｍ，ｎ表示ｍ阶路、ｍ阶完全图以及ｍ＋ｎ阶完全二部图。用Ｋｍ表示ｍ阶完全图的补图。设Ｈ、Ｇ为两个简单图，记Ｅ（Ｈ，Ｇ）＝｛ｕｖ｜ｕ∈Ｖ（Ｈ），ｖ∈Ｖ（Ｇ）｝。Ｈ∪Ｇ表示顶点集为Ｖ（Ｈ）∪Ｖ（Ｇ），边集为Ｅ（Ｈ）∪Ｅ（Ｇ）的图。Ｈ∨Ｇ表示顶点集为Ｖ（Ｈ）∪Ｖ（Ｇ），边集为Ｅ（Ｈ）∪Ｅ（Ｇ）∪Ｅ（Ｈ，Ｇ）的图。设ｖ∈Ｖ（Ｇ），Ｘ⊆Ｖ（Ｇ），那么ＮＸ（ｖ）表示在Ｘ中与ｖ相邻的点所构成的点集。用Ｇ［Ｘ］表示在图Ｇ中由点集Ｘ所诱导的子图。记Ｇ＼ｖ＝Ｇ［Ｖ（Ｇ）＼ｖ］，Ｇ＼Ｘ＝Ｇ［Ｖ（Ｇ）＼Ｘ］。用Ｋｍ－Ｅ（Ｈ）表示在Ｋｍ的基础上删除掉图Ｈ对应的边所得到的图。在本文出现，未定义的标记参考文献［１］。图Ｇ是ｋ树当且仅当Ｇ是一个顶点数为ｋ＋１的完全图，或者在Ｇ中能够找到度为ｋ的点ｖ，使得与ｖ相邻的ｋ个点构成的点集为团，且Ｇ／ｖ也是一个ｋ树。１树就是我们通常所说的树。在ｋ树中我们把度为ｋ的顶点称为这个ｋ树的耳朵。显然，对于任意一个顶点为ｎ的ｋ树Ｇ，若ｎ≠ｋ＋１，则都能在某个顶点数为ｎ－１的ｋ树Ｇ＇的基础上增加一个度为ｋ的新顶点ｕ，让ｕ与Ｇ＇中某ｋ个阶团中的顶点ｖ１，ｖ２，…，ｖｋ均连边构造而成。我们称这个过程为将耳朵ｕ粘贴到团｛ｖ１，ｖ２，…，ｖｋ｝上。设Ｔ（ｋ，ｎ）＝Ｋｋ∨Ｋｎ－ｋ。显然，Ｔ（ｋ，ｎ）是一个顶点数为ｎ，耳朵数为ｎ－ｋ的ｋ树，并且是同一个团被这ｎ－ｋ个耳朵粘贴。设Ｇ是一个顶点数为ｎ的２树，其中ｎ⩾３，设ｎ≡ｑ（ｍｏｄ３），其中ｑ＝０，１，２。我们设ｎ＝３ｐ＋ｑ，其中ｑ＝０，１，２。对于ｑ＝０，１，２，分别构造三类图如下：当ｎ＝３ｐ时，Ｇ（３ｐ）构造如下：设Ｖ（Ｋ２ｐ）＝｛ｖ１，…，ｖ２ｐ｝，Ｇ（３ｐ）是在图Ｋ２ｐ的基础...
