在这篇文章中,作者吴跃生副教授研究了非连通图C3(m,0,0)∪G的优美性问题,并提出了该图的两种优美标号。为了深入理解这篇论文,我们需要了解以下几个关键的图论概念:优美标号、平衡二分图、交错图以及图的冠。 优美标号是组合数学中的一个重要概念。对于一个无向简单图G,如果存在一个单射θ,将G的顶点集合V(G)映射到整数集合{0,1,...,|E(G)|}上,并且使得由θ导出的每一条边e=(u,v)的边权重θ′(e)等于|θ(u)-θ(v)|是边集合E(G)到{1,2,...,|E(G)|}的一个双射,那么我们称这个图G是优美图,θ是G的一组优美标号,θ′是G边上的诱导值。 接下来,平衡二分图是图论中的一个概念,如果一个二部图G存在一个优美标号f,且对于任意的边(u,v)∈E(G),有f(u)>k≥f(v)或f(u)≤k<f(v)成立,其中k是一个正整数,我们称这个标号f为G的平衡标号,k为f的特征,而图G被称为平衡二分图。 在平衡二分图中,如果优美标号θ的特征为k,并且θ(u0)=k,θ(v0)=k+1,那么称顶点u0为G的二分点,v0为G的对偶二分点。 关于交错图,如果一个二部图G的优美标号θ是交错标号,即划分顶点集合为X和Y两个集合,满足maxv∈Xθ(v)<minv∈Yθ(v),那么称G为交错图,其特征即为交错标号的特征。 图的冠概念指的是给定图G的每个顶点vi都粘接了ri条悬挂边(ri为自然数,i=1,2,...,n),得到的图称为G的(r1,r2,...,rn)-冠,简记为G(r1,r2,...,rn)。当r1=r2=...=rn=r时,称为图G的r-冠。图G的0-冠即为图G本身。 在这篇文章中,作者具体讨论了非连通图C3(m,0,0)∪G的优美性,这里的C3(m,0,0)是指在圈C3的基础上添加(m,0,0)-冠得到的图。作者提出了该非连通图的两种优美标号,并在定理1中给出了一种标号的存在性证明。这个定理指出,如果G是一个有p条边的优美图,且其优美标号的特征值为k+1,那么将G与特征为k的交错图H合并,就一定能找到一个优美标号,使得非连通图G∪H的顶点标号不包含k+1。 为了证明这一点,作者定义了非连通图G∪H的顶点标号θ,并通过证明θ满足优美图的条件来完成证明。首先证明了θ是单射或双射,然后证明了θ′(边的诱导值)同样满足条件,从而验证了θ确实是非连通图G∪H的优美标号。这个定理为图的优美性研究提供了新的方法和思路,对于图论和组合数学的发展具有一定的贡献。
- 粉丝: 7
- 资源: 941
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助