一类代数图的Cayley性 Cayley Properties of a Class of Algebraic Graphs

doi:10.12677/AAM.2021.1011382

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

AdvancesinAppliedMathematicsA^êÆ?Ð,2021,10(11),3618-3622

PublishedOnlineNovemb er2021inHans.http://www.hanspub.org/journal/aam

https://doi.org/10.12677/aam.2021.1011382

˜a“êãCayley5

LLL§§§ÙÙÙ‡‡‡

∗

B²ŒÆêÆ†ÚOÆ§B²B

ÂvFÏµ2021c102F¶¹^FÏµ2021c1023F¶uÙFÏµ2021c114F

Á‡

R´˜‡k•‚"©Äu“êãØÄ¯¢§ïÄ˜ a-‡ãxCayley5Ÿ§E 

“êãBΓ

(R;f

,...,f

)˜‡Ã•fx§Ù¥z‡ãÑ´Cayleyã§3dÄ:þ?˜Ú•Äù

a“êã•Œ"

'…c

Cayleyã§Hamiltonã§2Â¡N+

CayleyPropertiesofaClassof

AlgebraicGraphs

FuyuanYang,ChaoZhang

∗

SchoolofMathematicsandStatistics,GuizhouUniversity,GuiyangGuizhou

Received:Oct.2

,2021;accepted:Oct.23

,2021;published:Nov.4

,2021

Abstract

LetRbeaﬁnitering.Basedonthebasicfactsofalgebraicgraphtheory,thispaper

studiestheCayleypropertiesofanimportantfamilyofgraphs,andconstructsan

∗ÏÕŠöEmail:zhangc@amss.ac.cn

©ÙÚ^:L,Ù‡.˜a“êãCayley5[J].A^êÆ?Ð,2021,10(11):3618-3622.

DOI:10.12677/aam.2021.1011382

L§Ù‡

inﬁnitesubfamilyofalgebraicgraphsBΓ

(R;f

,...,f

),inwhicheachgraphisCayley

graph.Onthisbasis,themaximalcycleofthiskindofalgebraicgraphisfurther

considered.

Keywords

CayleyGraph,HamiltonianGraph,GeneralizedDihedralGroup

2021byauthor(s)andHansPublishersInc.

This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).

http://creativecommons.org/licenses/by/4.0/

1.Úó

©¥§¤kãÑ´{üÃloopÃ•ã"•§|½Âã•@´dLazebnikJÑ˜a

ã§•Ð^5)û4ŠãØ¥¯K[1]§LazebnikÚWoldarïáùaã˜-‡5Ÿ[2]§

•)K5ÚVK5"2002c§©Ù[3]?Ø˜XŒé¡•§ |½Âã¿½§‚´

ÄëÏ§ù˜XãØ´Cayleyã¿…¼êØ´é¡"d§ãBΓ

(R;f

,...,f

)•õ5Ÿ

Ú¯KŒ±3Lazebnik©Ù[4]¥é"3A^•¡§UstimenkoÚ¦ÜŠöò•§|½Âã

A^u?ènØÚ—èÆ[5]"

CayleyãCay(G,S)´±+G¥ƒ•º:§±f8S½Â>˜aã§§†Hamiltonã

2•ïÄ[6]"Lazebnik3©Ù[2]5.2!¥‰Ñã˜úm¯K§©Ì‡ïÄÙ¥

˜‡-‡úm¯K§=•§|½Âã=¼ê(½ãBΓ

(R;f

,...,f

)´Cayleyã½ö

´Hamiltonã§ù´˜‡k…k¿Â¯K§©E˜X•§|½ÂCayleyã§

¿…ãBΓ

)•Œ"

2.ý•£

Γ´˜‡ã§·‚o´^V(Γ)L«º:8§^E(Γ)L«>8§x∼yL«º:xÚyƒ"

½Â1[2]R´k•‚§¼êf

2i−2

→R´?¿‰½¼ê"·‚½Â©ãBΓ

BΓ

(R;f

,...,f

)"§ü‡Ü8´©OuR

P

ÚL

§P

ÚL

¥ƒ©O¡•:(p)=

,...,p

)Ú‚[l] = [l

,...,l

]"·‚½Âº:(p)Ú[l]…=e¡n−1‡^‡¤áµ

= f

......

= f

,...,p

n−1

DOI:10.12677/aam.2021.10113823619A^êÆ?Ð

L§Ù‡

w,§XJR´r§@oãBΓ

(R;f

,...,f

)º:ê´2r

…´r−K§Ï•éu?Û

º:a∈V(BΓ

)Úx∈R§•3•˜º:b∈V(BΓ

)§¦b†aƒ§¿…b1˜‡‹I´x"

½Â2[7]G´+§S´Gf8"k•ãΓ=Cay(G,S)´Cayleyã§XJCay(G,S)º

:8•G…ü‡º:x,y∈Gƒ§…=yx

−1

∈S"XJS

−1

=S§KT'X´é¡§

džCayleyãCay(G,S)d˜‡Ã•ã"

½Â3Γ´˜‡ã§H´gÓ+Aut(Γ)˜‡f+"XJH3V(Γ)´D4…éu ?

¿v∈V(Γ)Úσ∈H§¦σ(v) = v§@oσ´ðgÓ§K¡H3V(Γ)þ´K"

Ún1[7]ãΓ´+GCayleyã…=Aut(Γ)•¹†GÓf+3V(Γ)þ´K"

½Â4+G´2Â¡N+§XJ§k˜‡•ê•2†f+AÚ˜‡•2ƒπ∈

G\A§é?¿g∈A§¦πgπ= g

−1

"3ù«œ¹e§·‚PŠG= hπ,Ai"

½Â5[8]•¹ãΓz‡º:´»¡•ΓHamilton´»¶aq/§ΓHamilton´•

¹Γz‡º:"eãΓ•¹Hamilton§K¡ãΓ´Hamiltonã½ö´hamiltonian"

Ún2[6]G´k•+§S´Gf8"d÷v§

(1)S´G)¤8§

(2)A´G5p−f+é,ƒêp§…

(3)st

−1

∈Aé¤ks,t∈S§

@oCay(G,S)k˜‡Hamliton"

3.Ì‡(J

e¡E˜X•§|½ÂãBΓ

(R;f

,...,f

)Ñ´Cayleyã"

½n1e{f

|i= 2,...,n}÷v±eœ¹§KãBΓ

(R;f

,...,f

)´Cayleyã"

(1)f

i−1

s=1

)

+c§Ù¥a

,c∈R´~ê…b

´ê¶

(2)n= 2…f

= cp

é~êc∈R§Ù¥R´†‚…2

−1

∈R¶

(3)f

n−1

s=1

n−1

s=1

)

n−1

s=1

)

+cÚf

i−1

s=1

i,s

)

i,s

éi=2,···,n−1§Ù¥R´Ap…2

−1

∈R†‚§mp´Ûê§a

i,s

,c,d

∈R§

i,s

´ê¶

(4)f

= p

m−1

§f

= p

é2 ≤i<mÚf

= p

m−1

ém<i≤n§Ù¥R´†

‚…2

−1

∈R"

y²µéu1 ≤k<i≤nÚx∈R§·‚e¡Nφ,σ

i,x

: R

→R

φ: (p

,...,p

) 7→[p

,...,p

],[ l

,...,l

] 7→(l

,...,l

k,x

: (p) 7→(p

,...,p

+x,p

k+1

k+1,k

,...,p

i,k

,...,p

n,k

)

[ l] 7→[ l

,...,l

−x,l

k+1

k+1,k

,...,l

i,k

,...,l

n,k

DOI:10.12677/aam.2021.10113823620A^êÆ?Ð

L§Ù‡

éu(1)§½Âb

i,k

= 0§y

i,k

= 0"

éu(2)§-b

2,1

= c(−p

x−

)§y

2,1

= c(l

x−

éu(3)§b

i,k

= y

i,k

= 0éuk<i<n§…

n,k

n−1

s=1

(−p

x−

n−1

s=1

(−(p

−

2mp

n,k

n−1

s=1

x−

n−1

s=1

((l

−

2mp

éu(4)§-b

i,k

= −p

x−

i,k

= l

x−

é1 ≤k<m<i≤n§b

i,k

= y

i,k

= 0éuÙ¦

œ¹"éu?¿x,y∈R·‚ØJyNφ,σ

i,x

´ãBΓ

gÓ…e¡†5¤áµ

k,x

j,y

= σ

j,y

k,x

,φσ

k,x

φ= σ

k,−x

= σ

−1

k,x

A= hσ

k,x

|k= 1,...,n;x∈RiÚG= hφ,Ai"ØJyA´˜‡†+"

d§|φ|=2§é1≤k≤n§8Ü{σ

k,x

|x∈R}kr‡ƒ"duσ

k,x

k,y

=σ

k,x+y

§K

†+Akr

‡gÓ§ÏdG=hφ,Ai≤Aut(BΓ

)´2Â¡N+…k2r

‡ƒ"·‚Œ±

yG3V(BΓ

)þ´K"dÚn1§Œ•BΓ

´2Â¡N+þCayleyã"

y3©•ÄãBΓ

)ÚãBΓ

)´

ëÏ§e¡íØŒ•BΓ

)k˜‡Hamilton"

íØ1F

´˜‡k••§Ù¥q =p

…p´Ûƒê§KãBΓ

)´Hamiltonã§

ãBΓ

)k˜‡•Ý•2q"

y²µd½n1Œ•ãBΓ

)ÚBΓ

)´2Â¡N+þCayleyãCay(G,S)"

éuãBΓ

)§ÄkãBΓ

)´ëÏ§dÚn1¥Ïé)¤8hSi§Œ•φσ

1,x

∈

hSidu(0) ∼[x,0] é?¿x∈F

"-x= 0§u´φ∈hSi§σ

2,x

,σ

2,−x

∈hSi§·‚kσ

2,−

∈hSi

Úσ

1,x

∈hSi§x

= zk)(x,y)é?¿z∈F

§u´σ

2,z

∈hSi§Œ•ãBΓ(F

)ëÏ"Œ

±yCay(G,S)÷vÚn2^‡§u´ãBΓ

)k˜‡Hamliton"éuãBΓ

)ÓCay(G

)§du(0)∼[x,x]§Ùë8S

)¤8ÜhS

i•hφσ

1,x

2,x

i§d½n1¥†

5Œ•hφσ

1,x

2,x

i=hφ,σ

1,x

2,x

i´2q§ãBΓ

)k˜‡•Ý•2q"

Ä7‘8

ë•©z

[1]Lazebnik,F. andUstimenko,V.A.(1993)New Examplesof Graphswithout SmallCyclesand

ofLargeSize.EuropeanJournalofCombinatorics,14,445-460.

DOI:10.12677/aam.2021.10113823621A^êÆ?Ð

L§Ù‡

https://doi.org/10.1006/eujc.1993.1048

[2]Lazebnik,F.andWoldar,A.J.(2001)GeneralPropertiesofSomeFamiliesofGraphsDeﬁned

bySystemsofEquations.JournalofGraphTheory,38,65-86.

https://doi.org/10.1002/jgt.1024

[3]Lazebnik,F.andViglione,R.(2002)AnInﬁniteSeriesofRegularEdge)ButNotVertex-

TransitiveGraphs.JournalofGraphTheory,41,249-258.https://doi.org/10.1002/jgt.10064

[4]Lazebnik,F.,Sun,S.andWang,Y.(2017)SomeFamiliesofGraphs,HypergraphsandDi-

graphsDeﬁnedbySystemsofEquations:ASurvey.LectureNotesofSeminarioInterdisci-

plinarediMatematica,14,105-142.

[5]Klisowski,M.andUstimenko,V.(2012)OntheComparisonofCryptographicalProperties

ofTwoDiﬀerentFamiliesofGraphswithLargeCycleIndicator.MathematicsinComputer

Science,6,181-198.

[6]Morris,D.W.(2012)2-GeneratedCayleyDigraphsonNilpotentGroupsHaveHamiltonian

Paths.ContributionstoDiscreteMathematics,7,41-47.

https://doi.org/10.11575/cdm.v7i1.62051

[7]Biggs,N.(1992)AlgebraicGraphTheory.CambridgeUniversityPress,NewYork.

[8]Bondy,J.A.andMurty,U.S.R.(1976)GraphTheorywithApplications.Macmillan,London.

DOI:10.12677/aam.2021.10113823622A^êÆ?Ð