平面图的诱导圈符号控制数问题

论文摘要

设G=（V,E）是一个简单图,定义函数f：E→{-1,+1}.如果G的任意一个诱导圈C都满足f（C）=∑e∈E（C）f（e）≥1,则称f为图G的诱导圈符号控制函数（signed cycle domination function）,简记为SCDF.同时定义γ’SC（G）=min{f（G）|f是G的一个SCDF}为图G的诱导圈符号控制数（signed cycle domination number）.本文主要研究了极大平面图,2-连通平面图和最小度为3的图的诱导圈符号控制数.主要结果如下：（1）设G（|V（G）|= n）是一个极大平面图,γ’SC（G）=n-2当且仅当它的所有诱导圈都是C3.（2）设G（|V（G）|= n）是一个极大平面图,γ’SC（G）≥n当且仅当G有一个诱导圈Ck,其中k≥4.（3）若G是一个2-连通平面图,则γ’SC（G）≥1.（4）任意δ（G）=3的图G,若γ’SC（G）有常数下界,则γ’SC（G）≥2.上述关于极大平面图的结果,否定了徐宝根在[On signed cycle domination in graphs, Discrete Math.309 （2009） 1007-1012]中的一个猜想.

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 背景和基本概念
• 1.2 研究现状
• 第二章 极大平面图的诱导圈符号控制数
• 2.1 任意极大平面图的诱导圈符号控制数的界
• SC=n-2的极大平面图'>2.2 构造出γ'_SC=n-2的极大平面图
• 3的极大平面图的诱导圈符号控制数'>2.3 所有诱导圈是C₃的极大平面图的诱导圈符号控制数
• k（k≥4）诱导圈的极大平面图的γ'_SC（G）'>2.4 含有C_k（k≥4）诱导圈的极大平面图的γ'_SC（G）
• 第三章 诱导圈符号控制数在一些图上的界
• 3.1 2-连通平面图的诱导圈符号控制数
• 3.2 δ（G）=3的图的诱导圈符号控制数
• 第四章 总结
• 参考文献
• 致谢