【摘 要】
:
确定图的色数(chromatic number)和团数(clique number)是图论中两个基本而重要的问题.虽然从理论上已经知道确定一般图的色数和团数都属于NP-hard的问题,确定一些特殊图的色
论文部分内容阅读
确定图的色数(chromatic number)和团数(clique number)是图论中两个基本而重要的问题.虽然从理论上已经知道确定一般图的色数和团数都属于NP-hard的问题,确定一些特殊图的色数和团数对图论工作者仍然具有莫大的吸引力.本工作的初始动机来源于对本原置换群的同步性的研究,这是当前置换群理论与代数图论中的一个前沿课题.2008年著名群论学家Peter Neumann指出一般本原群的同步性与其轨道图的色数和团数之间是否相等存在密切的关系.这一事实为本原置换群的同步性的研究开辟了一条新路,即从图论的角度来确定本原群的轨道图的色数和团数.当研究本原置换群的同步性时,其中一种重要类型是几乎单型本原群,而对称群S_n是其中最具代表性的一种.本工作我们研究对称群S_n在无序r-元子集上的诱导本原作用的轨道图的团数和色数.我们首先从S_n在无序r-元子集上的诱导本原作用的轨道图的定义出发,得到该轨道图与广义Johnson图的联系,进而由广义Johnson图的性质得到了相应的轨道图的团数和色数(范围).特别,本文先给出r = 2,3,4的情况,并将其推广至一般的情况.一个图的团数与色数对这个图本身而言是至关重要的,从一个图的团数可以看出一个图的结构,而色数则是对图的顶点进行了一个分类,这样我们对S_n在无序r-元子集上的诱导本原作用的轨道图有了一个较为清晰的认识,同时,相关结果可望对以后判定对称群S_n在无序r-元子集上的同步性打下理论基础。
其他文献
近年来,分数阶微分方程在许多学科领域都起到了至关重要的作用,如生物学、化学、工程学、物理学等等,从而吸引了越来越多的学者参与到该问题的研究中来,并取得了许多成果.本
图的核的研究是当前图论特别是代数图论中的一个前沿课题.一个图的核定义为与该图同态等价的最小阶的图.从理论上已经知道确定一般图的核是NP-完全问题,但由于图的核可以继承
新的需求为科学技术的发展指明了方向,科学技术的发展又促使新的需求提出。随着电信网络建设与改造的不断深化,网络规模逐渐扩大,通信设备的种类增多,对子网中通信单盘的功能
艾滋病和乙型肝炎作为目前全世界两种极具危害的传染病,己经给人类的健康造成了很大程度的威胁.本文则从它们的源头-病毒入手,通过分析相应微分方程平衡点的稳定性,探讨HIV-1
水电机组作为水力与电力能源转换的核心设备,确保它的运行稳定性十分关键,一旦水电机组的稳定运行环境遭到破坏,电能输送质量和电网频率都将被影响,造成不必要的经济损失甚至会威胁到人身安全。水电机组振动信号是反映机组故障的一个重要信息,基于对振动信号的处理和分析可以实时掌握机组的运行状况,对提高机组的稳定性运行有着重大意义。随着水电机组结构愈发复杂,内部结构间的机械、电磁等激励耦合作用变的更加强烈,同时伴
科技的发展,加速了工业化的进程,使人们得到了许多便利,但随之而来的环境污染问题却日益严重,并且已经威胁到在其中生存的各种生物的日常生存。而生存于自然界中的种群必然与
企业网站建设进度计划与控制研究是为了解决企业建立网站中存在的问题,当今网站建设时对事前计划比较重视,而忽略了事中控制从而导致了网站建设时间过长,费用过高,挫伤了投资
本研究在前期实验研究中获得一种由四因子c-Myc,Klf4,E-cadherin,Glis1诱导的,形态、体外增殖和体内外分化能力类似于胚胎干细胞,但不具有嵌合能力的部分重编程细胞,KMEG-prC
在本论文中,通过对f-分配子的深入研究,讨论了f-分配子的若干新的性质。给出了一些由f-分配子诱导的群同态。本文将群的中心以及p-中心和n-中心的概念统一,定义了一个新的概
随着互联网经济的崛起,零售业、快递业、仓储运输业得到迅速发展。贴在货架用来展示商品价格等信息的纸质价牌遇到许多新的困难,商品种类繁多信息复杂使得纸质价牌维护成本增