符号图的符号圈覆盖问题研究

The circuit cover of graphs is an important research area in graph theory. The signed circuit cover of signed graphs is a new research topic arising in recent years. The project mainly investigates signed circuit covers of signed graphs, with emphasis on the following three topics: 1.Signed circuit covers of signed graphs, aiming for an improvement on the upper bound of the length of a shortest signed circuit cover; 2.Signed circuit k-covers of signed graphs, with hopes of finding positive integers k such that coverable signed graphs have a signed circuit k-cover; 3.The shortest circuit cover conjecture, hoping to improve the upper bound of the length of a shortest circuit cover. The investigation will promote the study of signed circuit covers of signed graphs, and furthermore, promote the research of circuit covers of graphs and related problems in graph theory.

图的圈覆盖问题是图论的重要研究内容，符号图的符号圈覆盖问题是近几年的新兴课题。本项目以符号图为主要研究对象，研究图上的符号圈覆盖。项目的主要研究内容包括：1.研究符号图的符号圈覆盖问题，改进最短符号圈覆盖长度的上界；2.探讨符号图的符号圈k-覆盖，即判定对于哪些正整数k，使得符号图存在符号圈k-覆盖；3.研究图的短圈覆盖猜想，改进最短圈覆盖长度的上界。本项目的开展将丰富符号图的符号圈覆盖问题的研究成果，从而进一步促进图的圈覆盖及相关问题的发展。

本项目研究了图的圈覆盖及其相关问题，主要包括图的圈k-覆盖、短圈覆盖及图的交叉数、能量等参数的相关问题。对于符号图的圈k-覆盖问题，圈6-覆盖猜想是一个重要的研究课题。本项目刻画了2-连通欧拉符号图的覆盖分解，进而证明圈6-覆盖猜想对欧拉符号图成立，即任意圈可覆盖的欧拉符号图有由4个圈覆盖构成的圈6-覆盖,且每个圈覆盖包含图中任意边不超过2次，得到比已有文献中关于欧拉符号图的圈6-覆盖更强的研究结果，进而证明圈6-覆盖猜想对广义欧拉符号图成立。特别的，本项目研究证明含有偶数条负边的欧拉符号图有由3个圈覆盖构成的圈4-覆盖，进而证明任意圈可覆盖的拟欧拉符号图也有由3个圈覆盖构成的圈4-覆盖。本项目将图的圈k-覆盖问题的研究结果应用于符号图的短圈覆盖问题，利用广义欧拉符号图的圈6-覆盖，得到广义欧拉符号图G的最短圈覆盖长度的上界3/2|E(G)|，推广了欧拉符号图的短圈覆盖问题的研究结果，并进一步证明feasible-连通图G的最短圈覆盖的长度满足scc(G)<8/3|E(G)|。对于图的交叉数、能量、控制数等参数的相关问题，本项目利用图的组合结构分析法，引入旋系技巧确定了一些典型联积图类的交叉数；通过对图的能量与匹配数、奇圈个数及秩等参数之间关系的分析，利用匹配数给出了图能量的上界并刻画了极值图，推广了已有文献对于无三角形的图的能量的研究；对图、区组设计及有限群的相关问题进行了交叉研究，刻画了双循环群的同谱凯莱图和交换图、区组设计的关联图的控制数及度量维度等相关问题。