对等图是图论中的一个重要概念,它在研究图的因子和覆盖问题中具有重要作用。在这篇1998年的论文中,高敬振提出了对等图的定义,并给出了一个图是对等图的充要条件,同时还证明了一类图是对等图。
需要明确的是,本文中讨论的图均为有限无向图。一个图G是一个允许有环和重边的图,用V(G)表示G的顶点集,用E(G)表示G的边集。对于G中的一个顶点x,dG(x)表示x在G中的度数,而δ(G)定义为G中所有顶点度数的最小值。
接下来,我们来理解对等图中的几个关键概念。对于给定的函数g和f,它们都是从G的顶点集V(G)到整数集Z的映射。如果对于每个顶点xεV(G),都有g(x)≤f(x),并且对于每个顶点xεP(g,f),有g(x)=f(x),这里的P(g,f)表示的是满足g(x)=f(x)的所有顶点x的集合。此时,如果存在G的一个支撑子图F(即F是G的子图,且包含G中所有顶点),使得对于每个顶点xεV(G),有g(x)≤dF(x)≤f(x),并且对于每个顶点xεP(g,f),有dF(x)=f(x),那么这样的F称为一个(P,f)一间余的(g,f)一因子。这里间余是指“在边上恰好满足条件”的意思。
如果对于图G的任意一边e,都存在一个(P,f)一间余的(g,f)一因子包含e,那么称G是(P,f)一覆盖的。相反,如果对于图G的任意一边e,都存在一个(P,f)一间余的(g,f)一因子不包含e,那么称G是(P,f)一消去的。一个图如果既(P,f)一覆盖又(P,f)一消去,则称为(P,f)一对等图。
在这里,对等图的概念是核心。当P(g,f)=V(G)时,(P,f)一间余的(g,f)一因子即为普通的(g,f)一因子。而(P,f)一覆盖(消去)图即为普通的(g,f)一覆盖(消去)图。特别地,如果对于所有顶点xεV(G),有g(x)=k,f(x)=l,显然P(g,f)=V(G),则(P,f)一覆盖(消去,对等)图即为k-覆盖(消去,对等)图。
文章还引入了一些关键的数学符号和定义,如对于定义在V(G)上的实数函数γ(x)和ø:;i:XCV(G),定义了γ(ø):=0。这里的ø是一个从X到C的映射,其中C是G中所有顶点的集合。对于图G中的不交子集S和T,eG(S,T)表示连接S和T的边数。另外还定义了分支的概念,以及P一中分支和P-偶分支的定义。
论文中还提出了一些引理来辅助证明主要结果。例如,引理1提出G是(g,j;P)-覆盖的当且仅当对于V(G)的所有不交子集S和T,γ(S,T;P)≥ε1(S,T;P)成立。这里的ε1(S,T;P)是一个由S,T和P共同决定的值,而γ(S,T;P)是另一个根据S,T和P定义的值。类似的,引理2提出了G是(g,j;P)-消去的条件。定理1给出了G是(g,j;P)-对等的条件。
在定理A和定理B中,给出了图对等的一些已知结果。例如,定理A指出,如果G是n阶图,且G的韧度至少为k,则G是k-对等的。定理B指出,对于不包含环和重边的n阶图,如果n至少为6,且G的边数大于k,那么G是h-对等的。这些结果是对等图概念的具体应用,展示了其在图的因子问题中的应用。
文章中提及了作者获得山东省自然科学基金的资助,以及文章的收稿日期。
通过对等图的研究,论文提供了深入理解图的结构性质和因子问题的方法,有助于在理论和应用方面进一步拓展图论的研究。