编辑推荐:
研究人员证明:若A与B为τ-图(τ-graphs)均为森林的菊花立方体(daisy cubes),则A与B同构当且仅当其τ-图同构。该结果被用于表明:一个至少含一条边的菊花立方体是平面二部图(plane bipartite graph)G的共振图(resona
研究人员证明:若A与B为τ-图(τ-graphs)均为森林的菊花立方体(daisy cubes),则A与B同构当且仅当其τ-图同构。该结果被用于表明:一个至少含一条边的菊花立方体是平面二部图(plane bipartite graph)G的共振图(resonance graph)当且仅当其τ-图是一个森林,且该森林同构于删除G中所有禁止边(forbidden edges)所得子图的内对偶(inner dual)。作为推论,以不同证明作为例子给出了Fibonacci立方体(Fibonacci cubes)与Lucas立方体(Lucas cubes)的τ-图的一些已知性质。文中还提出了关于用τ-图刻画Lucas立方体的开放问题。
研究背景:菊花立方体(daisy cube)与中位图(median graph)均为部分立方体(partial cube)的重要子族,并与化学图论中的共振图(resonance graph)密切相关。已知平面弱基本二部图(plane weakly elementary bipartite graph)的共振图是中位图;近期已有工作刻画了共振图为菊花立方体的平面二部图。τ-图(τ-graph)最初由Vesel引入以刻画链状六边形图的共振图,Klav?ar与Kov?e将其推广到部分立方体,并指出每个图都是某个中位图的τ-图;中位图G的τ-图无K
n当且仅当G不含凸K
1,n;部分立方体G的τ-图连通当且仅当G关于笛卡尔积为素图。存在的问题是:非同构部分立方体可具有相同τ-图,例如C
6、Λ
3?K
1,3与Q
3?具有相同τ-图K
3;P
n+1与Γ
n具有相同τ-图P
n;非同构菊花立方体也可具有相同τ-图,如K
1,3与Q
3?同τ-图K
3,以及两个非同构菊花立方体同τ-图K
5。因此,研究人员聚焦菊花立方体的τ-图,研究其在何种条件下可由τ-图决定同构,并据此刻画作为共振图的菊花立方体。研究结论是:若A与B的τ-图为森林,则A与B同构当且仅当其τ-图同构;至少含一条边的菊花立方体是平面二部图G的共振图当且仅当其τ-图为森林且同构于删除G中所有禁止边所得子图的内对偶;特别地,菊花立方体是顶点数大于2的平面基本二部图G的共振图当且仅当其τ-图为树且同构于G的内对偶。其重要意义在于给出森林型τ-图下的同构判定,并建立菊花立方体作为共振图的τ-图刻画,同时为Fibonacci立方体和Lucas立方体的已知τ-图性质提供不同证明。
方法概括:论文以图的Θ-类(Djokovi?-Winkler关系)为基础,围绕部分立方体、中位图和菊花立方体的扩张—收缩结构展开;以τ-图(顶点为Θ-类、边由凸P
3决定)为工具,采用关于维数或Θ-类数的归纳法,并结合笛卡尔积的τ-图分解、收缩与外围/≤-扩张,以及共振图与内对偶的关系进行刻画。未涉及实验样本队列。
研究结果:
3. 主要结果
Lemma 3.1表明,若H为菊花立方体且idim(H)=n,则H?Q
n当且仅当H
τ?K
nC;证明由必要性、归纳法以及≤-扩张和笛卡尔积τ-图分解得出。Theorem 3.2表明,设A与B的τ-图A
τ、B
τ为森林且idim(A)=idim(B)=n,若τ-图同构?:A
τ→B
τ满足?(E
i)=F
i,则存在同构λ:A→B,使得uv∈E
i当且仅当λ(u)λ(v)∈F
i,且λ限制在收缩A/E
j上给出A/E
j与B/F
j的同构;证明通过对n归纳、取非孤立Θ类、收缩并利用森林条件与度1顶点构造同构。Corollary 3.3由此得出:若A与B的τ-图为森林,则A与B同构当且仅当A
τ与B
τ同构。文中还指出,若τ-图不是森林,上述结论一般不成立;原文给出非同构菊花立方体具有相同τ-图K
5,并说明对n≥3可通过K
1,3与Q
3?具有相同τ-图K
3,以及对具有τ-图K
n?1的非同构菊花立方体的最小顶点添加悬挂边,构造具有相同τ-图K
n的非同构菊花立方体。
4. 作为共振图的菊花立方体
本节先给出完美匹配、允许边、禁止边、基本图、弱基本图、内对偶和共振图的定义。Lemma 4.1表明,若G为平面弱基本二部图,其不同于K
2的基本分量G
1,…,G
t为外围2-可着色图(peripherally 2-colorable graphs),则R(G)
τ=R(G
1)
τ∪…∪R(G
t)
τ为森林,其中每个R(G
i)
τ为树且同构于G
i的内对偶;特别地,若G为外围2-可着色图,则R(G)
τ为树且同构于G的内对偶。其证明利用共振图的笛卡尔积分解、τ-图在笛卡尔积下的不交并性质,以及2连通外平面二部图的相关结果。Lemma 4.2表明,若至少含一条边的菊花立方体H同构于平面二部图G的共振图,则H
τ为森林,其分量为树且同构于G的不同于K
2的基本分量的内对偶;特别地,若H同构于平面基本二部图G的共振图,则H
τ为树且同构于G的内对偶。Theorem 4.3表明,至少含一条边的菊花立方体H同构于平面二部图的共振图当且仅当H
τ为森林;特别地,H同构于平面基本二部图的共振图当且仅当H
τ为树。必要性由Lemma 4.2得到;充分性通过对每个树归纳构造内对偶同构于该树的外围2-可着色图,再取不交并并应用Lemma 4.1与Corollary 3.3得到。文中注记指出,Q
n(n≥2)的τ-图为K
nC,故由Theorem 4.3不能是任何平面基本二部图的共振图;而Q
n(n≥1)可作为具有n个偶圈基本分量的平面弱基本二部图的共振图,因为偶圈的共振图为K
2。Lemma 4.4表明:(i) 对n≥1,Γ
nτ?P
n;(ii) 对n≥3,Λ
nτ?C
n;(iii) 对n≥3,Λ
n不能是任何平面二部图的共振图。其证明利用Γ
n?K(P
nC)、Λ
n?K(C
nC)以及关于单纯形图与τ-图的已知恒等式,并由(ii)与Theorem 4.3推出(iii)。Remark指出,已有关于中位图G为Γ
n当且仅当每个Θ-类均为外围类且G
τ?P
n的结果蕴含Lemma 4.4(i);由Corollary 3.3,Γ
n是τ-图为P
n的唯一菊花立方体;对n≥3,非同构中位图P
n+1与Γ
n具有相同τ-图P
n,非同构部分立方体C
2n与Λ
n具有相同τ-图C
n。Question 4.1提出:对n≥3,Λ
n是否为τ-图为C
n的唯一菊花立方体或唯一中位图;能否类似已有结果用τ-图刻画Λ
n。Proposition 4.5表明,对n≥3,Lucas立方体Λ
n的τ-图Λ
nτ为C
n;证明定义Θ类X
i为两端二进制码仅第i位不同的边类,证明X
1邻接X
2与X
n,且不邻接X
j(3≤j≤n?1),并利用凸P
3与4-圈排除得出每个顶点在Λ
nτ中度为2,从而Λ
nτ?C
n。
讨论与结论:讨论部分强调森林型τ-图在同构判定中的关键作用;当τ-图不是森林时,相同τ-图未必对应同构菊花立方体。论文将同构判据应用于共振图识别,给出菊花立方体作为平面二部图或平面基本二部图共振图的τ-图条件,并以不同证明呈现Fibonacci立方体和Lucas立方体τ-图的已知性质;同时提出用τ-图刻画Lucas立方体的开放问题。研究结论翻译为:若A与B是τ-图为森林的菊花立方体,则A与B同构当且仅当其τ-图同构。一个至少含一条边的菊花立方体是平面二部图G的共振图当且仅当其τ-图是一个森林,且该森林同构于删除G中所有禁止边所得子图的内对偶。特别地,一个菊花立方体是顶点数大于2的平面基本二部图G的共振图当且仅当其τ-图是一棵树且同构于G的内对偶。