包含所有固定阶数k树的一类图_翟冬阳.pdf

：包含所有固定阶数 树的一类图翟冬阳 曾德炎三亚学院理工学院 海南三亚 摘 要：图 是 树当且仅当 是一个顶点数为 的完全图，或者在图 中能找到度为 的点，使得与 相邻的 个点构成的点集为团，且 也是一个 树。设 是一个顶点数为 的 树，其中，。本文构造了一类新的图包含 作为子图。关键词：树；完全图；子图中图分类号：文献标识码：一、介绍本文所研究的图都是简单图。在本文中，一个图的阶数是指这个图的顶点的个数。我们用、和，表示 阶路、阶完全图以及 阶完全二部图。用表示 阶完全图的补图。设、为两个简单图，记（，）（），（）。表示顶点集为（）（），边集为（）（）的图。表示顶点集为（）（），边集为（）（）（，）的图。设（），（），那么（）表示在 中与 相邻的点所构成的点集。用 表示在图 中由点集 所诱导的子图。记（），（）。用（）表示在 的基础上删除掉图 对应的边所得到的图。在本文出现，未定义的标记参考文献。图 是 树当且仅当 是一个顶点数为 的完全图，或者在 中能够找到度为 的点，使得与 相邻的 个点构成的点集为团，且 也是一个 树。树就是我们通常所说的树。在 树中我们把度为 的顶点称为这个 树的耳朵。显然，对于任意一个顶点为 的 树，若，则都能在某个顶点数为 的 树 的基础上增加一个度为 的新顶点，让 与 中某 个阶团中的顶点，均连边构造而成。我们称这个过程为将耳朵 粘贴到团，上。设（，）。显然，（，）是一个顶点数为，耳朵数为 的 树，并且是同一个团被这 个耳朵粘贴。设 是一个顶点数为 的 树，其中，设（），其中，。我们设，其中，。对于，分别构造三类图如下：当 时，（）构造如下：设（），（）是在图 的基础上增加新的点，并让与，连边构造而成，其中 。显然图（）有 个顶点。当，时，（）构造如下：设（），（）是在图 的基础上增加新的点，并让 与，连边构造而成，其中 。显然图（）有 个顶点。当，时，（）的构造如下：设（），（）是在图 的基础上增加新的点，并让 与，连边构造而成，这里 。显然图（）有 个顶点。曾德炎证明了这三类图分别包含对应顶点数的所有 树作为子图，得到了下面三个定理：定理：设 是任意一个顶点数为 的 树，其中，则（）包含 作为子图。定理：设 是任意一个顶点数为 的 树，其中，则（）包含 作为子图。定理：设 是任意一个顶点数为 的 树，其中，则（）包含 作为子图。设 是一个顶点数为 的 树，其中。设 （），其中，。为了方便，我们设，其中，。对于，和 这三种情形，我们分别构造（，），（，）和（，）三类图如下：当 时，构造（，）如下：设（），（，）是在 的基础上增加新的点，并让 与，连边构造而成，这里 。显然图（，）有 个顶点。当 时，构造（，）如下：设（），（，）是在（）的基础上增加新的顶点，并让 与，连边构造而成，这里 。显然图（，）有 个顶点。当 时，这里 ，构造（，）如下：设（），（，）是在 的基础上增加新的点，并让 与，连边构造而成，这里 。显然（，）的顶点数为。图 为（，）。科技风 年 月科教论坛图 （，）最近我们将定理 中关于 树的结论推广到了 树，得到了相应的定理：定理：设 是任意一个顶点数为 的 树，其中，则图（，）包含 作为子图。定理：设 是任意一个顶点数为 的 树，其中，。则图（，）包含 作为子图。定理：设 是任意一个顶点数为 的 树，其中，。则图（，）包含 作为子图。当顶点数 时，我们构造了一个新的图 （）()，显然该图的顶点数为。记（，）（）()。以下的定理 是本文的主要结论：定理：设 是一个顶点数为 的 树，其中。则（，）包含 作为子图。当 ，时，（，）（，）（）()，如图 所示。它是包含所有 个顶点的 树作为子图。图 （）()二、证明为了证明定理，我们用到下面这个已知的结论：定理：设 是一个 阶的 树。则：（）中的耳朵数大于等于；（）中度为 的顶点都是 的耳朵；（）若 不是顶点数为 的完全图，那么在 中的任意两个耳朵均不相邻；（）中不包含长度大于等于 的无弦圈；（）中不包含顶点数为 的完全图。为证明定理，我们还需要下面的一些引理：引理：设 是一个顶点数为 的 树，则存在（），其中 存在整数 满足 ，使得 是，的子图。证明：设，是 中所有耳朵构成的集合。显然，。设。若，则（，），且。令（），则 。显然，当 时，是，的子图。若，则，且在 中有 个不同的。由于 中有 个顶点，并且每个顶点与 中的一个 相邻，则至少存在两个不同的顶点，使得（）（）。令（）（），显然 是，的子图。从而，当 时，是，的子图。若 ，则 是某个顶点数为 的 树。设 是 的一个耳朵，其中（）。由于 不是 的一个耳朵，所以在 中至少有一个顶点与 相邻，即。若，由于 中至少有两个耳朵，设 是 的另一个耳朵。因为 也不是 的耳朵，所以（）。不妨设（），由，有（），从而、（）。因为 是 的耳朵，有（），从而（）。这与定理（）顶点数大于等于 的 树中的任意两个耳朵互不相邻矛盾。因此，。由 ，有 。令（），由于在 中由顶点集（）诱导的子图为，有 是，的子图。引理得证。科教论坛科技风 年 月引理：设 是一个顶点数为 的 树，其中。若（），那么 是某个顶点数为 的 树的子图。证明：我们对 用归纳法。当 时，由于 是唯一一个顶点数为 的 树，且 的顶点数为，从而 是 的子图，也就是说 是某个顶点数为 的 树的子图。因此引理 对于 的情形是成立的。假设，设 是 的一个耳朵，则 是一个顶点数为 的 树，也就是说引理 对于这种情形成立。因此假设 不是 的耳朵，设 是 的一个耳朵。若 与 相邻，记，则 是一个顶点数为 的 树。因为（）（），所以 是 的一个子图，从而 是某个顶点数为 的 树 的子图。若 与 不相邻，由 是 阶 树，根据归纳假设可知，是某个顶点数为 的 树 的子图。显然（）（）且在 中由顶点集（）诱导的子图是顶点数为 的完全图。我们在 的基础上构造一个新图。是在 树 的基础上增加一个新的顶点，并让 与（）中的任意一个顶点都相邻。显然 就是在顶点数为 的 树 的基础上增加了一个新的耳朵。也就是说 是一个顶点数为 的 树，同时 是 的子图。引理得证。引理：设 是一个顶点数为 的 树，这里。设（），其中 中顶点的个数为，这里 。则 某个顶点数为 的 树的子图。证明：我们对 用归纳法。由引理 可以得到，引理 对于 的情形成立。我们现假设 （）。设 是 中的一个点，根据归纳假设可知（）是某个顶点数为（）的 树 的子图。根据引理 可知 是某个顶点数为 的 树 的子图。由 是 的一个子图，从而有 也是某个顶点数为 的 树 的生成子图。引理得证。定理 的证明：设 是一个顶点数为 的 树，其中。我们对 用归纳法。为了方便描述，在（，）（）()中我们记（），（），。若，则（）。根据引理，存在（），其中，存在整数 满足 ，使得 是，的子图。令 （，），则（）。显然，对于满足 的任意整数，均有 包含，作为子图。因此，包含 作为子图。我们将 中的 放置到 中的，上，由（）（）（），有（，）包含 作为子图。若，根据引理，在 中存在一个耳朵，使得（）是某个顶点数为 的 树的子图。令（，），则（），从而 包含所有 个顶点的 树作为子图。因此 包含（）作为子图。我们将 中的点集（）与点 对应放置到 中的点集，与点 上，有（，）包含 作为子图。若，根据引理，在 中存在一个耳朵，使得（）是某个顶点数为（）（）的 树的子图。令（，），则（）（）（）()。根据归纳假设 包含所有（）（）的个顶点 树的子图，由于（）是某个顶点数为（）（）的 树的子图，从而有 包含（）作为子图。我们将 中的点集（）与点 对应放置到 中的点集，与点 上，有（，）包含 作为子图。证毕。参考文献：，：，：，（）：曾德炎，翟冬阳关于 树子图的一些性质黑龙江科学，：曾德炎，翟冬阳包含所有固定阶数 树作为子图的图的构造科技风，：翟冬阳，曾德炎包含所有固定阶数 树作为子图的图的构造科研管理，：基金项目：海南省自然科学基金项目“关于可图序列的一类极值问题的研究”（）；青年教师专项培养科研项目“关于两类特殊图蕴含函数的研究”（）作者简介：翟冬阳（），女，汉族，辽宁辽阳人，硕士，讲师，研究方向：图论及其应用的研究；曾德炎（），男，汉族，湖北荆州人，硕士，副教授，研究方向：图论及其应用。科技风 年 月科教论坛