二面体群的立方Cayley图的零强制数

《Discrete Mathematics》:The zero forcing number for cubic Cayley graphs of dihedral groups

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

编辑推荐:

  摘要:图 Γ 的零迫数值 Z(Γ) 是零迫集 Z?V(Γ) 的最小基数。在本文中,我们研究了立方体连通凯莱图 Γ=Cay(D2n,S) 的零迫数值,其中 D2n=〈a,b|an=b2=1,bab=a?1〉 是阶为 2n 的二面体群。当 Γ 与完全图 K4、梯形图 L(2n) 或莫

  摘要:图 Γ 的零迫数值 Z(Γ) 是零迫集 Z?V(Γ) 的最小基数。在本文中,我们研究了立方体连通凯莱图 Γ=Cay(D2n,S) 的零迫数值,其中 D2n=〈a,b|an=b2=1,bab=a?1〉 是阶为 2n 的二面体群。当 Γ 与完全图 K4、梯形图 L(2n) 或莫比乌斯梯形图 M(2n) 同构时,我们精确地确定了 Z(Γ) 的值。对于其余类型,即类型 III 的情况,我们在两个标准化的素数情况下给出了确切的值,并一般性地建立了明确的下界和上界。这些估计值是用 Γ 的周长以及与生成集合中指数差异相关的算术参数来表示的。

引言:在本文中,所有考虑的图都是有限的、无方向的且简单的。对于此处未定义的任何术语,可以参考 [6]。

对于简单图 Γ 的最小秩问题,是代数图论和组合矩阵论中的一个核心问题。它询问所有非对角线元素为 0 或非 0 的实对称矩阵中的最小秩,用 mr(Γ) 表示;图的最大零度是同一组矩阵中的最大零度,用 M(Γ) 表示。显然,M(Γ)+mr(Γ)=|V(Γ)|。为了获得 M(Γ) 的上界,在 2008 年的一次线性代数研讨会上,AIM 最小秩-特殊图工作组 [2] 提出了零迫的概念。此外,受物理思想的启发,Burgarth 和 Giovannetti [7] 独立地引入了零迫的概念。

图 Γ 由一组顶点 V(Γ) 和一组边 E(Γ) 组成,其中边是一对无序的顶点。设 Z 是 V(Γ) 的一个非空子集。最初将 Z 和 V(Γ)?Z 中的顶点分别着色为黑色和白色。定义以下颜色变换规则:对于 V(Γ) 中的每一个黑色顶点 u,如果 u 恰好有一个白色邻居 v,则将 v 重新标记为黑色;我们说 u 强制 v 变为黑色。如果通过反复应用颜色变换规则使得 V(Γ)?Z 中的所有顶点都变为黑色,则子集 Z 被称为零迫集。图 Γ 的零迫数值是在所有零迫集 Z?V(Γ) 中 |Z| 的最小值,用 Z(Γ) 表示(在文献中 juga 用 F(Γ) 表示)。对于图 Γ 的一个零迫集 Z,应用颜色变换规则将 V(Γ)?Z 中的所有顶点强制变为黑色的过程称为 Z 在 Γ 中的强制过程。零迫问题在计算最小秩和最大零度方面得到了广泛应用,并作为具有各种应用的有趣图不变量进行了研究 [5]、[8]、[17]。在 [2] 中,获得了一些关于图零迫的基本结果,例如树和两条路径的笛卡尔积。Kalinowski 等人 [20] 表明,如果 Γ 是具有 n 个顶点的 d-正则图,则 Z(Γ)≥n(1+2λmind?λmin)。此外,Vatandoost 和 Golkhandy Pour [26] 在某些特殊情况下获得了二面体群上的凯莱图的零迫数值。因此,确定所有立方体图(以及更一般的 k-正则图)的界限是一个有趣且具有挑战性的问题。有关零迫的更多详细信息,请参见 [9]、[10]、[11]、[14]、[15]、[22]、[25]、[27]。受这些结果的启发,我们的工作重点研究了二面体群上的凯莱图的零迫数值。

设 G 是一个具有单位元素 1 的有限群,设 S 是 G 的一个子集。我们用 〈S〉 表示由 S 中的元素生成的 G 的子群。如果 S=S?1={s?1:s∈S},则称 S 是 G 的一个逆封闭子集。现在设 S 是 G 的一个逆封闭子集且 1?S。关于 S 的凯莱图 Γ 是这样的图:顶点集为 G,且当且仅当 hg?1∈S 时,即存在 s∈S 使得 h=sg,G 中的两个顶点 g∈G 和 h∈G 是相邻的。众所周知并且容易证明,如果 〈S〉=G,则 Cay(G,S) 是连通的。凯莱图长期以来一直是代数图论中的活跃研究课题。它们与各种图参数和网络结构密切相关;参见 [1]、[3]、[16]、[19]、[26]。

在本文中, let D2n=〈a,b|an=b2=1,bab=a?1〉 表示阶为 2n 的二面体群。用 (u,v) 表示整数 u 和 v 的最大公约数。我们现在介绍两个将在后续研究中使用的标准立方体图家族。对于 n≥3,梯形图 L(2n) 是通过添加边 uivi(对于 1≤i≤n)从两个顶点不相交的循环 Cn 的副本 (u1,u2,…,un,u1) 和 (v1,v2,…,vn,v1) 获得的。等价地,L(2n)?Cn□P2。莫比乌斯梯形图 M(2n) 是通过将一对平行的循环边替换为一对交叉的边从 Cn□P2 获得的。更准确地说,它是通过从 L(2n) 中删除 u1un 和 v1vn,然后添加 u1vn 和 v1un 获得的。

尽管已经研究了几种二面体群上的凯莱图的零迫数值,但对于连通的二面体群立方体凯莱图的一般处理方法仍然不可用。在本文中,我们研究了所有连通的二面体群立方体凯莱图的零迫数值。我们的主要结果总结在以下定理中。

定理 1.1:设 Γ=Cay(D2n,S) 是一个在二面体群 D2n 上的立方体连通凯莱图,g 是 Γ 的周长。那么以下情况之一成立:
(1) Γ?K4,且 Z(Γ)=3。
(2) Γ?L(2n),且 Z(Γ)=min?{n,4}。
(3) Γ?M(2n),且 Z(Γ)=4。
(4) 如果 S={bak1,bak2,bak3} 且 n 是一个奇素数,那么 Γ?Cay(D2p,{b,ba,bas}),其中 s 是 {2,…,p?1} 中最小的整数,{b,ba,bas} 是 D2p 的一个自同构下的 S 的像,并且以下情况之一成立:
(i) 如果 s=2,则 Z(Γ)=4;
(ii) 如果 3≤s≤max?{3,?p+13?},那么 6≤Z(Γ)≤2s。特别地,如果 s=3,则 Z(Γ)=6;
(iii) 如果 s≥max?{4,?p+23?},那么 6≤Z(Γ)≤2p?4s+4。
(5) 如果 S={bak1,bak2,bak3} 且 n 是一个偶数,定义 d1=max?{(n,ki?kj):1≤i< />1,则 max?{g,d1}≤Z(Γ)≤2nd1+d1?2;
(iii) 如果 d0=1
定理 1.1 精确地确定了部分 (1)–(3) 中图的 z(γ),包括 z(l(6))=3。在部分 (4) 的素数情况下,它也为 s=2 和 s=3 的标准化情况给出了确切的值。对于其余情况,定理根据连接集产生的参数给出了明确的界限。在部分 (4)(ii) 中,上下界之间的差异最多为 2s?6。因此,对于较小的 s 值,估计最为有效;例如,当 p=13 时,s=4 得到 6≤z(γ)≤8。对包含单位顶点 x0=1 的所有大小为 6 和 7 的集合进行了详尽检查,并验证了大小为 8 的一个集合,得到 z(cay(d26,{b,ba,ba4}))=8。这种对包含 x0 的集合的限制是由顶点传递性证明的。因此,上界可以是精确的。

引理 3.6 表明对于每个 2≤s≤p?1,都有 z(γ)≤2s。部分 (4) 中的划分涉及到可用的 2s 和 2p?4s+4,在 3s=p+2 的情况下两者一致;后者在引理 3.7 的假设下使用。部分 (4)(ii) 中的范围明确包括 (p,s)=(7,3),对于这种情况,z(γ)=6。

对于较大的最小代表值,部分 (4)(iii) 给出了例如 (p,s)=(19,8) 时的 6≤z(γ)≤10,以及 (p,s)=(31,12) 时的 6≤z(γ)≤18。这些是界限,而不是确切值的断言。当 p=31 时,参数 s=15 不是最小代表值,因为它相当于 s=3,因此 z(γ)=6。对于部分 (5) 和 (6) 中的合数情况,估计取决于周长和 d1;在部分 (6) 中,这些情况通过 d0 和 d1 来区分。

本文的其余部分组织如下。在第 2 节中,我们介绍了后来使用的初步概念和结果。在第 3 节中,我们通过考虑三种类型的二面体群立方体凯莱图来证明主要定理。

本文的初步结果:在本文中,我们关注立方体连通凯莱图 cay(d2n,s) 的零迫数值,因此 |s|=3。由于 d2n 的元素形式为 biaj,其中 0≤i≤1 且 0≤j≤n?1,我们可以假设 s={ak,a?k,bai}(如果 n 是偶数),或 s={an/2,bai,baj}(n 是偶数),或 s={bak1,bak2,bak3}。那么图 cay(d2n,s) 分别被称为类型 i、类型 ii 或类型 iii,如果 s 具有相应的形式 {ak,a?k,bai}、{an/2,bai,baj}、{bak1,bak2,bak3}。

表示整数 a 和 b 的最大公约数为 (a,b)。

二面体群立方体凯莱图的零迫数值:众所周知,z(k4)=3。根据 [2, 定理 3.8 和命题 3.9],z(l(2n))=min?{n,4},且 z(m(2n))=4(对于 n≥3)。因此,类型 i 和类型 ii 的二面体群立方体连通凯莱图的零迫数值得到了确定,然后定理 1.1 的部分 (1)–(3) 成立。接下来,我们转向类型 iii 的图。

我们根据参数 n 对立方体连通凯莱图 cay(d2n,s) 进行分类,得到三种不同的情况:(1) n 是一个奇素数;(2) n 是一个偶数;(3) n...

结论与进一步的方向:在本文中,我们研究了二面体群上的立方体连通凯莱图的零迫数值。利用 d2n 上立方体凯莱图的分类,我们考虑了三种可能的连接集类型。对于类型 i 和类型 ii 的图,相应的凯莱图同构于 k4、梯形图或莫比乌斯梯形图。它们的零迫数值已经确定。对于类型 iii 的图,我们使用砖积表示法得到了确切的值。

致谢:guang li 受到了中国国家自然科学基金(编号 12301449, 12371353)、山东省自然科学基金(编号 zr2022ma077)以及山东省高校青年科学家科技创新项目(编号 2024kjg014)的支持。

mengzhi li | huixian li | pengkai wang | guang li γ?cay(d2n,{b,ba,bas}) 对于某个 s,并且 max?{g,d1}≤z(γ)≤min?{2s,2nd1+d1?2}。 定理 1.1 精确地确定了部分 (1)–(3) 中图的 z(γ),包括 z(l(6))=3。在部分 (4) 的素数情况下,它也为 s=2 和 s=3 的标准化情况给出了确切的值。对于其余情况,定理根据连接集产生的参数给出了明确的界限。在部分 (4)(ii) 中,上下界之间的差异最多为 2s?6。因此,对于较小的 s 值,估计最为有效;例如,当 p=13 时,s=4 得到 6≤z(γ)≤8。对包含单位顶点 x0=1 的所有大小为 6 和 7 的集合进行了详尽检查,并验证了大小为 8 的一个集合,得到 z(cay(d26,{b,ba,ba4}))=8。这种对包含 x0 的集合的限制是由顶点传递性证明的。因此,上界可以是精确的。 引理 3.6 表明对于每个 2≤s≤p?1,都有 z(γ)≤2s。部分 (4) 中的划分涉及到可用的 2s 和 2p?4s+4,在 3s=p+2 的情况下两者一致;后者在引理 3.7 的假设下使用。部分 (4)(ii) 中的范围明确包括 (p,s)=(7,3),对于这种情况,Z(Γ)=6。 对于较大的最小代表值,部分 (4)(iii) 给出了例如 (p,s)=(19,8) 时的 6≤z(γ)≤10,以及 (p,s)=(31,12) 时的 6≤z(γ)≤18。这些是界限,而不是确切值的断言。当 p=31 时,参数 s=15 不是最小代表值,因为它相当于 s=3,因此 z(γ)=6。对于部分 (5) 和 (6) 中的合数情况,估计取决于周长和 d1;在部分 (6) 中,这些情况通过 d0 和 d1 来区分。 本文的其余部分组织如下。在第 2 节中,我们介绍了后来使用的初步概念和结果。在第 3 节中,我们通过考虑三种类型的二面体群立方体凯莱图来证明主要定理。 本文的初步结果:在本文中,我们关注立方体连通凯莱图 cay(d2n,s) 的零迫数值,因此 |s|=3。由于 d2n 的元素形式为 biaj,其中 0≤i≤1 且 0≤j≤n?1,我们可以假设 s={ak,a?k,bai}(如果 n 是偶数),或 s={an/2,bai,baj}(n 是偶数),或 s={bak1,bak2,bak3}。那么图 cay(d2n,s) 分别被称为类型 i、类型 ii 或类型 iii,如果 s 具有相应的形式 {ak,a?k,bai}、{an 2,bai,baj}、{bak1,bak2,bak3}。 表示整数 a 和 b 的最大公约数为 (a,b)。 二面体群立方体凯莱图的零迫数值:众所周知,z(k4)=3。根据 [2, 定理 3.8 和命题 3.9],z(l(2n))=min?{n,4},且 z(m(2n))=4(对于 n≥3)。因此,类型 i 和类型 ii 的二面体群立方体连通凯莱图的零迫数值得到了确定,然后定理 1.1 的部分 (1)–(3) 成立。接下来,我们转向类型 iii 的图。 我们根据参数 n 对立方体连通凯莱图 cay(d2n,s) 进行分类,得到三种不同的情况:(1) n 是一个奇素数;(2) n 是一个偶数;(3) n... 结论与进一步的方向:在本文中,我们研究了二面体群上的立方体连通凯莱图的零迫数值。利用 d2n 上立方体凯莱图的分类,我们考虑了三种可能的连接集类型。对于类型 i 和类型 ii 的图,相应的凯莱图同构于 k4、梯形图或莫比乌斯梯形图。它们的零迫数值已经确定。对于类型 iii 的图,我们使用砖积表示法得到了确切的值。 致谢:guang li 受到了中国国家自然科学基金(编号 12301449, 12371353)、山东省自然科学基金(编号 zr2022ma077)以及山东省高校青年科学家科技创新项目(编号 2024kjg014)的支持。 mengzhi li | huixian li | pengkai wang | guang>

定理 1.1 精确地确定了部分 (1)–(3) 中图的 z(γ),包括 z(l(6))=3。在部分 (4) 的素数情况下,它也为 s=2 和 s=3 的标准化情况给出了确切的值。对于其余情况,定理根据连接集产生的参数给出了明确的界限。在部分 (4)(ii) 中,上下界之间的差异最多为 2s?6。因此,对于较小的 s 值,估计最为有效;例如,当 p=13 时,s=4 得到 6≤z(γ)≤8。对包含单位顶点 x0=1 的所有大小为 6 和 7 的集合进行了详尽检查,并验证了大小为 8 的一个集合,得到 z(cay(d26,{b,ba,ba4}))=8。这种对包含 x0 的集合的限制是由顶点传递性证明的。因此,上界可以是精确的。

引理 3.6 表明对于每个 2≤s≤p?1,都有 z(γ)≤2s。部分 (4) 中的划分涉及到可用的 2s 和 2p?4s+4,在 3s=p+2 的情况下两者一致;后者在引理 3.7 的假设下使用。部分 (4)(ii) 中的范围明确包括 (p,s)=(7,3),对于这种情况,z(γ)=6。

对于较大的最小代表值,部分 (4)(iii) 给出了例如 (p,s)=(19,8) 时的 6≤z(γ)≤10,以及 (p,s)=(31,12) 时的 6≤z(γ)≤18。这些是界限,而不是确切值的断言。当 p=31 时,参数 s=15 不是最小代表值,因为它相当于 s=3,因此 z(γ)=6。对于部分 (5) 和 (6) 中的合数情况,估计取决于周长和 d1;在部分 (6) 中,这些情况通过 d0 和 d1 来区分。

本文的其余部分组织如下。在第 2 节中,我们介绍了后来使用的初步概念和结果。在第 3 节中,我们通过考虑三种类型的二面体群立方体凯莱图来证明主要定理。

本文的初步结果:在本文中,我们关注立方体连通凯莱图 cay(d2n,s) 的零迫数值,因此 |s|=3。由于 d2n 的元素形式为 biaj,其中 0≤i≤1 且 0≤j≤n?1,我们可以假设 s={ak,a?k,bai}(如果 n 是偶数),或 s={an/2,bai,baj}(n 是偶数),或 s={bak1,bak2,bak3}。那么图 cay(d2n,s) 分别被称为类型 i、类型 ii 或类型 iii,如果 s 具有相应的形式 {ak,a?k,bai}、{an/2,bai,baj}、{bak1,bak2,bak3}。

表示整数 a 和 b 的最大公约数为 (a,b)。

二面体群立方体凯莱图的零迫数值:众所周知,z(k4)=3。根据 [2, 定理 3.8 和命题 3.9],z(l(2n))=min?{n,4},且 z(m(2n))=4(对于 n≥3)。因此,类型 i 和类型 ii 的二面体群立方体连通凯莱图的零迫数值得到了确定,然后定理 1.1 的部分 (1)–(3) 成立。接下来,我们转向类型 iii 的图。

我们根据参数 n 对立方体连通凯莱图 cay(d2n,s) 进行分类,得到三种不同的情况:(1) n 是一个奇素数;(2) n 是一个偶数;(3) n...

结论与进一步的方向:在本文中,我们研究了二面体群上的立方体连通凯莱图的零迫数值。利用 d2n 上立方体凯莱图的分类,我们考虑了三种可能的连接集类型。对于类型 i 和类型 ii 的图,相应的凯莱图同构于 k4、梯形图或莫比乌斯梯形图。它们的零迫数值已经确定。对于类型 iii 的图,我们使用砖积表示法得到了确切的值。

致谢:guang li 受到了中国国家自然科学基金(编号 12301449, 12371353)、山东省自然科学基金(编号 zr2022ma077)以及山东省高校青年科学家科技创新项目(编号 2024kjg014)的支持。

mengzhi li | huixian li | pengkai wang | guang li>
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号