两个圈的卡氏积的群超幻标号
Group Supermagic Labeling of the Cartesian Product of Two Cycles
DOI: 10.12677/pm.2025.157210, PDF, HTML, XML,    国家自然科学基金支持
作者: 邓贵新*, 刘宇浩:南宁师范大学数学与统计学院,广西 南宁
关键词: 超幻标号群超幻标号图的卡氏积Supermaigc Labeling Group Supermagic Labeling Cartesian Product of Graph
摘要: 图的各种幻型标号的存在性是近年来图论中的一个研究热点。在该领域的研究中用到了图论、群论、数论、线性代数等数学工具。设 G=( V,E ) 是一个有限简单图, A 是一个有限交换群。 G 的一个 A -超幻标号是一个双射 φ:EA ,满足存在 cA ,使得对所有的 xV ,有 eE( x ) φ( e ) =c ,其中 E( x ) 代表所有与顶点 x 关联的边的集合。对任意 n3 ,记 C n n 个顶点的圈。我们利用有限交换群元素的排列得到了 C m C n A -超幻标号存在性的新的充分条件。
Abstract: The existence of various magic-type labeling of graphs is a research hotspot in recent years. Many mathematical tools, such as graph theory, group theory, number theory, and linear algebra, are used in the research of this area. Let G=( V,E ) be a finite simple graph and let A be a finite abelian group. An A -supermagic labeling of G is a bijection φ:EA which satisfies that there exists cA , such that eE( x ) φ( e ) =c for any xV , where E( x ) is the set of edges which adjacent to x . For any n3 , let C n denote the cycle with n vertices. We use some results on the arrangement of elements of finite abelian groups to obtain new sufficient conditions such that the Cartesian product of cycles C m C n admits A -supermagic labeling.
文章引用:邓贵新, 刘宇浩. 两个圈的卡氏积的群超幻标号[J]. 理论数学, 2025, 15(7): 83-89. https://doi.org/10.12677/pm.2025.157210

1. 引言

G=( V( G ),E( G ) ) 是一个有限简单图,对任意 xV( G ) ,我们用 N( x ) 表示与 x 相连的顶点集合,用 E( x ) 表示以 x 为一个顶点的边的集合。对任意正整数 n2,m3 ,我们用 K n , C m 分别代表 n 个顶点的完全图和 m 个顶点的圈,设有两个图 G 1 , G 2 。它们的卡氏积记为 G= G 1 G 1 ,其中 V( G )=V( G 1 )×V( G 2 ) ,对任意 z 1 =( x 1 , y 1 ), z 2 =( x 2 , y 2 )V( G ) z 1 z 2 E( G ) 当且仅当 x 1 = x 2 , y 1 y 2 E( G 2 ) 或者 x 1 x 2 E( G 1 ), y 1 = y 2 。图上的一个标号通常指定义域为 V( G ) 或者 E( G ) V( G )E( G ) 的一个映射。研究图上具有各种特殊性质标号的存在性是图论中的一个热门研究方向。本文研究的是其中一类被称为幻型标号的标号。

如果存在一个双射 φ:E( G ){ 1,2,,n } 满足条件:存在一个整数 c ,使得对任意的 xV( G ) ,有 eE( x ) φ( e ) =c ,那么称 G 是一个超幻图,并称 φ G 的一个超幻标号,而常数 c 称为超幻标号 φ 的幻常数。反之,如果对任意不同的两个顶点 x,yV( G ) 均有 eE( x ) φ( e ) eE( y ) φ( e ) ,那么称 φ 是一个反幻标号。如果一个图 G 有超幻标号(反幻标号),那么称该图是一个超幻图(反幻图)。Hartsfield和Ringel在文献[1]中提出了如下著名猜想。

猜想1.1 任一个不等于 K 2 的有限简单连通图都是反幻图。

很多学者都研究过上述的猜想。一些简单的图例,如圈、路、完全图(除了 K 2 )等,被证明都是反幻图。Cranton在[2]中证明了任一个正则的二部图都是反幻图。文献[3] [4]则证明了一些图的卡氏积是反幻图。文献[5]证明了如果 G 是一个树并且其中的2度点最多只有一个,那么 G 是反幻图。但至今仍不知道猜想1.1是否对任意的树都成立。Alon等人[6]证明了如果一个图的边比较多,那么该图是反幻图。

超幻图的概念则是Stewaut于1966年提出的,见[7]。并且Stewart [8]完全刻画了哪些完全图是超幻图。Ivanco在[9] [10]证明了如下结论。

定理1.2 m,n3 是两个整数

(1) 如果 m7,n5 且都是奇数,那么 K m K n 是超幻图;

(2) 如果 m=n 或者 m,n 都是偶数,那么 C m C n 是超幻图。

并且Ivanco还猜想对任意整数 m,n3 C m C n 都是超幻图。本文考察超幻标号的一种自然推广,称为群超幻标号,严格定义如下。

定义1.3 G=( V( G ),E( G ) ) 是一个有限简单图, A 是一个有限交换群, G 的一个 A -超幻标号是一个双射 φ:E( G )A ,满足存在 cA ,使得对所有的 xV ,有 eE( x ) φ( e ) =c

由定义马上可以得到,如果 G 是超幻图,那么 G Z n -超幻图,其中 n=| E( G ) | 。文献[11]中证明了如果 m,n 的奇偶性相同,那么对任意阶等于 2mn 的有限交换群 A C m C n 都是 A -超幻图。我们利用有限交换群上的排列给出了新的条件使得 C m C n 都是 A -超幻图。

2. 主要结论及其证明

我们需要如下的引理。

引理2.1 ([12]) A 是一个有限交换群, B A 的一个子群且 | A | | B | =2k ,那么存在 c, x i , y i A,i=1,2,,k 满足 x i + y i =c A=( i=1 k ( x i +B ) )( i=1 k ( y i +B ) )

引理2.2 ([12]) A 是一个有限交换群, H A 的一个子群,设 N 是一个正整数满足 | H || N,N || A | 。那么存在 A N 阶子群 B 满足 HB

引理2.3 ([13])假设 B 是交换群 A 的一个 l 阶子群,并且 cB

(1) 如果存在 k 阶元素 hB 使得 r= | B | k 是一个奇数,那么 ( c+B )B 中元素可以排列为 x 1 , x 2 ,, x 2l 满足 B={ x 2i :1il } 且对任意 i x i + x i+1 + x i+r + x i+r+1 =2c+h

(2) 如果 2|l ,那么 ( c+B )B 中元素可以排列为 x 1 , x 2 ,, x 2l 满足 B={ x 2i :1il } x i + x i+1 + x i+l + x i+l+1 =2c

以上 x i 的下标均模 2l 计算。

m,n 都是偶数的时候,文献[11]证明了对任意阶为 2mn 的交换群 A C m C n 都是 A -超幻图,但是文献中关于这一结论的证明很长。我们这里将 C m C n 的超幻标号与群元素的排列建立起联系,给出了这一结论更简洁的证明,并进一步得到新的充分条件使得 C m C n 都是 A -超幻图。首先我们定义图 C m C n 中的对角线和对角圈。

为方便起见我们将 C n 的顶点集合记为 { 0,1,,n1 } ,其中 ijE( C n ) 当且仅当 ij±1( modn ) 。这样 C m C n 中的顶点集可以记为 V={ ( i,j ):0im1,0jn1 } 。并且两个顶点 ( i,j )=( i , j ) 当且仅当 i i ( modm ) j j ( modn ) 。我们用 e ij h 表示边 ( i,j )( i+1,j ) ,并称这样的边为水平边,用 e ij v 表示边 ( i,j )( i,j+1 ) ,并称这样的边为竖直边。令 E h ={ e ij h :0im1,0jn1 } E v ={ e i,j v :0im1,0jn1 } 分别是水平边和竖直边构成的集合。那么 C m C n 的边集 E= E h E v 。令 l,d 分別是 m,n 的最小公倍数和最大公因子,由初等数论知识知道,对任意正整数 r,s 存在

i{ 0,1,,d1 } j{ 0,1,,l1 } 使得 { jr( modm ) i+js( modn )

所以我们可以将顶点集合分为 V( C m C n )= i=0 d1 D i ,其中 D i ={ ( j,j+i ):0j2l1 }

引理2.4 对任意正整数 m,n3 和阶为 2mn 的交換群 A C m C n A -超幻图当且仅当 A 中的元素恰好可以排成一个 d×2l 的排列 ( x ij ) 1id,1j2l 满足存在常数 cA 使得对任意偶数 j 以下成立:

(1) 对 i=1,2,,d1 x ij + x i,j+1 + x i+1,j1 + x i+1,j =c

(2) x d,j + x d,j+1 + x 1,j+2t1 + x 1,j+2t =c

其中 x ij 的第二个下标模 2l 计算,且 { t0( modm ) td( modn )

证明:注意到对任意 i=0,1,,d1 ,我们从 ( 0,i ) 开始,依次交替让第一个、第二个坐标加1得到 V( C m C n ) 中的 2l 个顶点。

( 0,i ),( 1,i ),( 1,i+1 ),( 2,i+1 ),,( l,i+l1 )

显然这 2l 个顶点以及它们之间的边构成了一个长度为 2l 的圈,将该圈记为 L i ,它的点集是 D i D i1 。从 ( 0,i );( 1,i ) 开始这 2l 条边依次为:

e 0i h , e 1,i v , e 1,i+1 h , e 2,i+1 v ,, e l1,i+l1 h , e l1,i+1 v ,0id1

所以如果我们有满足引理中 d×2l 的排列 { x ij } ,定义边标号 σ:EA 使得 σ 在上面的圈 L i 上的标号依次就是 x i+1,j ,0id1j2l

特别地,当 i=0,1,,d2 的时候,在 D i 上的点 ( j,j+i ) 的权重就是 x i+1,2j + x i+1,2j+1 + x i+2,2j1 + x i+2,2j ,而当 i=d1 时, ( j,j+d1 ) 的权重就等于 x d,2j + x d,2j+1 + x 1,2t+2j1 + x 1,2t+2j

这就证明了引理。

定理2.5 m,n 都是不小于4的偶数,那么对任意阶为 2mn 的交换群 A C m C n 都是 A -超幻图。

证明:我们取 A 的一个阶等于 d 的子群 B 。由于 | A | | B | =2l 是一个偶数,由引理2.1存在 x i , y i ,cA,i=1,2,,l ,使得 x i + y i =c A=( i=1 l ( x i +B ) )( i=1 l ( y i +B ) ) 。设 B={ b 1 , b 2 ,, b d } ,为方便起见我们让 x i , y i 的下标模 l 计算,而 b j 的下标模 d 计算。我们构造如下 A 的元素的 d×2l 排列 ( z ij ) 1id,1j2l :对 i=1,2,,d ,对 i 的奇偶性分别定义 z ij ,构造如下:

如果 2i z ij :={ x i+1 2 + b i ,2j y j 2 b i ,2|j

如果 2|i z ij :={ x i+1 2 + b i ,2j y j 2 +1 b i ,2|j

由假设 x i , y i 的下标模 l 计算,可知道 z ij 定义是良好的并且第二个下标可以看成模 2l 计算,又由于 B 是一个子群,所以 B=B 。这样该 d×2l 排列的第 i 行的元素全体等于 { x j + b i :1jl }{ y j b i :1jl } 。所以 A 中元素均在该 d×2l 排列中出现一次。我们还需要验证引理2.4中的条件(1)和(2)也成立。对 i=1,2,,d 和任意偶数 j ,由标号的构造有如下三种情况:

1): 2i,1id1

z i,j + z i,j+1 + z i+1,j1 + z i+1,j =( y j 2 b i )+( x j 2 +1 + b i )+( x j 2 + b i+1 )+( y j 2 +1 b i+1 ) =( x j 2 + y j 2 )+( x j 2 +1 + y j 2 +1 ) =c+c =2c.

2): 2|i,1id2

z i,j + z i,j+1 + z i+1,j1 + z i+1,j =( y j 2 +1 b i )+( x j 2 +1 + b i )+( x j 2 + b i+1 )+( y j 2 b i+1 ) =( x j 2 + y j 2 )+( x j 2 +1 + y j 2 +1 ) =c+c =2c.

3): i=d ,对任意整数 t

z d,j + z d,j+1 + z 1,j+2t1 + z 1,j+2t =( y j 2 +1 b d )+( x j 2 +1 + b d )+( x j 2 +t + b 1 )+( y j 2 +t b 1 ) =( x j 2 +1 + y j 2 +1 )+( x j 2 +t + y j 2 +t ) =c+c =2c.

由引理2.4我们知道 C m C n A -超幻图。

对任意有限群 A ,我们用 exp( A ) 表示 A 的指数,即最小的正整数 N 使得对任意 aA Na=0

定理2.6 m,n3 是两个整数, A 是一个阶为 2mn 的有限交換群。如果 l d |exp( A ) C m C n A -超幻图。

证明:如果 m,n 同奇偶,由之前的结论知道 C m C n A -超幻图,下设 2|m,2n 。由假设可以取 A 的一个阶为 l d 的元素 h ,并令 H 是由 h 生成的循环子群。由引理2.2存在 A l 阶子群 B ,满足 HB 。由于 | A | | B | =2d ,由引理2.1存在 c, x i , y i A,i=1,2,,d 满足 x i + y i =c A=( i=1 d ( x i +B ) )( i=1 d ( y i +B ) )

我们先证明如下断言。

断言:假设有一个 B( c+B ) 元素的 d×2l 的排列 ( z ij ) 1id,1j2l 満足如下条件:

(i) 对任意 i{ 1,2,,d } B( c+B )={ z ij :1j2l }

(ii) 对任意 i{ 1,2,,d } z i1 , z i2 ,, z i,2l B c+B 中的元素交替出现;

(iii) 存在 aA 使得对 i=1,2,,d1 和任意 j z ij + z i,j+1 + z i+1,j1 + z i+1,j =a z d,j + z d,j+1 + z 1,j+2t1 + z 1,j+2t =a ,其中 z ij 的第二个下标模 2l 计算,且 { t0( modm ) td( modn ) ,那么 C m C n A -超幻图。

断言的证明:我们构造另一个 d×2l 的排列 ( u ij ) 1id,1j2l ,定义如下:对任意给定的 i=1,2,,d ,令 u ij :={ z ij + x i , z ij B z ij x i , z ij ( c+B ) ,由条件(i)以及 x i + y i =c 知道 { u ij :1j2l }=( x i +B )( x i +c+B )=( x i +B )( y i +B ) 。所以 { u ij :1id,1j2l }=( i=1 d ( x i +B ) )( i=1 d ( y i +B ) )=A ,这样 A 中任一元素恰好在排列 ( u ij ) 1id,1j2l 中出现一次,由条件(ii)以及构造知道 u ij + u i,j+1 = z ij + z i,j+1 + x i x i = z ij + z i,j+1 ,即排列 ( u ij ) 1id,1j2l 相邻两项之和等于原排列 ( z ij ) 1id,1j2l 相应位置的相邻两项之和。结合条件(iii)知道排列 ( u ij ) 1id,1j2l 满足引理2.4中的条件,所以 C m C n A -超幻图,断言证毕。

由于 hB ,由引理2.3我们可以将 B( c+B ) 中的 2l 个元素交替排列为 ( z i ) i=1 2l 满足对任意 i (模 2l 计算)

z i + z i+1 + z i+d + z i+d+1 =2c+h (1)

现在我们定义一个 d×2l 排列 ( x ij ) 如下,对 1id ,令 x ij := z i( d+1 )+j 。注意 z j 的下标,以及 x ij 的第二个下标都是模 2l 计算。

下面我们还需要验证排列 ( x ij ) 满足引理2.4中的条件(1)和(2)。首先设 1id1 1j2l 。令 i 1 =i( d+1 )+j 。那么由式(1)有

x ij + x i,j+1 + x i+1,j1 + x i+1,j = z i( d+1 )+j + z i( d+1 )+j+1 + z ( i+1 )( d+1 )+j1 + z ( i+1 )( d+1 )+j = z i 1 + z i 1 +1 + z i 1 +d + z i 1 +d+1 =2c+h.

其次取 t 满足 { t0( modm ) td( modn ) ,令 i 2 =d+j+2t,k=d 2t d 。注意 d 是奇数,所以 k 也是奇数.由式(1)我们有

x d,j + x d,j+1 + x 1,j+2t1 + x 1,j+2t = z d( d+1 )+j + z d( d+1 )+j+1 + z d+j+2t + z d+j+2t+1 = z i 2 + z i 2 +1 + z i 2 +kd + z i 2 +kd+1 = r=0 k1 ( 1 ) r ( z i 2 +rd + z i 2 +rd+1 + z i 2 +( r+1 )d + z i 2 +( r+1 )d+1 ) = r=0 k1 ( 1 ) r ( 2c+h ) =2c+h.

由引理2.4知道 C m C n A -超幻图。

3. 小结和展望

本文将两个圈的卡氏积 C m C n 上的群超幻标号的存在性问题转化成了一个交换群上特殊排列存在性问题,进而利用一些特殊子群的陪集分解得到了 C m C n 上存在群超幻标号的新的充分条件。由于 C m C n 是一类特殊的4度凯莱图,所以本文方法有可能运用到4度凯莱图上的群超幻标号上,或者更一般的凯莱图上,这也是我们进一步希望研究的问题。

基金项目

本论文由广西自然科学面上项目(2025GXNSFAA069810)和国家自然科学基金项目(12161059)资助。

NOTES

*通讯作者。

参考文献

[1] Hartsfield, N. and Ringel, G. (1990) Pearls in Graph Theory: A Comprehensive Introduction. Dover Publications.
[2] Cranston, D.W. (2008) Regular Bipartite Graphs Are Antimagic. Journal of Graph Theory, 60, 173-182.
https://doi.org/10.1002/jgt.20347
[3] Cheng, Y. (2008) A New Class of Antimagic Cartesian Product Graphs. Discrete Mathematics, 308, 6441-6448.
https://doi.org/10.1016/j.disc.2007.12.032
[4] Liang, Y. and Zhu, X. (2013) Anti-Magic Labelling of Cartesian Product of Graphs. Theoretical Computer Science, 477, 1-5.
https://doi.org/10.1016/j.tcs.2012.12.023
[5] Liang, Y., Wong, T. and Zhu, X. (2014) Anti-Magic Labeling of Trees. Discrete Mathematics, 331, 9-14.
https://doi.org/10.1016/j.disc.2014.04.021
[6] Alon, N., Kaplan, G., Lev, A., Roditty, Y. and Yuster, R. (2004) Dense Graphs Are Antimagic. Journal of Graph Theory, 47, 297-309.
https://doi.org/10.1002/jgt.20027
[7] Stewart, B.M. (1966) Magic Graphs. Canadian Journal of Mathematics, 18, 1031-1059.
https://doi.org/10.4153/cjm-1966-104-7
[8] Stewart, B.M. (1967) Supermagic Complete Graphs. Canadian Journal of Mathematics, 19, 427-438.
https://doi.org/10.4153/cjm-1967-035-9
[9] Ivančo, J. (2000) On Supermagic Regular Graphs. Mathematica Bohemica, 125, 99-114.
https://doi.org/10.21136/mb.2000.126259
[10] Ivančo, J. (2016) Supermagic Generalized Double Graphs. Discussiones Mathematicae Graph Theory, 36, 211-225.
https://doi.org/10.7151/dmgt.1849
[11] Froncek, D., Paananen, P. and Sorensen, L. (2024) Group-Supermagic Labeling of Cartesian Products of Two Even Cycles. Discrete Mathematics, 347, Article ID: 113741.
https://doi.org/10.1016/j.disc.2023.113741
[12] Zeng, X., Deng, G. and Luo, C. (2023) Characterize Group Distance Magic Labeling of Cartesian Product of Two Cycles. Discrete Mathematics, 346, Article ID: 113407.
https://doi.org/10.1016/j.disc.2023.113407
[13] Deng, G., Geng, J. and Zeng, X. (2024) Group Distance Magic Labeling of Tetravalent Circulant Graphs. Discrete Applied Mathematics, 342, 19-26.
https://doi.org/10.1016/j.dam.2023.08.025