路和森林的符号乘积图的边染色 Edge Coloring of the Signed Product Graphs of Paths and Forests

doi:10.12677/AAM.2022.113104

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

期刊菜单

文章导航

AdvancesinAppliedMathematicsA^êÆ?Ð,2022,11(3),973-979

PublishedOnlineMarch2022inHans.http://www.hanspub.org/journal/aam

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

´ÚÜÎÒ¦Èã>/Ú

äää···

úô“‰ŒÆ§êÆ†OŽÅ‰ÆÆ§úô7u

ÂvFÏµ2022c29F¶¹^FÏµ2022c34F¶uÙFÏµ2022c311F

Á‡

2019c§Behr|^ÎÒã>/ÚVgy²éu?¿ÎÒã(G,σ)Ñk∆(G,σ)≤

(G,σ)≤∆(G,σ)+1§Ù¥χ

(G,σ)´(G,σ)>/Úê§∆(G,σ)´(G,σ)•ŒÝ"©

·‚y²3´Ú ÜÎÒ¦Èã(P

,σ)¥§Ù¥P

ÚT

©O´kn‡º:´Úkm‡

º:Ü§n>2…∆(T

) >1ž§Kχ

,σ) = ∆(P

,σ)"

'…c

ÎÒã§¦Èã§´§Ü§>/Ú

EdgeColoringoftheSignedProduct

GraphsofPathsandForests

YajingWang

CollegeofMathematicsandComputerScienceofZhejiangNormalUniversity,JinhuaZhejiang

Received:Feb.9

,2022;accepted:Mar.4

,2022;published:Mar.11

,2022

Abstract

2019,Behrusedtheconceptofedgecoloringofsignedgraphstoprovethatforany

©ÙÚ^:ä·.´ÚÜÎÒ¦Èã>/Ú[J].A^êÆ?Ð,2022,11(3):973-979.

DOI:10.12677/aam.2022.113104

ä·

signedgraphs(G,σ) thereis∆(G,σ) ≤χ

(G,σ) ≤∆(G,σ)+1,whereχ

(G,σ) isthenumber

ofedgecoloringof(G,σ),∆(G,σ)isthemaximumdegreeof(G,σ).Inthispaper,we

provethatinthesignedproductgraphsofpathsandforests(P

,σ),P

andT

arerespectivelypathswiththenumberofnverticesandforestswiththenumberof

mvertices.Whenn>2and∆(T

) >1,thenχ

,σ) = ∆(P

,σ).

Keywords

SignedGraphs,ProductGraphs,Paths,Forests,Edge-Coloring

2022byauthor(s)andHansPublishersInc.

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

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

1.Úó

Harary 3þ-V50c“JÑÎÒãVg[1]"ÎÒã(G,σ) ´‰Ä:ãG=(V(G),E(G))

>8\˜‡ÎÒNσ:E(G)→{+1,−1}§¦Gz˜^>eÑk˜‡ÎÒσ(e)"σ(e)=

+1ž§>e•>¶ σ(e)= −1ž§>e•K>"(G,σ) ˜‡incidence´:->kSé(v,e)§v

´e˜‡à:"‰½˜‡ÎÒã(G,σ)§I(G)L«(G,σ) ¥¤kincidence 8Ü"V(G) L«

(G,σ)º:8¶E(G,σ) L«(G,σ)>8"∆(G)L«G•ŒÝ"©¤?ØÎÒãþ´

Ã‚§Ã->{ük•ÎÒã"

©™`²PÒÚâŠþë©z[2]"

½Â1{üÎÒã(G,σ) >/Ú´•é(G,σ)incidence XÚ§¦Ó˜‡º:'é

incidenceþkØÓôÚ"ÎÒã(G,σ)>Úêχ

(G,σ)´•¦ÎÒã(G,σ)•~>/Ú

•ôÚê"

Vizing31964c§‰Ñ{üã>/Úêþe."

½n1(Vizing,1964,[3])˜‡ãG>/Úêχ

(G)÷v∆(G) ≤χ

(G) ≤∆(G)+1"

2019c§Behr ‰Ñ{üÎÒã>/ÚVg[4]¿y²þã(Ø3{üÎÒã(G,σ)¥

Ó÷v∆(G,σ) ≤χ

(G,σ) ≤∆(G,σ)+1"

½Â2ãGÚH¦ÈãG2H´•äkº:8V(G2H)Ú>8E(G2H)ã§Ù¥V(G2H) =

V(G)×V(H)={(u,v)|u∈V(G),v∈V(H)},E(G2H)= {(u,v)(u

)|u=u

,vv

∈E(H)½v=

,uu

∈E(G)}"

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

ä·

½Â3ÎÒ¦Èã(G2H,σ)´‰§>8\˜‡ÎÒNσ:E(G2H)→{+1,−1}§¦

G2Hz˜^>eÑk˜‡ÎÒσ(e)"

½Â4éuÎÒã(G,σ)§XJχ

(G,σ)=∆(G,σ)§K¡ÎÒã(G,σ)•1˜aÎÒã"

P(G,σ) ∈C

½Â5éuÎÒã(G,σ)§XJχ

(G,σ)=∆(G,σ) +1§K¡ÎÒã(G,σ)•1aÎÒ

ã"P(G,σ) ∈C

3©z[5]§[6]§[7]¥§þïÄÎÒã/Ú"3©¥§·‚òÎÒã˜‡n- >/Ú

½Â•:

½Â6(G,σ)´˜‡ÎÒã§n´˜‡ê§en=2k§K(G,σ)˜‡n->/

ÚÒ´˜‡Nγ:E(G)→{±k,±(k−1),···,±1}¶en=2k+ 1§Kγ:E(G)→{±k,±(k−

1),···,±1,0}§¦é?¿>e=vw∈E(G)Ñkγ(v,e)=σ(e)γ(w,e)"?¿ƒü^

= vwÚe

= vu§¦γ(v,e

) 6= γ(v,e

)§K¡γ´(G,σ)þ~n->/Ú"

Behr ÏLé½n1?1í2§?¿{üÎÒã(G,σ)>/Úêχ

(G,σ)÷v∆(G,σ)≤

(G,σ)≤∆(G,σ)+ 1"3©¥§·‚y²´ÚÜÎÒ¦Èã(P

,σ)>/Ú

êχ

,σ)÷vn>2…∆(T

)>1ž§Kχ

,σ)=∆(P

,σ)"·‚©¤2 ‡½

n5y²ù‡(Ø"·‚Äky²3´ÚÜÎÒ¦Èã(P

,σ)¥§1≤∆(T

)≤2ž§

½n2¤á¶2y²n>2…∆(T

) >2ž§½n3¤á"

½n23ÎÒ¦Èã(P

,σ)¥§Ù¥n§m©O´P

§T

þ:ê"

(i)n= 2§∆(T

) =1…ÎÒã(P

,σ)´˜‡š²ïž§ KÎÒã(P

,σ)•1

aÎÒã"

(ii)n= 2§∆(T

) =1…ÎÒã(P

,σ)´˜‡²ïž§KÎÒã(P

,σ)•1˜a

ÎÒã"

(iii)n>2…∆(T

) = 2ž§KÎÒã(P

,σ)•1˜aÎÒã"

½n33ÎÒ¦Èã(P

,σ)¥§Ù¥n§m©O´P

§T

þ:ê"

n>2…∆(T

) >2ž§KÎÒã(P

,σ)•1˜aÎÒã"

2.½n2y²

y²3ÎÒ¦Èã(P

,σ)¥§1≤∆(T

)≤2ž§ÎÒã(P

,σ)=(P

,σ)"

(•§(P

,σ)´‘kÎÒ•‚ã"

Äky²(i)"n=2§∆(T

)=1…ÎÒã(P

,σ)•k˜‡š²ïž·‚ù‡š

²ï•C=v

"v

´˜^>§Ï•C´š²ï§¤±P=v

þ˜½k

Ûê^K>"P–Œ±^2«ôÚ/Ð§^±a/Ð"bl(v

)m©^aÚ−a?1/Ú§

K(v

)˜½/−a"¤±Cþ•˜^>v

˜½‡^1n«ôÚâU/Ð§•b"¤

±χ

,σ) = 3"džÎÒã∆(P

,σ) = 2§¤±džÎÒã(P

,σ)´1aÎÒ

ã"

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

ä·

Ùgy²(ii)"n=2§∆(T

)=1…ÎÒã(P

,σ)•k˜‡²ïž·‚ù‡²ï

•C

"v

´˜^>§Ï•C

´²ï§¤±P

þ˜½kóê

^K>"P

–Œ±^2«ôÚ/Ð§^±a/Ð"bl(v

)m©^aÚ−a?1/Ú§

K(v

)˜½/a"¤±C

þ•˜^>v

Œ±^−a/Ð"¤ ±χ

,σ) = 2"dž

ÎÒã∆(P

,σ) = 2§¤±ÎÒã(P

,σ)´1˜aÎÒã"

•·‚y²(iii)"n>2…∆(T

) = 2ž§∆(P

) = 4"

·‚‰Ñù‡ÎÒã(P

,σ)˜‡~4->/Úγ¿…y²ù‡.´;"

Äk·‚‰Ñù‡ÎÒã(P

,σ)˜‡~4->/Úγ"

éu?¿i§j§i∈[m]§j∈[n]§iL«(P

,σ)1i1§jL«(P

,σ)1j§

i,j

L«(P

,σ)þ1i1§1j:"











γ(u

i,1

,e(u

i,1

i,2

)) = 1,

γ(u

i,j

,e(u

i,j

i,j−1

)) = γ(u

i,j−1

,e(u

i,j−1

i,j

))σ(e(u

i,j−1

i,j

)),

γ(u

i,j

,e(u

i,j

i,j+1

)) = −γ(u

i,j

,e(u

i,j

i,j−1

)),

(1)

-Eþã/ÚL§,†31m1"éu?¿1i1´P

5`§§•˜^>e(u

i,n−1

i,n

Ú•:











γ(u

i,n−1

,e(u

i,n−1

i,n−2

)) = γ(u

i,n−2

,e(u

i,n−1

i,n−2

))σ(e(u

i,n−2

i,n−1

)),

γ(u

i,n−1

,e(u

i,n−1

i,n

)) = −γ(u

i,n−1

,e(u

i,n−2

i,n−1

)),

γ(u

i,n

,e(u

i,n

i,n−1

)) = γ(u

i,n−1

,e(u

i,n−1

i,n

))σ(e(u

i,n−1

i,n

)),

(2)

di?¿5•(P

,σ)z˜1incidence ÑŒ±^?¿2‡ƒ‡ôÚ±a/Ð"þã/Ú

·‚´a= 1"

;X-











γ(u

1,j

,e(u

1,j

2,j

)) = 2,

γ(u

i,j

,e(u

i,j

i−1,j

)) = γ(u

i−1,j

,e(u

i−1,j

i,j

))σ(e(u

i−1,j

i,j

)),

γ(u

i,j

,e(u

i,j

i+1,j

)) = −γ(u

i,j

,e(u

i,j

i−1,j

)),

(3)

-Eþã/ÚL§,†31n"éu?¿1j´P

5`§§•˜^>e(u

m−1,j

m,j

)

/Ú•:











γ(u

m−1,j

,e(u

m−1,j

m−2,j

)) = γ(u

m−2,j

,e(u

m−1,j

m−2,j

))σ(e(u

m−1,j

m−2,j

)),

γ(u

m−1,j

,e(u

m−1,j

m,j

)) = −γ(u

m−1,j

,e(u

m−2,j

m−1,j

)),

γ(u

m,j

,e(u

m,j

m−1,j

)) = γ(u

m−1,j

,e(u

m−1,j

m,j

))σ(e(u

m−1,j

m,j

)),

(4)

dj?¿5•(P

,σ)z˜incidence ÑŒ±^ØÓu±a?¿2 ‡ƒ‡ôÚ±b/

Ð"þã/Ú·‚´b= 2"

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

ä·

qÏ•P

?¿2 1Ú?¿2 ÑØ¬u˜:"¤±(P

,σ)Œ±^4 ‡ôÚ±a

Ú±b/Ð"=γ´ÎÒã(P

,σ)˜‡~4->/Ú§χ

,σ) = 4"

dBehr {üÎÒã>/Ú(Ø§·‚•éu?¿{üÎÒã(G,σ)§χ

(G,σ)

e.´∆(G,σ)"·‚3þ¡y²¥®²‰Ñ1«/Ú•{χ

,σ)=4§¤

±χ

,σ)=∆(P

,σ)§=(P

,σ)´1˜a"n>2…∆(T

)=2ž§T

§¤±ÎÒã(P

,σ)•1˜aÎÒã"

3.½n3y²

y²éuÎÒ¦Èã(P

,σ)5`§n>2…∆(T

)>2ž§·‚‰Ñù‡ÎÒã˜

‡~∆(P

,σ)->/Úγ¿…y²ù‡.´;"

(•§n>2…∆(T

)>2ž§∆(P

)=∆(T

)+2"ë•½n2/Ú

•{§aq/"·‚k‰(P

,σ)z˜1?1/Ú"(P

,σ)z˜1þ´:Ø´P

(i∈[m])§Ïdz‡P

þŒ±^2 «ôÚ±a/Ð"qÏ•(P

,σ)z˜þ´:ØäT

(j∈[n])"

Ï•Šâ©z[2]¥·K2.2:XJÎÒã´˜‡•ŒÝ•∆äT§Kχ

(T,σ) = ∆"

Œ•éu?¿˜†äT

þ÷vχ

,σ)=∆(T

)"qÏ•T

´üü:Øƒ§¤±z

‡T

þŒ±^ØÓu±a∆(T

) «ôÚ/Ð"=χ

,σ) =∆(T

)+2 =∆(P

)"¤

±§ÎÒã(P

,σ)•1˜aÎÒã"

ÏL½n2§½n3y²§·‚Œ±µ´ÚÜÎÒ¦Èã(P

,σ)>/Ú

êχ

,σ)÷vn>2…∆(T

) >1ž§Kχ

,σ) = ∆(P

,σ)"

3ÎÒã(P

,σ)¥§n>2§m=2½n=2§m>2ž§KÎÒã(P

,σ)=

,σ)½(P

,σ)=(P

,σ)"3(P

,σ)¥§n>2§∆(T

)=1ž§KÎÒ

ã(P

,σ) = (P

,σ)"

¯¢þn=mž§(P

,σ)Ú(P

,σ)´Ó˜‡{üÎÒã"éu(P

,σ)5`§

n>2ž§Kχ

,σ)ŒU´∆(P

,σ)+1§„ã1§•ŒU´∆(P

,σ)§„ã2"ã

1§ã2´þ´(P

,σ)fã"

Figure1.χ

,σ) = ∆(P

,σ)+1

ã1.χ

,σ) = ∆(P

,σ)+1

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

ä·

Figure2.χ

,σ) = ∆(P

,σ)

ã2.χ

,σ) = ∆(P

,σ)

3ã1¥§u

2,2

'é2^K>e(u

2,1

2,2

)§e(u

2,3

2,2

)§1^>e(u

1,2

2,2

)§¿…2‡ú>

´>e(u

1,2

2,2

)§džu

2,2

'éù3^>–‡^3«ôÚ/Ð"

3ã1¥§-











γ(u

1,2

,e(u

1,2

2,2

)) = 2,

γ(u

2,2

,e(u

1,2

2,2

)) = 2,

γ(u

2,2

,e(u

2,2

2,1

)) = −1,

γ(u

2,1

,e(u

2,2

2,1

)) = 1,

γ(u

2,2

,e(u

2,2

2,3

)) = 1,

γ(u

2,3

,e(u

2,2

2,3

)) = −1.

(5)

‡Žã1¤^ôÚ•§•U-











γ(u

2,1

,e(u

2,1

1,1

)) = −1,

γ(u

1,1

,e(u

2,1

1,1

)) = 1,

γ(u

2,3

,e(u

2,3

1,3

)) = 1,

γ(u

1,3

,e(u

2,3

1,3

)) = −1,

γ(u

1,3

,e(u

1,3

1,2

)) = 1,

γ(u

1,2

,e(u

1,3

1,2

)) = −1.

(6)

dž§γ(u

1,1

,e(u

1,1

1,2

))§γ(u

1,2

,e(u

1,1

1,2

))•U^1o«ôÚâU/Ð"

¤±§ã1¥(P

,σ)>Úêχ

,σ)´∆(P

,σ)+1"

Ïd§ éu(P

,σ)=∆(P

,σ)+ 1´1˜a

,σ)=∆(P

,σ)´1a§ù„I‡·‚?˜

ÚïÄ"

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

ä·

ë•©z

[1]Harary,F.(1953)OntheNotionofBalanceofaSignedGraph.MichiganMathematicalJournal,

2,143-146.https://doi.org/10.1307/mmj/1028989917

[2]Zhang, L., Lu, Y., Lou, R., Ye, D. and Zhang, S.(2020) EdgeColoring SignedGraphs. Discrete

AppliedMathematics,282,234-242.https://doi.org/10.1016/j.dam.2019.12.004

[3]Vizing,V.(1964)OnanEstimateoftheChromaticClassofap-Graph.DiscretAnaliz,3,

23-30.

[4]Behr,R.(2020) EdgeColoringSigned Graphs.DiscreteMathematics, 343,ArticleID:111654.

https://doi.org/10.1016/j.disc.2019.111654

[5]Cartwright,D.andHarary,F.(1968)OntheColoringofSignedGraphs.ElementederMath-

ematik,23,85-89.

[6]Zaslavsky,T.(1991)OrientationofSignedGraphs.EuropeanJournalofCombinatorics,12,

361-375.https://doi.org/10.1016/S0195-6698(13)80118-7

[7]Zaslavsky,T.(1982)SignedGraphs.DiscreteAppliedMathematics,4,47-74.

https://doi.org/10.1016/0166-218X(82)90033-6

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