基于森林型τ-图的菊花立方体同构判定与共振图刻画

《Discrete Mathematics》:Isomorphic daisy cubes based on their τ-graphs

【字体: 大 中 小 】 时间:2026年10月23日 来源:Discrete Mathematics 1.1

编辑推荐:

  研究人员证明:若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的τ-图无Kn当且仅当G不含凸K1,n;部分立方体G的τ-图连通当且仅当G关于笛卡尔积为素图。存在的问题是:非同构部分立方体可具有相同τ-图,例如C6、Λ3?K1,3与Q3?具有相同τ-图K3;Pn+1与Γn具有相同τ-图Pn;非同构菊花立方体也可具有相同τ-图,如K1,3与Q3?同τ-图K3,以及两个非同构菊花立方体同τ-图K5。因此,研究人员聚焦菊花立方体的τ-图,研究其在何种条件下可由τ-图决定同构,并据此刻画作为共振图的菊花立方体。研究结论是:若A与B的τ-图为森林,则A与B同构当且仅当其τ-图同构;至少含一条边的菊花立方体是平面二部图G的共振图当且仅当其τ-图为森林且同构于删除G中所有禁止边所得子图的内对偶;特别地,菊花立方体是顶点数大于2的平面基本二部图G的共振图当且仅当其τ-图为树且同构于G的内对偶。其重要意义在于给出森林型τ-图下的同构判定,并建立菊花立方体作为共振图的τ-图刻画,同时为Fibonacci立方体和Lucas立方体的已知τ-图性质提供不同证明。

方法概括:论文以图的Θ-类(Djokovi?-Winkler关系)为基础,围绕部分立方体、中位图和菊花立方体的扩张—收缩结构展开;以τ-图(顶点为Θ-类、边由凸P3决定)为工具,采用关于维数或Θ-类数的归纳法,并结合笛卡尔积的τ-图分解、收缩与外围/≤-扩张,以及共振图与内对偶的关系进行刻画。未涉及实验样本队列。

研究结果:
3. 主要结果
Lemma 3.1表明,若H为菊花立方体且idim(H)=n,则H?Qn当且仅当Hτ?KnC;证明由必要性、归纳法以及≤-扩张和笛卡尔积τ-图分解得出。Theorem 3.2表明,设A与B的τ-图Aτ、Bτ为森林且idim(A)=idim(B)=n,若τ-图同构?:Aτ→Bτ满足?(Ei)=Fi,则存在同构λ:A→B,使得uv∈Ei当且仅当λ(u)λ(v)∈Fi,且λ限制在收缩A/Ej上给出A/Ej与B/Fj的同构;证明通过对n归纳、取非孤立Θ类、收缩并利用森林条件与度1顶点构造同构。Corollary 3.3由此得出:若A与B的τ-图为森林,则A与B同构当且仅当Aτ与Bτ同构。文中还指出,若τ-图不是森林,上述结论一般不成立;原文给出非同构菊花立方体具有相同τ-图K5,并说明对n≥3可通过K1,3与Q3?具有相同τ-图K3,以及对具有τ-图Kn?1的非同构菊花立方体的最小顶点添加悬挂边,构造具有相同τ-图Kn的非同构菊花立方体。

4. 作为共振图的菊花立方体
本节先给出完美匹配、允许边、禁止边、基本图、弱基本图、内对偶和共振图的定义。Lemma 4.1表明,若G为平面弱基本二部图,其不同于K2的基本分量G1,…,Gt为外围2-可着色图(peripherally 2-colorable graphs),则R(G)τ=R(G1)τ∪…∪R(Gt)τ为森林,其中每个R(Gi)τ为树且同构于Gi的内对偶;特别地,若G为外围2-可着色图,则R(G)τ为树且同构于G的内对偶。其证明利用共振图的笛卡尔积分解、τ-图在笛卡尔积下的不交并性质,以及2连通外平面二部图的相关结果。Lemma 4.2表明,若至少含一条边的菊花立方体H同构于平面二部图G的共振图,则Hτ为森林,其分量为树且同构于G的不同于K2的基本分量的内对偶;特别地,若H同构于平面基本二部图G的共振图,则Hτ为树且同构于G的内对偶。Theorem 4.3表明,至少含一条边的菊花立方体H同构于平面二部图的共振图当且仅当Hτ为森林;特别地,H同构于平面基本二部图的共振图当且仅当Hτ为树。必要性由Lemma 4.2得到;充分性通过对每个树归纳构造内对偶同构于该树的外围2-可着色图,再取不交并并应用Lemma 4.1与Corollary 3.3得到。文中注记指出,Qn(n≥2)的τ-图为KnC,故由Theorem 4.3不能是任何平面基本二部图的共振图;而Qn(n≥1)可作为具有n个偶圈基本分量的平面弱基本二部图的共振图,因为偶圈的共振图为K2。Lemma 4.4表明:(i) 对n≥1,Γnτ?Pn;(ii) 对n≥3,Λnτ?Cn;(iii) 对n≥3,Λn不能是任何平面二部图的共振图。其证明利用Γn?K(PnC)、Λn?K(CnC)以及关于单纯形图与τ-图的已知恒等式,并由(ii)与Theorem 4.3推出(iii)。Remark指出,已有关于中位图G为Γn当且仅当每个Θ-类均为外围类且Gτ?Pn的结果蕴含Lemma 4.4(i);由Corollary 3.3,Γn是τ-图为Pn的唯一菊花立方体;对n≥3,非同构中位图Pn+1与Γn具有相同τ-图Pn,非同构部分立方体C2n与Λn具有相同τ-图Cn。Question 4.1提出:对n≥3,Λn是否为τ-图为Cn的唯一菊花立方体或唯一中位图;能否类似已有结果用τ-图刻画Λn。Proposition 4.5表明,对n≥3,Lucas立方体Λn的τ-图Λnτ为Cn;证明定义Θ类Xi为两端二进制码仅第i位不同的边类,证明X1邻接X2与Xn,且不邻接Xj(3≤j≤n?1),并利用凸P3与4-圈排除得出每个顶点在Λnτ中度为2,从而Λnτ?Cn。

讨论与结论:讨论部分强调森林型τ-图在同构判定中的关键作用;当τ-图不是森林时,相同τ-图未必对应同构菊花立方体。论文将同构判据应用于共振图识别,给出菊花立方体作为平面二部图或平面基本二部图共振图的τ-图条件,并以不同证明呈现Fibonacci立方体和Lucas立方体τ-图的已知性质;同时提出用τ-图刻画Lucas立方体的开放问题。研究结论翻译为:若A与B是τ-图为森林的菊花立方体,则A与B同构当且仅当其τ-图同构。一个至少含一条边的菊花立方体是平面二部图G的共振图当且仅当其τ-图是一个森林,且该森林同构于删除G中所有禁止边所得子图的内对偶。特别地,一个菊花立方体是顶点数大于2的平面基本二部图G的共振图当且仅当其τ-图是一棵树且同构于G的内对偶。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号