加边对图的弱凸控制数和凸控制数的影响 The Influence of the Edge Adding on the Weakly Convex and Convex Domination Number of Graphs

doi:10.12677/AAM.2021.109334

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

期刊菜单

文章导航

AdvancesinAppliedMathematicsA^êÆ?Ð,2021,10(9),3200-3206

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

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

\>éãfà››êÚà››êK•

ÙÙÙøøøJJJùùù###MMM555JJJ

1∗

§§§>>>ùùù

1†

§§§uuu°°°

#õ“‰ŒÆêÆ‰ÆÆ§#õ¿°7à

#õŒÆêÆ†XÚ‰ÆÆ§#õ¿°7à

ÂvFÏµ2021c822F¶¹^FÏµ2021c912F¶uÙFÏµ2021c924F

Á‡

-G=(V,E)´˜‡ëÏã"^d

(u,v)L«ãG¥ü‡º:uÚvƒm•á(u,v)´•

Ý§˜‡•Ý•d

(u,v)(u,v)´¡Š˜‡(u,v)-ÿ/‚"ãG˜‡:f8X⊆V‰ãG

˜‡fà8§XJéX¥?¿ü‡º:a,b§3ãG¥Ñ•3˜‡(a,b)-ÿ/‚¦(a,b)-

ÿ/‚þ¤kº:ÑáuX"aq/§ãG˜‡:f8X⊆V‰ãG˜‡à8§XJ

éX¥?¿ü‡º:a,b,ãG¥z˜^(a,b)-ÿ/‚þ¤kº:ÑáuX"ãG˜‡:

f8D⊆V‰ãG˜‡››8§XJV-D¥z˜‡º:Ñ–k˜‡:3D¥.V

:f8X¡•Gfà››8§XJXQ´fà8q´››8"ãGfà››ê§´:ê•

fà››8¤•¹:ê§P•γ

wcon

(G)"ãGà››8Úà››êaq½Â§^γ

con

(G)5

L«ãGà››ê"©Ì‡ïÄ\>é˜ãafà››êÚà››êK•"

'…c

fà››ê§à››ê§››ê§§ä

TheInﬂuenceoftheEdgeAddingonthe

WeaklyConvexandConvexDomination

NumberofGraphs

∗1˜Šö"

†ÏÕŠö"

©ÙÚ^:ÙøJù#M5J,>ù,u°.\>éãfà››êÚà››êK•[J].A^êÆ?Ð,2021,

10(9):3200-3206.DOI:10.12677/aam.2021.109334

ÙøJù#M5J

BupatimanAilaiti

1∗

HongBian

1†

,HaizhengYu

SchoolofMathematicalSciences,XinjiangNormalUniversity,UrumqiXinjiang

CollegeofMathematicsandSystemSciences,XinjiangUniversity,UrumqiXinjiang

Received:Aug.22

,2021;accepted:Sep.12

,2021;published:Sep.24

,2021

Abstract

LetG= (V,E)beaconnectedgraph.Thedistanced

(u,v)betweentwovertices uand

vinaconnectedgraphGisthelengthoftheshortest(u,v)pathinG.A(u,v)path

oflengthd

(u,v)iscalleda(u,v)-geodesic.AsetX⊆ViscalledweaklyconvexinGif

foreverytwoverticesa,b∈X,thereexistsan(a,b)-geodesic,allofwhosevertices

belongtoX.AsetXisconvexinGifforalla,b∈Xallverticesfromevery(a,b)-

geodesicbelongtoX.AsubsetDofVisdominatinginGifeveryvertexofV−Dhas

atleastoneneighbourinD.AsetX⊆V iscalledweaklyconvexdominatingsetinGif

itisweakly convexanddominating,andcalledconvexdominatingsetinGifitisconvex

anddominating.TheweaklyconvexdominationnumberofagraphGistheminimum

cardinalityofaweaklyconvexdominatingsetofG,whiletheconvexdominationnumber

ofagraphGistheminimumcardinalityofaconvexdominatingsetofG,denotedby

wcon

(G)andγ

con

(G),respectively.Inthispaper,westudyedgeaddinganditseﬀect

ontheweaklyconvexdominationnumbersandconvexdominationnumbersforsome

graphs.

Keywords

WeaklyConvexDominationNumber,ConvexDominationNumber,

DominationNumber,Cycle,Tree

2021byauthor(s)andHansPublishersInc.

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

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

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

ÙøJù#M5J

1.0

©¥¤•ÄÑ´{ü,Ã•ëÏã.-G= (V,E)´˜‡{üã.3G¥,:vm •½

Â•N

(v) ={u|uv∈E(G)},4•N

[v] =N

(v)

{v},^E(v)L«†:vƒ'é>8Ü.

¡ãG¥:v´simplicial:,XJN

[v]´˜‡ã.ãG¥1Ý:¡•“f:,†1Ý:

ƒ:¡•| :.-V

ÚV

©OL«ãG¥“f:Ú| :8Ü,…n

= |V

|.ãG¥

:v¡•G•:,XJG−{v}´ØëÏ.-V

L«G¥•:8Ü.

ãG˜‡:f8D¡•ãG››8,XJ3V-D¥z‡:–†D¥˜‡:ƒ.

ãG¥ê•››8¤•¹:ê¡•ãG››ê,P•γ(G).Äuy¢)¹¥A^,

<‚ÅÚÚ\˜ØÓ/ª››8.››89ÙC/2•/A^uÀŒ¯K!iÿÏ&

½>åä!OŽÅä¯KÚè/ÿþ¥Ñy¢S¯K.ãG˜‡:f8D¡•ãG

ëÏ››8,XJD´››8¿…DÑfã´ëÏ.ãG¥ê•ëÏ››8¤

•¹:ê¡•ãGëÏ››ê,P•γ

(G).^d

(u,v)L«ãG¥ü‡º:uÚvƒm

•á(u,v)´•Ý,˜‡•Ý•d

(u,v)(u,v)´¡Š˜‡(u,v)-ÿ/‚.ãG˜‡:f

8X⊆V‰ãG˜‡fà8,XJéX¥?¿ü‡º:a,b,3ãG¥Ñ•3˜‡(a,b)-ÿ

/‚¦(a,b)-ÿ/‚þ¤kº:ÑáuX.aq/,ãG˜‡:f8X⊆V‰ãG˜‡

à8,XJéX¥?¿ü‡ º:a,b,ãG¥z˜^(a,b)-ÿ/‚þ¤kº:ÑáuX.ãG

:f8X¡•Gfà››8,XJXQ´fà8q´››8.ãG:f8X¡•Gà›

›8,XJXQ´à8q´››8.ãGfà››ê,´:ê•fà››8¤•¹:ê,P

•γ

wcon

(G).ãGà››êÚfà››êaq½Â,^γ

con

(G)5L«ãGà››ê.

à››êÚfà››ê•@´dTopp[1]JÑ,¦yÏL››8!:ë´•á,

U?ëÏ››3Ï&äO¥A^.32004c,Lema´nska[2]ïÄfà››Úà››

†Ù§››aëêƒm'X;AO/,ïÄà››êÚëÏ››êƒnKã.Ó32004

c,Raczek[3]y² (½˜‡ãfà››8Úà››8´˜‡NP-¯K.32010c,Raczek

ÚLema´nska[4]ïÄ‚¡fà››êÚà›ê,¿‰Ñ˜AÏ‚¡à››êÚfà››

ê(ƒŠ.Ó˜cLema´nska[5]‰Ñ˜‡ãfà››êNordhaus-Gaddum(J.32019

c,Rosicka[6]Šâ˜‡ãG= (V,E)ÚãGº:8V˜‡˜†π,½Â˜acÎãπG,Äk

éùacÎãà››8Úfà››85ŸŠ';Ùg,‰ÑüaAÏcÎã•x;•,

y²ãG†éAcÎãfà››êŒ±´?¿Œ;cÎãà››êÃ{^ ãG

à››ê5.½.Ó32019c,Lema´nska[7]<ÄkïÄfà››êÚëÏ››êƒm'

X,¿‰Ñ÷vγ

wcon

(G)=γ

(G)ãG•x;„y²3˜„œ/e,ãëÏ››ê†fà

››êŒ ±?¿Œ;d,„ïÄ>éfà››êK•.©z[8]¥ïÄ\>½>é

ã>››êK•.

©3®kïÄ(JÄ:þ,Ì‡ïÄ\>é˜ãafà››êÚà››êK•.

2.Ì‡(J

-G´˜‡º:ê•n{üã,g(G)“LãGŒ•.Lema´nska‰ÑãGfà››ê

TÐuº:êã¤÷v^‡.

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

ÙøJù#M5J

½n1[5]eãG´÷vδ(G) ≥2…g(G) ≥7n‡º:ëÏã,K

wcon

(G) = n.

e¡½n2‰Ñà››êTÐuº:êãG¤÷vaq^‡.

½n2 eãG´÷vδ(G) ≥2…g(G) ≥6n‡º:ëÏã,K

con

(G) = n.

y²-ãG´δ(G)≥2…g(G)≥6ëÏã.bγ

con

(G)<n.-D´G•à››

8.Ï•γ

con

(G)<n,KG¥•3˜‡º:x¦x6∈D.-N

(x)= {x

,...,x

},Ù¥p≥2(Ï

•δ(G)≥2).éu?¿x

,Ù¥1≤i,j≤p,Ñ‡÷vx

6∈E(G),ÄKx,x

EÑ

˜‡C

,´ù†g(G)≥6)gñ.5¿éu?¿x

,Ù¥x

6=x

…1≤i,j≤p,Ñ

)=2,¿…z˜éx

Úx

ƒm•á´Ñ•¹x.ÄK,e3x

Úx

ƒmé,˜^

Ø•¹x•á´x

,Kx

,x,x

¤˜‡o,ù†g(G) ≥6)gñ.

b•3ü‡:x

∈N

(x)¦x

∈D.duD´à8,…éu?¿x

Úx

ƒmz˜‡•á´Ñ‡•¹x,´ù†x6∈D)gñ.Ïd|N

(x) ∩D|≤1.Ï•‡›

›x,…|N

(x) ∩D|≤1,Ïd,Ø”˜„5,x

∈N

(x) ∩D.Ï•δ(G)≥2,Ïdùp–

•3˜‡áuN

(x):x

¦x

6∈D,Ø”x

.duδ(G)≥2…x

I‡››,Ïdù

p•3˜‡:y∈N

)¦y6=x…y∈D.Ï•g(G)≥6,ÏdkN

(y) ∩N

(x)=∅Ú

(y)∩N

) = ∅,Ù¥1 ≤i≤p.Ï•D´à8,Ïdd

(y,x

) <3¿…•3(x

,y)-ÿ/‚P

¦P

¤k:ÑáuD.Ïd–•3ü‡(x

,y)-´:P

ÚP

=(x

,x,x

,y)EÑ˜‡

u6.ù†g(G) ≥6)gñ.nþ,γ

con

(G) = n.

©z[7]‰ÑãGëÏ››8Úfà››8¥:¤÷v^‡.

Ún3[7]-G6=K

´˜‡ëÏã,Ù¥n≥3.XJD´G•ëÏ½fà ››8,K

z‡•:ÑáuD,…¤ksimplicial:ÑØáuD.

½n4[7]-G= (V(G),E(G))´g(G) ≥7ëÏã.K,

(1)γ

wcon

(G) = n−n

,Ù¥n´ãGº:ê;

(2)γ

wcon

(G) = γ

(G)…=éuz‡u∈V(G),u´“f:½•:.

-G“ LãGÖã.´•,éu?¿e∈E(G)Œ±¦ãG+e››ê•õ~1,Chen

<[9]y²\>¦ëÏ››ê•õ~2.ég,/¯KÒ´\>´Ø´• ¬¦ãfà›

›ê~ºe5•Ä\>éãC

ÚT

(f)à››êK•.

½n5 -C

´n≥3,Kéu?¿>e∈E(C

),Kk

wcon

)−4 ≤γ

wcon

+e) ≤γ

wcon

y²-e= uv.C

+eÑkú>uvü‡,Ø”^C

L«ùü‡,Ù¥n

≤n

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

ÙøJù#M5J

n.-S

´C

ê•fà››8,i∈{1,2}.Šân

Ún

ØÓŠ©±eo«œ /?1?

Øµ

œ/1n

≥7,n

≥7.Ï•n≥7ž,γ

wcon

)=n,Ïdγ

wcon

)=n

,γ

wcon

.qÏ•u,v∈S

∩S

,Kkγ

wcon

+e) = γ

wcon

) = n.

œ/2n

∈{4,5,6},n

≥7.Ï•n≥7ž,γ

wcon

)=n,Ïdγ

wcon

)=n

,Šâfà››8½Â,n

∈{4,5,6}ž,γ

wcon

)=n

−2.qÏ•u,v∈S

∩S

,Ï

dγ

wcon

+ e)=n−2.Ï•n

∈{4,5,6},n

≥7,…n

≤n

<n,Kkγ

wcon

)=n.¤

±γ

wcon

+e) = n−2 <γ

wcon

) = n.

œ/3 n

∈{4,5,6},n

∈{4,5,6}.Šâfà››8½Â,n

∈{4,5,6},n

∈{4,5,6}ž,

kγ

wcon

)=n

−2,γ

wcon

)=n

−2.qÏ•u,v∈S

∩S

,¤±γ

wcon

+e)=n−4.

d,Ï•n

∈{4,5,6},n

∈{4,5,6},…u,v∈C

∩C

,n∈{6,7,8,9,10},n=6ž,

wcon

) = n−2;7 ≤n≤10ž,γ

wcon

) = n.Ïd,γ

wcon

) >γ

wcon

+e).

œ /4n

=3,n

≥3.XJn

=3,Ï•u,v∈C

∩C

,@oC

´˜ ‡4.Šâfà›

›8½Â§γ

wcon

+ e)=n−3=1.¤±γ

wcon

+ e)=1<γ

wcon

)=n−2=2.X

∈{4,5,6},Šâfà››8½Â,γ

wcon

)=n−2.qÏ•u,v∈(S

∩V(C

)),…u

ÚvÑU››:V(C

) −{u,v},Ïdγ

wcon

+ e)=n−3.d,Ï•n

=3,n

∈{4,5,6},

…u,v∈C

∩C

, džn∈{5,6,7},¿…n= 7ž,γ

wcon

) = n;5 ≤n≤6ž,γ

wcon

) =

n−2.Ïd,γ

wcon

)>γ

wcon

+ e).XJn

≥7,@oγ

wcon

)=n

,…u,v∈S

Ï•u,v∈(S

∩V(C

)),…uÚvÑU››:V(C

)−{u,v},γ

wcon

+e)=n−1.¤

±γ

wcon

+e) = n−1 <γ

wcon

) = n.

nþ¤ã,γ

wcon

)−4 ≤γ

wcon

+e) ≤γ

wcon

Šâ½n2,Uì½n5©Û•{,Œ±‰Ñ\>éà››êaq(J.

½n6 -C

´n≥3,Kéu?¿>e∈E(C

),Kk

con

)−4 ≤γ

con

+e) ≤γ

con

½n7 -T

´º:ên≥3äã.Kéu?¿>e∈E(T

),Kk

wcon

)−2 ≤γ

wcon

+e) ≤γ

wcon

)+2.

y²ŠâÚn3,N´•D

=V−V

)´T

•fà››8,ùpV“LT

º

:8.e¡•ÄT

+efà››8,Ù¥e= uv∈E(T

).rT

+e¤•˜^C

5L«,

©±en«œ/?1?Ø:

œ/1bu,v∈D

,@ou,v6∈V

),d

(u)≥2,d

(v)≥2,¿…V

)=V

+e),

¤±D

= V−V

+e).

XJC

, Ù¥p≥7.KV−V

+e) ´T

+e•fà››8, ¿…Œ±γ

wcon

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

ÙøJù#M5J

e) = |D

|= γ

wcon

XJp= 4,5,6, …3C

þ•3ü‡ëY2Ý:x,y, KV−(V

+e)∪{x,y})´T

+e•

fà››8, ÏdŒ±γ

wcon

+e) = |D

|−2 = γ

wcon

)−2.eC

vkü‡ëY2Ý

:x,y, p= 5,6ž,D

´T

+e•fà››8, Ïdγ

wcon

+e) = |D

|= γ

wcon

p=4ž,eC

þk˜‡2Ý:,Kγ

wcon

+e)=|D

|−1= γ

wcon

)−1,eC

þvk2Ý

:,Kkγ

wcon

+e) = |D

|= γ

wcon

XJp=3,½ÂC

þ1n‡:•ω.Šâω∈V

+ e)½ω6∈V

+ e),KkD

½D

−ω´T

+e´•fà››8.

Ïd,3ù«œ¹ekγ

wcon

+e) ∈{|D

|,|D

|−1,|D

|−2}.

œ/2b|D

∩{u,v}|=1,·‚Ø”u∈D

,v∈V−D

,@od

(u) ≥2…d

(v) =1.

5¿v∈V

)−V

+e),ÏdkD

= V−(V

+e)∪{v})´T

•fà››8.

XJC

, Ù¥p≥7.KV−V

+e)´T

+e•fà››8, ¿…Œ±γ

wcon

e) = |D

|+1 = γ

wcon

)+1.

XJp=4,5,6,…3C

þ•3ü‡ëY2Ý:x,y,KV−(V

+e)∪{x,y})´T

•fà››8,ÏdŒ±γ

wcon

+e)=|D

|−1=γ

wcon

)−1.eC

ü‡ëY2Ý:,p=5,6 ž,V−V

+ e) ´T

+ e•fà››8,ÏdŒ±

γ

wcon

+e) = |D

|+1 = γ

wcon

)+1.p= 4ž,eC

þk˜‡2Ý:,KD

´T

+e

•fà››8,γ

wcon

+e) = |D

|= γ

wcon

XJp= 3, -C

þ1n‡:•ω.Šâω∈V

+e)½ω6∈V

+e),kD

½D

−ω

´T

+e´•fà››8.

Ïd,3ù«œ¹ekγ

wcon

+e) ∈{|D

|−1,|D

|,|D

|+1}.

œ/3-u,v∈V−D

,Kd

(u)=1=d

(v).5¿u,v∈V

) −V

+ e).Ïd

= V−(V

+e)∪{u,v})´T

•fà››8.

XJC

, Ù¥p≥7.KV−V

+e)´T

+e•fà››8, ¿…Œ±γ

wcon

e) = |D

|+2 = γ

wcon

)+2.

XJp=4,5,6.Ï•u,v∈V−D

,¤±3C

þ•3ü‡ëY2Ý:u,v,ÏdŒV−

+e)∪{u,v})´T

+e•fà››8,¿…γ

wcon

+e) = |D

|= γ

wcon

XJp=3,@oD

´T

+ e•fà››ê,¿…Œ±γ

wcon

+ e)=|D

wcon

).Ïd,3ù«œ¹e,kγ

wcon

+e) ∈{|D

|,|D

|+2}.

nþŒ•,éuT

kγ

wcon

+e) ∈{|D

|−2,|D

|−1,|D

|,|D

|+1,|D

|+2}.

à››êaq(J.

½n8 -T

´º:ên≥3äã.Kéu?¿>e∈E(T

),Kk

con

)−2 ≤γ

con

+e) ≤γ

con

)+2.

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

ÙøJù#M5J

Ä7‘8

I[g,‰ÆÄ7‘8(11761070,61662079)¶2021c#õ‘Æg£«g,Ä7éÜ‘

8(2021D01C078)¶2020c#õ“‰ŒÆ˜6;’!˜6‘§‘8]Ï"

ë•©z

[1]Topp,J.(2002)PersonalCommunication.Gda´nskUniversityofTechnology,Gda´nsk.

[2]Lema´nska,M. (2004)Weakly Convex and ConvexDominationNumbers.OpusculaMathemat-

ica,24,181-188.

[3]Raczek,J.(2004)NP-CompletenessofWeaklyConvexandConvexDominatingSetDecision

Problems.OpusculaMathematica,24,189-196.

[4]Raczek,J.andLema´nska,M.(2010)ANoteontheWeaklyConvexandConvexDomination

NumbersofaTorus.DiscreteAppliedMathematics,158,1708-1713.

https://doi.org/10.1016/j.dam.2010.06.001

[5]Lema´nska,M.(2010)Nordhaus-GaddumResultsforWeaklyConvexDominationNumberof

aGraph.DiscussionesMathematicaeGraphTheory,30,257-263.

https://doi.org/10.7151/dmgt.1491

[6]Rosicka,M.(2019)ConvexandWeaklyConvexDominationinPrismGraphs.Discussiones

MathematicaeGraphTheory,39,741-755.https://doi.org/10.7151/dmgt.2207

[7]Dettlaﬀ,M.,Lema´nska,M.andOsula,D.(2019)OntheConnectedandWeaklyConvex

DominationNumbers.arXiv:1902.07505v1

[8]Cš,ÏI.†>››ƒ'üaã[J].#õŒÆÆ(g,‰Æ‡),2019,36(1):11-16+38.

[9]Chen,X.J.,Sun,L.andMa,D.X.(2004)ConnectedDominationCriticalGraphs.Applied

MathematicsLetters,158,503-507.https://doi.org/10.1016/S0893-9659(04)90118-8

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