完全图在圈和路分解下的彩虹生成树

张涛 ,  郭志伟 ,  李丽 ,  石晓芸

延安大学学报(自然科学版) ›› 2026, Vol. 45 ›› Issue (3) : 90 -97.

PDF (459KB)
延安大学学报(自然科学版) ›› 2026, Vol. 45 ›› Issue (3) : 90 -97.
数理科学

完全图在圈和路分解下的彩虹生成树

作者信息 +

Rainbow spanning trees in complete graphs with cycle-decompositions and path- decompositions

Author information +
文章历史 +
PDF (469K)

摘要

研究了完全图在特定子图分解下彩虹生成树的存在性。基于拟阵理论并利用Rado定理,证明了顶点数为奇数的完全图在特定圈分解下和顶点数为偶数的完全图在特定路分解下均包含彩虹生成树及边不交彩虹生成树。此外,通过引入基于特定子图分解的色度矩阵并利用柯西-比奈定理,建立了顶点数为奇数的完全图在特定圈分解下和顶点数为偶数的完全图在特定路分解下彩虹生成树数目的下界。研究结果丰富了完全图在特定子图分解下彩虹生成树及边不交彩虹生成树的存在性理论,同时完善了完全图在特定子图分解下彩虹生成树数目下界的结果。

Abstract

The existence of rainbow spanning trees in complete graphs with specific subgraph-decompositions is considered. Based on matroid theory and using Rado theorem, it is proved that both a complete graph on an odd number of vertices with a specific cycle-decomposition and a complete graph on an even number of vertices with a specific path-decomposition contain rainbow spanning trees and edge-disjoint rainbow spanning tree. Moreover, the lower bounds on the numbers of rainbow spanning trees in a complete graph on an odd number of vertices with a specific cycle-decomposition and a complete graph on an even number of vertices with a specific path-decomposition are established, by introducing color-degree matrices of complete graphs with specific subgraph-decompositions and using the Cauchy-Binet theorem. The results enrich the existence theory of rainbow spanning trees and edge-disjoint rainbow spanning trees in complete graphs with specific subgraph-decompositions, and complete the results of lower bounds on the numbers of rainbow spanning trees in complete graphs with specific subgraph-decompositions.

关键词

完全图 / 圈(路)分解 / 彩虹生成树 / 拟阵理论 / 色度矩阵

Key words

complete graph / cycle- (path-) decomposition / rainbow spanning tree / matroid theory / color-degree matrix

引用本文

引用格式 ▾
张涛,郭志伟,李丽,石晓芸. 完全图在圈和路分解下的彩虹生成树[J]. 延安大学学报(自然科学版), 2026, 45(3): 90-97 DOI:

登录浏览全文

4963

注册一个新账户 忘记密码

在图论研究中,生成树作为极小连通无圈图,是研究复杂图结构的重要基础。KIRCHHOFF[1]考虑电流线性分布问题时首次提出了“树”的概念,并探究了生成树的存在性和计数问题。此后,生成树的存在性和计数问题逐渐成为研究热点[2-4]。特别地,边着色图中彩虹生成树的存在性和计数问题已被广泛研究[5-8]。边着色图是指具有从边集到自然数集的固定映射的图,且彩虹图是指满足任意两条边的颜色均不相同的边着色图。此外,边着色图中彩虹生成树的存在性和计数问题在工程实践领域具有广泛应用。例如,在通信网络领域,彩虹生成树可为“连接所有节点且成本最优”的需求提供有效拓扑结构,并且其数目可作为评估通信网络稳健性的关键指标[9];在化学图论中,将分子图中的原子和化学键分别看作顶点和边建立图模型后,彩虹生成树可用于分析分子结构的稳定性[10];而且,彩虹生成树计数问题在模拟复杂网络与评估网络可靠性等领域也具有重要的应用价值[11]。
图的子图分解是指将该图分解为若干个边不交子图,使得其顶点集的并集为该图顶点集且边集的并集为该图边集。事实上,图的子图分解与图的边着色之间存在着自然的对应关系。对于具有特定子图分解的图,其彩虹子图是指满足任意两条边均来自该子图分解中不同子图的图。近年来,关于完全图在特定子图分解下彩虹生成树的存在性已被关注。BRUALDI等[12]通过划分完全图K2n的边集,构造了2n-1个1-因子,并证明了K2n在该子图分解下存在边不交彩虹生成树。KRUSSEL等[13]在文献[12]的研究基础上改进了结果,并证明了完全图K2n在相同条件下存在三棵边不交彩虹生成树。ALON等[14]针对完全图Kn给出了一种完全二部分解θ:=G1,G2,…,Gn-1,并证明了Kn在此分解下存在彩虹生成树。LIU等[15]针对完全图Kn的最小完全二部分解θ:=G1,G2,…,Gn-1,引入了基于该分解的色度矩阵,并通过色度矩阵的性质给出了Kn在任意最小完全二部分解下彩虹生成树数目的下界。最小完全二部分解是指包含最少数目子图的完全二部分解。
本文借助拟阵理论和Rado定理,分别证明了完全图K2n+1在特定圈分解下和完全图K2n在特定路分解下包含彩虹生成树及边不交彩虹生成树。同时,通过引入基于特定子图分解的色度矩阵并结合柯西-比奈定理,建立了完全图K2n+1在特定圈分解下和完全图K2n在特定路分解下彩虹生成树数目的下界。研究结果进一步丰富了完全图在特定子图分解下彩虹子图存在性的理论体系,并为彩虹子图在相关工程技术领域的应用提供了理论支撑。

1 基本概念及引理

首先,介绍一些基本定义与符号,对于文中出现但未定义的图论术语和符号,可参考文献[16]。本文只考虑简单图,即无环或重边的图。用G=VG,EG表示顶点集VG和边集EG的图,并用EG表示图G的边数。给定图G的边定向是指对G的每条边指定一个方向,从而得到对应有向图D=VD,AD,其中,VD=VG且AD是由EG中每条边定向后得到的弧集。图G的生成子图是指顶点集VG且边集为X⊆EG的图,记作GX。边集X⊆EG在G中的导出子图是指边集为X且顶点集为X中所有边的端点构成集合的图,记作GX。完全图是指图中每对不同顶点都有一条边相连,并用Kn表示n个顶点的完全图。二部图是指顶点集可以划分为两个子集X和Y且图中每条边的两个顶点分别属于X和Y的图,并称X和Y为该二部图的两个部集。对于部集分别为X和Y的二部图,若X中每个顶点都与Y中每个顶点相连,则称该二部图为完全二部图,并用Km,n表示部集顶点数分别为m和n的完全二部图。图中的路是指该图中顶点和边互不相同的点边交替序列;圈是指起点和终点重合的路。用Pk表示k个顶点,并用Ck表示k个顶点的圈。

图G的边着色是指从边集到自然数集的映射c:EG→N。称具有固定边着色的图为边着色图。若边着色图中任意两条边的颜色均不相同,则称该图为彩虹图。图G的子图分解θ:=G1,G2,…,Gk是指将G分解为k个子图G1,G2,…,Gk,使得∪i=1kVGi=VG,∪i=1kEGi=EG且对于1≤i≤j≤k满足EGi⋂EGj=∅。特别地,若图G子图分解中的每个子图均为圈,则称该分解为G的圈分解;若图G子图分解中的每个子图均为路,则称该分解为G的路分解。相应地,若具有子图分解θ的图G的子图H中任意两条边均来自θ的不同子图,则称H是G的彩虹子图。

拟阵M是指有序对E,ℐ,其中,E是有限集合,称为拟阵M的基础集,ℐ⊆2EG是E的子集族且满足以下条件:1)∅∈ℐ;2)若I∈ℐ,且J⊆I,则J∈ℐ;3)若I1,I2∈ℐ且I1<I2,则存在e∈I2-I1使得I1⋃e∈ℐ。称ℐ中的元素为拟阵M的独立集。设G=VG,EG为无向图,定义ℐ⊆2EG是由EG的子集构成的集族,使得X∈ℐ当且仅当GX不包含图G的圈,并称拟阵M=EG,ℐ为图G的圈拟阵。对于图G边集的任意非空子集X,定义rankX=maxI:I⊆X,I∈ℐ为圈拟阵的秩函数。

引理1[17] (Rado定理) 设M=E,ℐ是有限集合E上的拟阵,I=1,2,…,n且𝒞=C1,C2,…,Cn是E的子集族。则对于满足0≤m≤I的整数m,存在基数为m且元素来自𝒞中不同子集的独立集F,当且仅当对于任意子集J⊆I,秩函数

rank∪i∈JCi≥J-I-m。

引理2[17] 设G是顶点数为n,边集为EG的图,且M=EG,ℐ是G的圈拟阵。则对于任意子集X⊆EG,拟阵M的秩函数为rankX=n-t,其中,t是GX的分支数。

引理3 设G是顶点数为n的简单图,且X⊆EG。如果对于给定正整数r,X>r2,那么X的秩函数rankX≥r。

证明 设t为GX的分支数,其中,1≤t≤n。分别用n1,n2,…,nt表示各分支的顶点数,则∑i=1tni=n。由于r2<X≤n12+n22+⋯+nt2,根据不等式a2+b2≤a+b-12可得r2<X≤n-t+12,因此n-t≥r,即rankX≥r。引理3得证。

引理4[18] 设n≥1是整数,且K2n是顶点数为2n的完全图。则K2n存在路分解θ:=P1,P2,…,P2n-1,其中,对于i∈1,2,…,2n-1,Pi是长度为n的路。

接下来,在完全图Kn上定义基于二部子图分解的色度矩阵。

设θ:=G1,G2,…,Gn-1是完全图Kn的二部子图分解,其中,对于i∈1,2,…,n-1,Gi是以Xi和Yi为部集的二部图。规定:如果顶点v∈Xi,那么v在Gi中度的符号记作“+”;如果顶点v∈Yi,那么v在Gi中度的符号记作“-”。在这种情形下,Kn的色度矩阵定义为B=±bijn×n-1,其中,如果vi∈VGj,那么bij表示顶点vi在子图Gj中的度;如果vi∉VGj,那么bij=0。

令Bi表示矩阵B删除第i行后的子矩阵。由色度矩阵的定义可知,矩阵B满足每一列元素之和为零。对B添加列和不为零的一列元素构成n阶矩阵。考虑n阶矩阵对应的行列式,对其进行初等行变换,将各行元素加到指定行后按该行展开。由于此n阶行列式值的绝对值为定值,且该定值等于新增列元素之和与矩阵B删除指定行后对应n-1阶行列式乘积的绝对值,因此原矩阵B任意删除一行对应的n-1行列式值仅符号存在不同,即满足

|detBi|=|detBj|。

不难发现,基于二部子图分解所定义的色度矩阵并不唯一。由于顶点(子图)可以任意重新标记,因此导致矩阵的行(列)重新排列。此外,顶点在子图中度的符号可任意定义使得每一列均可独立乘以±1。这些改变仅会使任意子矩阵Bi的行列式改变一个因子±1。因此,detBi是二部子图分解θ的不变量,记为detθ。

对于图G的二部子图分解θ:=G1,G2,…,Gn-1,按照从一个部集到另一个部集的方向对Gii∈1,2,…,n-1中的边定向,由此得到图G在θ下的有向图,记作D。根据有向图D,定义顶点-弧关联矩阵M=mijn×q,其中,mij=1,如果aj指出顶点vi;           -1,如果aj指向顶点vi;         0,如果aj和顶点vi不关联。

进一步,定义弧-子图关联矩阵N=nijq×n-1,其中,nij=1,如果ai∈AGj;0,其他。                 

对于无向图,可以采用同样的方式定义边-子图关联矩阵。

引理5 设G是顶点数为n且具有二部子图分解θ:=G1,G2,…,Gn-1的图,B是图G基于二部子图分解的色度矩阵,M是顶点-弧关联矩阵,且N是弧-子图关联矩阵。则满足B=MN。

证明 根据矩阵乘法运算法则可知,需证明矩阵B中元素bij等于矩阵M的第i行子矩阵与矩阵N的第j列子矩阵的乘积,其中,乘积表示子图Gj中与顶点vi关联的边数。由于子图Gj的边定向,从而矩阵M和N中与边相关的元素符号一致,因此这些元素的和等于顶点vi在子图Gj中的度。根据色度矩阵B的定义,矩阵B中元素bij等于矩阵M的第i行子矩阵与矩阵N的第j列子矩阵的乘积。引理5得证。

引理6[19] (柯西-比奈定理) 设A是m×n矩阵,且B是n×m矩阵。假设子集S⊆N+且满足S=m,AS为A中列指标取对应S的m×m子矩阵,且ΒS为B中行指标取对应S的m×m子矩阵。则有

detAB=∑S⊆N+,S=mdetASdetBS。

引理7[20] 设M是图G的顶点-边关联矩阵。若G不包含圈,当且仅当M的列向量组线性无关。设N是图G的边-子图关联矩阵。若集合S⊆EG中的边构成彩虹子图,当且仅当N关于集合S的行向量组线性相关。

2 主要结果

定理1 设n≥3是整数,且K2n+1是顶点数为2n+1的完全图。如果K2n+1存在满足k≥2n且对于i∈1,2,…,k,3≤ECi≤n的圈分解θ:=C1,C2,…,Ck,那么K2n+1在该分解下包含彩虹生成树。

证明 设θ:=C1,C2,…,Ck是完全图K2n+1的圈分解,其中,k≥2n且对于i∈1,2,…,k,3≤ECi≤n。考虑完全图K2n+1的圈拟阵M(E(K2n+1),ℐ)。设I=1,2,…,k且𝒞=EC1,EC2,…,ECk是边集EK2n+1的子集族。根据引理1可知,存在基数为2n且元素来自𝒞中不同子集的独立集F,当且仅当对于任意子集J⊆I,秩函数

rank∪i∈JECi≥J-k-2n。

情形1J-k-2n≤0。

根据引理2可知,秩函数rank∪i∈JECi=2n+1-t。因为K2n+1∪i∈JECi的分支数t≤2n+1,所以秩函数rank∪i∈JECi≥0。又因为J-k-2n≤0,所以秩函数rank∪i∈JECi≥J-k-2n成立。

情形2J-k-2n>0。

情形2.1J-k-2n=1。

因为k≥2n,所以J≥1。此时∪i∈JECi≥3>J-k-2n2。根据引理3可知,秩函数

rank∪i∈JECi≥J-k-2n。

情形2.2J-k-2n=2。

因为k≥2n,所以J≥2。此时∪i∈JECi≥6>J-k-2n2。根据引理3可知,秩函数

rank∪i∈JECi≥J-k-2n。

情形2.3J-k-2n>2。

考虑∪i∈JECi与J-k-2n2之间的关系,因此存在

∪i∈JECi-J-k-2n2≥2n+12-k-Jn-J-k-2n2=2n-12k-Jk-J-2n+1。

由于J-k-2n>0且k≥J,因此0≤k-J<2n。又因为J-k-2n>2,所以k-J-2n+1<-1。因此2n-12k-Jk-J-2n+1>0,从而∪i∈JECi>J-k-2n2成立。根据引理3可知,秩函数

rank∪i∈JECi≥J-k-2n。

综上所述,对于任意子集J⊆I,都有秩函数rank∪i∈JECi≥J-k-2n成立。根据引理1可知,对于K2n+1的圈拟阵MEK2n+1,ℐ,存在基数为2n且元素来自𝒞中不同子集的独立集F。由于该独立集F是不包含圈的边集,且包含2n+1个顶点和2n条边,因此F构成的图是连通的,即形成彩虹生成树。定理1得证。

推论1 设n≥3是整数,且K2n+1是顶点数为2n+1的完全图。则K2n+1在满足k≥2n且对于i∈1,2,…,k,3≤ECi≤n的圈分解θ:=C1,C2,…,Ck下包含不同构于K1,2n的彩虹生成树。

证明 设θ:=C1,C2,…,Ck是完全图K2n+1的圈分解,其中,k≥2n且对于i∈1,2,…,k,3≤ECi≤n。由定理1可知,完全图K2n+1在该圈分解θ:=C1,C2,…,Ck下包含彩虹生成树,记作T。若T不同构于K1,2n,则该推论得证。接下来,假定T同构于K1,2n。设ET=e1,e2,…,e2n,其中,对于i∈1,2,…,2n,边ei=vvi∈ECi。

当k=2n时。由于每个圈Ci至少包含3条边,因此对于任意指定的圈Ci,可通过从Ci中选取一条未出现在T的边ei'=vivj替换T中来自Ci的边ei,得到新的彩虹生成树,即T'=T-ei+ei'。

当k>2n时。由于彩虹生成树T的构造仅需从2n个子图中选取2n条来自不同子图的边,因此在该圈分解θ中,除被选取的2n个子图C1,C2,…,C2n外,仍存在至少一个未被T使用任何边的子图,记作Cjj∈1,2…,k\1,2,…,2n。假设边e∈ECj。此时,边e必连接两个非中心顶点vi与vj。由于圈Cii∈1,2,…,k至少包含3条边,因此对于任意指定的圈Cj,可以通过从Cj中选取未出现在T的边e=vivj替换T中来自Ci的边ei,得到新的彩虹生成树,即T″=T-ei+e。

综上所述,K2n+1在该分解θ下包含不同构于K1,2n的彩虹生成树。推论1得证。

定理2 设n≥3是整数,且K2n+1是顶点数为2n+1的完全图。假设T是K2n+1在满足k≥2n且对于i∈1,2,…,k,3≤ECi≤n的给定圈分解θ:=C1,C2,…,Ck下不同构于K1,2n的彩虹生成树。则K2n+1在该圈分解θ下包含与T边不交的彩虹生成树T'。

证明 设T是K2n+1在满足k≥2n且对于i∈1,2,…,k,3≤EGi≤n的给定圈分解θ:=C1,C2,…,Ck下不同构于K1,2n的彩虹生成树。令G'=K2n+1-ET。对于i∈1,2,…,k,记Ci'=Ci-ei,其中,Ci∈θ且边ei=ET⋂ECi。不难发现,子图Ci'包含一条路或一个圈。记θ':=C1',C2',…,Ck'是G'的子图分解。因此,为证明K2n+1在圈分解θ下存在边不交彩虹生成树,需证明G'在子图分解θ'下存在彩虹生成树T'。

对于图G',考虑其圈拟阵MEG',ℐ。设I=1,2,…,k,且𝒞'=EC1',EC2',…,ECk'是EG'的子集族,其中,ECi'≥ECi-1≥2i∈I。根据引理1可知,存在基数为2n且元素来自𝒞'中不同子集的独立集F',当且仅当对于任意子集J⊆I,有秩函数rank∪i∈JECi'≥J-k-2n。接下来,根据J的大小分两种情形讨论。

情形1J=I=k。

由于T是不同构于K1,2n的彩虹生成树,因此G'∪i∈JECi'=G'∪i∈IECi'=G'是连通的。根据引理2可知,秩函数rank∪i∈JECi'=2n+1-1=2n。又因为J=k,所以秩函数rank∪i∈JECi'≥J-k-2n成立。

情形2J<I=k。

考虑∪i∈JECi'与J-k-2n2之间的关系,因此存在

∪i∈JECi'-J-k-2n2≥2n+12-2n-k-Jn-J-k-2n2=12(k-J)(J-k+2n-1)。

情形2.1J-k+2n-1>0。

此时12k-JJ-k+2n-1>0。因此∪i∈JECi'-J-k-2n2>0成立。根据引理3可知,秩函数rank∪i∈JECi'≥J-k-2n。

情形2.2J-k+2n-1=0。

因为k≥2n,所以J≥1。此时∪i∈JECi'≥2>J-k-2n2。根据引理3可知,秩函数

rank∪i∈JECi'≥J-k-2n。

综上所述,对于任意子集J⊆I,都有秩函数rank∪i∈JECi'≥J-k-2n成立。根据引理1可知,对于图G'的圈拟阵MEG',ℐ,存在基数为2n且元素来自𝒞'中不同子集的独立集F'。因为该独立集F'是不包含圈的边集,且包含2n+1个顶点和2n条边,所以F'构成的图是连通的,即形成彩虹生成树。因此K2n+1在该圈分解θ下包含与T边不交的彩虹生成树T'。定理2得证。

注1 在定理2中,如果T是K2n+1在给定圈分解θ下同构于K1,2n的彩虹生成树,那么与T边不交的彩虹树将无法包含与K1,2n的中心点关联的边,即无法构成彩虹生成树。

定理3 设n≥2是整数,且K2n是顶点数为2n的完全图。则存在路分解θ:=P1,…,P2n-1,使得K2n在该分解θ下包含彩虹生成树。

证明 由引理4可知,完全图K2n存在由长度为n的路组成的路分解。设θ:=P1,…,P2n-1是K2n的路分解,其中,Pii∈1,2,…,2n-1是长度为n的路。对于完全图K2n,考虑其圈拟阵MEK2n,ℐ。设I=1,2,…,2n-1且𝒫=EP1,EP2,…,EP2n-1是EK2n的子集族。根据引理1可知,存在基数为2n-1且元素来自P中不同子集的独立集F=e1,e2,…,e2n-1,当且仅当对于任意子集J⊆I,秩函数rank∪i∈JEPi≥J-I-2n+1=J。接下来,根据J的大小分三种情形讨论。

情形1J=0。

此时∪i∈JEPi=∅,空集生成子图是空图,其分支数t=0。根据引理2可知,秩函数rank∪i∈JEPi=2n-t=2n。因为J=0,所以秩函数

rank∪i∈JEPi=2n≥J。

情形21≤J<I=2n-1。

情形2.1J=1。

此时∪i∈JEPi=n。因此∪i∈JEPi=n>J2成立。根据引理3可知,秩函数rank∪i∈JEPi≥J。

情形2.2J=2。

此时∪i∈JEPi=2n。因此∪i∈JEPi=2n>J2成立。根据引理3可知,秩函数

rank∪i∈JEPi≥J。

情形2.33≤J<2n-1。

考虑∪i∈JEPi与J2之间的关系,因此存在

∪i∈JEPi-J2≥2n2-2n-1-Jn-J2=12J2n+1-J。

又因为J<2n-1,所以2n+1-J>0。因此12J2n+1-J>0,从而∪i∈JEPi>J2成立。根据引理3可知,秩函数

rank∪i∈JEPi≥J。

情形3J=I=2n-1。

此时K2n∪i∈JEPi的分支数t=1。根据引理2可知,秩函数rank∪i∈JEPi=2n-t=2n-1。因为J=2n-1,所以秩函数

rank∪i∈JEPi=2n-1=J。

综上所述,对于任意子集J⊆I,都有秩函数rank∪i∈JEPi≥J成立。根据引理1可知,对于图K2n的圈拟阵MEK2n,ℐ,存在基数为2n-1且元素都来自P中不同子集的独立集F=e1,e2,…,e2n-1。由于该独立集F是不包含圈的边集,且包含2n个顶点和2n-1条边,因此F构成的图是连通的,即形成彩虹生成树。定理3得证。

推论2 设n≥2是整数,且K2n是顶点数为2n的完全图。则K2n在由长度为n的路组成的路分解θ:=P1,…,P2n-1下包含不同构于K1,2n-1的彩虹生成树。

证明 由定理3可知,K2n在由长度为n的路组成的路分解θ:=P1,…,P2n-1下包含彩虹生成树,记作T。如果T不同构于K1,2n-1,那么该推论得证。接下来,假定T同构于K1,2n-1。设ET=e1,e2,…,e2n-1,其中,对于i∈1,2,…,2n-1,边ei=vvi∈EPi。由于每条路Pi包含n条边,因此对于任意指定的路Pii∈1,2,…,2n-1,可通过从Pi中选取一条未出现在T的边ei'=vivj替换T中来自Pi的边ei,得到新的彩虹生成树,即T'=T-ei+ei'。不难检验新的彩虹生成树T'不同构于K1,2n-1。

综上所述,完全图K2n在该路分解θ:=P1,…,P2n-1下包含不同构于K1,2n-1的彩虹生成树。推论2得证。

定理4 设n≥2是整数,且K2n是顶点数为2n的完全图。假设T是K2n在由长度为n的路组成的给定路分解θ:=P1,…,P2n-1下不同构于K1,2n-1的彩虹生成树。则K2n在该分解θ下包含与T边不交的彩虹生成树T'。

证明 设T是K2n在给定路分解θ:=P1,…,P2n-1下不同构于K1,2n-1的彩虹生成树。令G'=K2n-ET。对于i∈1,2,…,2n-1,记Pi'=Pi-ei,其中,Pi∈θ且边ei=ET⋂EPi。不难发现,子图Pi'至多包含两条边不交路。记θ':=P1',P2',…,P2n-1'是G'的子图分解。因此,为证明K2n在该路分解θ下存在与T边不交的彩虹生成树,需证明G'在子图分解θ'下存在彩虹生成树T'。

对于图G',考虑其圈拟阵MEG',ℐ。设I=1,2,…,2n-1且𝒫'=EP1',EP2',…,EP2n-1'是边集EG'的子集族。根据引理1可知,存在基数为2n-1且元素来自𝒫'中不同子集的独立集F'=e1',e2',…,e2n-1',当且仅当对于任意子集J⊆I,秩函数rank∪i∈JEPi'≥J-I-2n+1=J。接下来,根据J的大小分两种情形讨论。

情形1J=I=2n-1。

由于T是不同构于K1,2n-1的彩虹生成树,因此G'∪i∈JEPi'=G'∪i∈IEPi'=G'是连通的。根据引理2可知,秩函数rank∪i∈JEPi'=2n-t=2n-1。因为J=2n-1,所以秩函数rank∪i∈JEPi'=2n-1≥J成立。

情形2J<I=2n-1。

考虑∪i∈JEPi'与J2之间的关系,因此存在

∪i∈JEPi'-J2≥2n2-2n-1-2n-1-Jn-1-J2=12J2n-1-J。

因为J<2n-1,所以2n-1-J>0。因此12J2n-1-J>0,从而∪i∈JEPi'>J2成立。根据引理3可知,秩函数rank∪i∈JEPi'≥J。

综上所述,对于任意子集J⊆I,都有秩函数rank∪i∈JEPi'≥J成立。根据引理1可知,对于G'的圈拟阵MEG',ℐ,存在基数为2n-1且元素来自𝒫'中不同子集的独立集F'=e1',e2',…,e2n-1'。因为该独立集F'是不包含圈的边集,且包含2n个顶点和2n-1条边,所以F'构成的图是连通的,即形成彩虹生成树。因此K2n在该路分解θ下存在与T边不交的彩虹生成树T'。定理4得证。

注2 在定理4中,如果T是K2n在给定路分解θ下同构于K1,2n-1的彩虹生成树,那么与T边不交的彩虹树将无法包含与K1,2n-1的中心点关联的边,即无法构成彩虹生成树。

下面用RSTθ表示完全图Kn在子图分解θ下的彩虹生成树数目。

定理5 设n≥2是整数,且K2n是顶点数为2n并具有路分解θ:=P1,…,P2n-1的完全图。则在该分解θ下,RSTθ≥detθ。

证明 设θ:=P1,…,P2n-1为完全图K2n的路分解。值得注意的是θ中路Pii∈1,2,…,2n-1是二部图。设D是对θ中的每个路Pi进行从一个部集到另一个部集的任意定向形成K2n的有向图。设M为D的2n×q顶点-弧关联矩阵,且N为D的q×2n-1弧-路关联矩阵。进一步设B为K2n在路分解θ下的色度矩阵。根据引理5可知,B=MN。令Ai表示矩阵A删除第i行后形成的子矩阵。由B=MN可得B2n-1=M2n-1·N。根据detθ的定义可知

detθ=detB2n-1。进一步可得

detθ=detB2n-1=detM2n-1·N。

根据引理6可知

detM2n-1·N=∑S⊆E,S=2n-1detM2n-1S·detNS,

其中,∑是对由2n-1条边组成的所有子集S求和,M2n-1S是保留S对应M的2n-1列得到的矩阵,且NS是保留S所对应N的2n-1行得到的矩阵。

根据引理7可知,若集合S的边导出子图是K2n的生成树,则detM2n-1S=±1;否则,detM2n-1S=0。进一步由引理7及弧-路关联矩阵N的定义可知,若集合S的边导出子图是彩虹的,则detNS=±1;否则,detNS=0。因此集合S的边导出子图是K2n在θ分解下的彩虹生成树,当且仅当detM2n-1S·detNS=±1。进一步有K2n在θ分解下的彩虹生成树数目

RSTθ=∑S⊆E,S=2n-1detM2n-1S·detNS≥∑S⊆E,S=2n-1detM2n-1S·detΝS=detB2n-1=detθ。

定理5得证。

注3 定理5中完全图K2n的路分解θ:=P1,…,P2n-1不必满足Pii∈1,2,…,2n-1是长度为n的路,只需确保该分解θ恰包含2n-1条路。用定理5的证明思路同样可以得到完全图K2n+1在由长度为大于等于4的偶数的圈组成的圈分解θ:=C1,C2,…,C2n下彩虹生成树数目的下界。

3 结束语

本文证实了完全图K2n+1在特定的圈分解下和K2n在特定路分解下均能够包含彩虹生成树和边不交彩虹生成树,并证明了存在与对应分解相关的不变量作为K2n+1在特定圈分解下和K2n在特定路分解下彩虹生成树数目的下界。研究结果为进一步考虑更一般图在特定子图分解下不同结构彩虹子图的存在性及确定相应彩虹子图数目下界提供了理论支撑。后续值得进一步考虑完全图K2n+1在哪些圈分解下和K2n在哪些路分解下能够包含更多边不交彩虹生成树,以及探究目前无法用定理5的证明方法确定的K2n+1,在圈的个数大于2n的偶圈分解和包含奇圈的圈分解下及K2n在路的个数大于2n-1的路分解下,彩虹生成树数目的下界问题。

参考文献

[1]

KIRCHHOFF G. Über die auflösung der gleichungen,auf welche man bei der untersuchung derlinearen verteilung galvanischer Ströme geführt wird[J]. Annual Review of Physical Chemistry,1847,72:497-508.

[2]

ALBIN N, KOTTEGODA K, POGGI-CORRADINI P. An exact-arithmetic algorithm for spanning tree modulus[J]. Networks,2025,85(4):412-424.

[3]

DING C, WEI P, SHI Y,et al. Sampling and active learning methods for network reliability estimation using K-terminal spanning tree[J]. Reliability Engineering & System Safety,2024,250:110309.

[4]

GONG H L, JIN X A. A simple formula for the number of the spanning trees of line graphs[J]. Journal of Graph Theory,2018,88(2):294-301.

[5]

HU J, LI H, MAEZAWA S. Maximum properly colored trees in edge-colored graphs[J]. Journal of Combinatorial Optimization,2022,44:154-171.

[6]

BAI X Q, LI B, XU C D,et al. Fast algorithm for the rainbow disconnection coloring of 2-trees[J]. Journal of the Operations Research Society of China,2023,14:149-161.

[7]

AIGNER-HOREV E, HEFETZ D, LAHIRI A. Rainbow trees in uniformly edge-colored graphs[J]. Random Structures & Algorithms,2023,62(2):287-303.

[8]

GE J, DONG F M. Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs[J]. Discrete Applied Mathematics,2020,283:542-554.

[9]

NELSEN L M. Applications of geometric and spectral methods in graph theory[D]. Denver:University of Denver,2019.

[10]

XU M, CHEN H. Tree-Invent:A novel multipurpose molecular generative model constrained with a topological tree[J]. Journal of Chemical Information and Modeling,2023,63(22):7067-7082.

[11]

BRADSHAW P. Rainbow spanning trees in random subgraphs of dense regular graphs[J]. Discrete Math,2024,347(6):113960.

[12]

BRUALDI R, HOLLINGSWORTH S. Multicolored trees in complete graphs[J]. Journal of Combinatorial Theory,Series B,1996,68:310-313.

[13]

KRUSSEL J, MARSHALL S, VERRALL H. Spanning trees orthogonal to one-factorizations of K2 n [J]. Ars Combinatoria:A Canadian Journal of Combinatorics,2000,57:77-82.

[14]

ALON N, BRUALDI R A, SHADER B L. Multicolored forests in bipartite decompositions of graphs[J]. Journal of Combinatorial Theory,Series B,1991,53(1):143-148.

[15]

LIU J Q, SCHWENK A J. The color-degree matrix and the number of multicolored trees in star decompositions[J]. Journal of Combinatorial Theory,Series B,1994,60(2):207-221.

[16]

BONDY J A, MURTY U S R. 吴望名等译. 图论及其应用[M]. 北京:科学出版社,1984.

[17]

WELSH D J A. Matroid theory[M]. New York:Dover Publications,2010.

[18]

TARSI M. Decomposition of a complete multigraph into simple paths:nonbalanced handcuffed designs[J]. Journal of Combinatorial Theory,Series A,1983,34(1):60-70.

[19]

张远达. 线性代数原理[M]. 上海:上海教育出版社,1980.

[20]

WHITNEY H. Non-separable and planar graphs[J]. Proceedings of the National Academy of Sciences of the United States of America,1931,17(2):125-127.

基金资助

国家自然科学基金项目(12301456)

国家自然科学基金项目(12471334)

陕西高校优秀青年人才支持计划项目(202120009)

延安大学研究生科研创新计划项目(YKY2025030)

延安大学创新创业训练项目(D2024117)

AI Summary AI Mindmap
PDF (459KB)

0

访问

0

被引

详细

导航
相关文章

AI思维导图

/

〈 〉