项目名称: 超图的2-可染色性和图的控制集问题
项目编号: No.11371008
项目类型: 面上项目
立项/批准年度: 2013
项目学科: 数理科学和化学
项目作者: 吕长虹
作者单位: 华东师范大学
项目金额: 50万元
中文摘要: 超图的2-可染色问题是超图染色的一个中心问题,图的控制集理论是目前图论研究的重要内容,也是运筹学选址问题的自然模型。本项目研究的核心内容包括:一、研究超图的2-可染色问题的一个重要的极值问题:一个至少拥有m(n)条边的 n-uniform 超图不是2-可染色的,则m(n)应为多少?本项目将围绕这个问题及相关问题进行研究,希望改进目前关于m(n)的上下界;二、利用超图2-可染色性研究中"slow recoloring"随机思想,结合半正定规划方法,研究图的各种染色问题;三、围绕Goddard和Henning在2009年关于配对控制数上界的猜想,考虑各种图类配对控制数上界估计和极图刻画,希望改进目前已知结果;四、考虑chordal graphs及其子图类上电力控制集问题算法复杂性、有效算法、近似算法等。
中文关键词: 2-染色超图;覆盖;配对控制集;电力控制集;邻域全控制集
英文摘要: The 2-colorability of hypergraphs is a central issue in hypergraph coloring. The domination problem play an important role on graph theory,it is also a natural model for many locating problems in operations research.The core of this project include: Firs
英文关键词: 2-coloring hypergraph;covering;paired-domination;power domination;neighborhood total domination