关于一些特殊图类的弱控制多项式的研究.pdf

书 书 书 年月第卷第期四川师范大学学报（自然科学版）（），收稿日期：接受日期：基金项目：国家自然科学基金（、）和新疆维吾尔自治区自然科学基金联合项目（）通信作者简介：边红（），女，教授，主要从事图论与网络推断的研究，：引用格式：刘慧灵，边红，于海征，等关于一些特殊图类的弱控制多项式的研究四川师范大学学报（自然科学版），（）：关于一些特殊图类的弱控制多项式的研究刘慧灵，边红，于海征，魏丽娜（新疆师范大学数学科学学院，新疆乌鲁木齐；新疆大学数学与系统科学学院，新疆乌鲁木齐）摘要：研究一些特殊图类的弱控制多项式令图（），（）是一个简单连通图，若对任意（），存在（），使得（）且（）（）成立，则称弱控制设（）（），如果对任意（）（），存在（），使得弱控制，则称（）为图的一个弱控制集含点数最少的弱控制集称为最小弱控制集，最小弱控制集中所包含点的个数称为图的弱控制数，记为（）图的弱控制多项式为（，）（）（，），其中（，）表示图中阶为的弱控制集的个数关键词：控制集；弱控制集；弱控制数；控制多项式；弱控制多项式中图分类号：文献标志码：文章编号：（）：设图（），（）是简单连通图，（）和（）分别为图的顶点集和边集顶点集的阶是指该集合中包含的点的个数点（）的开邻集（）（）（），点（）的度（）（）图中度为的点称为悬挂点令（）（），对图的任意一点（）（），至少存在一个点（），使得（），则称（）为图的一个控制集图的控制多项式为（，）（）（，），其中，（，）为图中阶为的控制集的个数，最小控制集中点的个数称为图的控制数，记为（）如果对任意（），均存在（），使得（）且（）（）成立，则称强控制，或弱控制令（）（），如果对任意（）（），均存在（），使得弱控制，则称（）为图的一个弱控制集图的弱控制多项式为（，）（）（，），其中（，）为图中阶为的弱控制集的个数，包含点数最少的弱控制集称为最小弱控制集，最小弱控制集中点的个数称为图的弱控制数，记为（）年，等提出了图的强控制和弱控制这一概念，同时这篇文章也提到了等证明了与计算图的弱控制数相关的问题是完全问题 年，等定义了图的控制多项式，并给出了控制多项式的一些简单性质 年，计算了一些特殊图类的控制集及弱控制集的总数 年，等计算了一些特殊图的控制多项式 年，介绍了图的独立控制多项式，并得到了一些图类的独立控制多项式，建立了图的独立控制多项式的一些性质 年，等介绍和建立了完全图的弱控制集和弱控制多项式同年，研究出一些特殊图类的控制多项式、独立控制多项式和全控制多项式，并得到了一些它们的性质和部分系数的性质，对于部分特殊图类，也得到了一些计算这些多项式函数的新公式 年，徐保根等研究了图的强控制和弱控制问题，分别获得了图的强控制数和弱控制数的上界，并确定了几类特殊图的强控第期刘慧灵，等：关于一些特殊图类的弱控制多项式的研究 制数和弱控制数 年，包冠宇等先借助定理给出友谊图的全控制多项式根的极限曲线，而后证明了控制多项式的根在整个复平面上是稠密的 年，等得出了齐次毛虫形图和全二元树的完美控制多项式本文主要介绍了一些特殊图类的弱控制多项式，其中包括（，）棒棒糖图、舵图、花图、双星图、三角书图、友谊图、荷兰风车图主要结论如下定理（，）棒棒糖图，的弱控制多项式为（，）（）()定理舵图的弱控制多项式为（，）（）()()定理花图的弱控制多项式为（，）（）()()定理双星图，的弱控制多项式为（，）（）定理三角书图，的弱控制多项式为（，）（）定理友谊图的弱控制多项式为（，）（）()()定理荷兰风车图的弱控制多项式为（，）（）()()基本概念定义一个图称为（，）棒棒糖图，如图（），记作，如果它满足（，），（，），定义一个图称为与的积，如图（），记作，如果它满足（），（），图（，）棒棒糖图，和与的积（，）定义一个图称为舵图，如图（），记作，如果它满足（），（），其中边就是边定义一个图称为型太阳花图，如图（），记作：，如果它满足（），（），其中，边就是，边就是边图 阶舵图与阶型太阳花图 定义一个图称为花图，如图（），记作，如果它满足（），（），其中边就是边定义一个图称为型太阳花图，如图（），记作，如果它满足（），（），四川师范大学学报（自然科学版）第卷，其中边就是边图 阶花图与阶型太阳花图 定义 一个图称为双星图（图），记作，如果它满足（，），（，），图 阶双星图，定义一个图称为三角书图（见图），记作，如果它满足（，），（，），图 阶三角书图，定义一个图称为友谊图（见图），记作，如果它满足（），（），图 阶友谊图 定义一个图称为荷兰风车图（见图），记作，如果它满足（），（），图 阶荷兰风车图 主要结果定理令，为 阶（，）棒棒糖图，则（，）棒棒糖图，的弱控制多项式为（，）（）()证明令，为 阶（，）棒棒糖图，（，），（，），因为为悬挂点，故点一定在弱控制集中，此时对于图，共 个点均未被弱控制，而为最大度点，不能弱控制图上其余各点，点，均彼此相邻，第期刘慧灵，等：关于一些特殊图类的弱控制多项式的研究 且（）（）（），因此图，的最小弱控制集（，），故（，），（，）()对于图，阶为的弱控制集（，），若所选的点中包含点，例如（，），那么，均被弱控制，故（，）()类似地，对于图，阶为的弱控制集（，），故（，）()综上所述（，）（）()图与的积，是由（，）棒棒糖图将，的每个点分别添加一个悬挂点构成的根据定理，自然可以给出的弱控制多项式推论令为与的积，则的弱控制多项式为（，）（）()证明令为与的积，（），（），因为，均为悬挂点，故，一定在弱控制集中，此时图的剩余个点，均被弱控制因此图的最小弱控制集（），故（），（，）对于图，阶为 的弱控制集（），故（，）()类似地，对于图，阶为 的弱控制集（），故（，）()综上所述（，）（）()定理令为 阶舵图，则舵图的弱控制多项式为（，）（）()()证明令为 阶舵图，（），（），其中边就是边因为，为悬挂点，故点，一定在弱控制集中，此时对于图，点未被，弱控制，因此，的最小弱控制集第一种类型是（），第二种类型是（），故（），（，）()()对于图，阶为 的弱控制集第一种类型是（），第二种类型是（），故（，）()()综上所述（，）()()()()()（）()()型太阳花图，是由舵图将点与点之间添加一条边构成的，其中，边就是根据定理，自然可以给出的弱控制多项式推论令为 阶型太阳花图，则型太阳花图的弱控制多项式为（，）（）()()证明令为 阶型太阳花图，（），（），其中，边就是，边就是边因为，均为最小度点且互不相邻，故点，一定在弱控制集中，此时 四川师范大学学报（自然科学版）第卷对于图，点未被，弱控制，因此的最小弱控制集第一种类型是（），第二种类型是（），故（），（，）()()对于图，阶为 的弱控制集第一种类型是（），第二种类型是（），故（，）()()综上所述（，）()()()()()（）()()定理令为 阶花图，则花图的弱控制多项式为（，）（）()()证明令为 阶花图，（），（），其中边就是边因为，为的最小度点且互不相邻，故点，一定在弱控制集中，此时点，均被弱控制，因此图的最小弱控制集是（），故（），（，）对于图，阶为 的弱控制集第一种类型是（），第二种类型是（），故（，）()()类似地，对于图，阶为 的弱控制集第一种类型是（），第二种类型是（），故（，）()()综上所述（，）()()()()()()()（）()()型太阳花图，是将花图的中心点添加个悬挂点，构成的根据定理，自然可以给出的弱控制多项式推论令为 阶型太阳花图，则型太阳花图的弱控制多项式为（，）（）()()证明令为 阶型太阳花图，（），（），其中边就是边因为，为悬挂点，故点，一定在弱控制集中因为（），且（）（）（），故点，一定在弱控制集中，此时点，均被弱控制，因此图的最小弱控制集是（），故（），（，）对于图，阶为 的弱控制集第一种类型是（），第二种类型是（），故（，）()()类似地，对于图，阶为 的弱控制集第一种类型是（），第二种类型是（），故（，）()()综上所述（，）()()()()()()()第期刘慧灵，等：关于一些特殊图类的弱控制多项式的研究（）()()定理令，为 阶双星图，则双星图，的弱控制多项式为（，）（）证明令，为 阶双星图，（，），（，），因为，为悬挂点，故点，一定在弱控制集中，此时点，均被弱控制，因此图，的最小弱控制集是（，），故（，），（，）对于图，阶为 的弱控制集是由从，中任选一个点，与，共同构成的，故（，）综上所述（，）（）（）对于图，若，则（，），（，）（）定理令，为 阶三角书图，则三角书图，的弱控制多项式为（，）（）证明令，为 阶三角书图，其中，为圈的个拷贝，（，），（，），因为，为，的最小度点且互不相邻，故点，一定在弱控制集中，此时点，均被弱控制，因此图，的最小弱控制集是（，），故（，），（，）对于图，阶为 的弱控制集是从，中任选一个点，与，共同构成的，故（，）综上所述（，）（）定理令为 阶友谊图，则友谊图的弱控制多项式为（，）（）()()证明令为 阶友谊图，其中，为圈的个拷贝，（），（），图的最小弱控制集（），故（），（，）对于图，阶为 的弱控制集第一种类型是（），第二种类型是（），故（，）()()类似地，对于图，阶为 的弱控制集第一种类型是（），第二种类型是（），故（，）()()综上所述（，）（）()()定理令为 阶荷兰风车图，则荷兰风车图的弱控制多项式为（，）（）()()证明令为 阶荷兰风车图，其中，为圈的个拷贝，（），（），因为，为的最小度点且互不相邻，故点，一定在弱控制集中，此时点未被，弱控制，因此图的最小弱控制集第一种类型是（），第二种类型是（），故（），四川师范大学学报（自然科学版）第卷（，）()()类似地，阶为 的弱控制集第一种类型是（），第二种类型是（），故（，）()()综上所述（，）（）()()致谢新疆师范大学年一流专业、年一流课程项目对本文给予了资助，谨致谢意参考文献，（）：，：，（）：?，（）：，：，（）：，（）：关于某些特殊图的三类多项式和拓扑指标的研究武汉：华中师范大学，徐保根，李广，张君霞关于图的强（弱）控制数数学的实践与认识，（）：包冠宇，刘丽全控制多项式的零点分布曲阜师范大学学报（自然科学版），（）：，（）：，（，；，）：（），（）（），（）（）（）（），（）（），（）（），（），（）（）（，）（）（，），（，）：；：（编辑陶志宁）