Fed igo, Alexand a
A icle
Th eshold p o ocol game on g aphs wi h magic squa e-
gene aliza ion labelings
Games
P o ided in Coope a ion wi h:
MDPI – Mul idisciplina y Digi al Publishing Ins i u e, Basel
Sugges ed Ci a ion: Fed igo, Alexand a (2024) : Th eshold p o ocol game on g aphs wi h magic
squa e-gene aliza ion labelings, Games, ISSN 2073-4336, MDPI, Basel, Vol. 15, Iss. 6, pp. 1-27,
h ps://doi.o g/10.3390/g15060042
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/330111
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h ps://c ea i ecommons.o g/licenses/by/4.0/
Ci a ion: Fed igo, A. Th eshold
P o ocol Game on G aphs wi h Magic
Squa e-Gene aliza ion Labelings.
Games 2024,15, 42. h ps://doi.o g/
10.3390/g15060042
Academic Edi o : Ul ich Be ge
Recei ed: 27 Sep embe 2024
Re ised: 22 No embe 2024
Accep ed: 29 No embe 2024
Published: 3 Decembe 2024
Copy igh : © 2024 by he au ho .
Licensee MDPI, Basel, Swi ze land.
This a icle is an open access a icle
dis ibu ed unde he e ms and
condi ions o he C ea i e Commons
A ibu ion (CC BY) license (h ps://
c ea i ecommons.o g/licenses/by/
4.0/).
games
A icle
Th eshold P o ocol Game on G aphs wi h Magic
Squa e-Gene aliza ion Labelings
Alexand a Fed igo
Depa men o Ma hema ical Sciences, Uni e si y o Alabama in Hun s ille, 301 Spa kman D i e,
Hun s ille, AL 35899, USA; [email p o ec ed]
Abs ac : G aphical games desc ibe s a egic in e ac ions among a speci ied ne wo k o playe s. The
h eshold p o ocol game is a g aphical game ha models he adop ion o a lesse -used p oduc in
a popula ion when indi iduals bene i by using he same p oduc . The h eshold p o ocol game
has his o ically been conside ed using in ini e, simple g aphs. In gene al, howe e , playe s migh
alue some ela ionships mo e han o he s o may ha e di e en le els o in luence in he g aph.
These ai s a e desc ibed by weigh s on g aph edges o e ices, espec i ely. Rela i e compa isons
on a bi a ily weigh ed g aphs ha e been s udied o a a ie y o g aphical games. Al e na i ely,
g aph labelings a e unc ions ha assign alues o he edges and e ices o g aphs based on a
pa icula se o ules. This wo k demons a es ha he ou come o he h eshold p o ocol game
can be cha ac e ized on a magic squa e-gene aliza ion labeled g aph. The e a e a a ie y o g aph
labelings ha gene alize he concep o magic squa es. In each, he labels on simila se s o g aph
elemen s sum o a cons an . The cons an sums o magic squa e-gene aliza ion labelings mean
ha each playe expe iences a cons an le el o in luence wi hou needing o speci y he alue o
playe s ela i e o one ano he . The game ou come is compa ed ac oss di e en ypes and ea u es
o labelings.
Keywo ds: h eshold; coo dina ion; labelings; magic g aph; sigma g aph; sigma’ g aph; e ex-magic
o al g aph
1. In oduc ion
The aim o g aphical game heo y is o model s a egic in e ac ions be ween playe s
wi h a speci ic ne wo k o ela ionships. The e is a a ie y o applica ions o such sys ems,
om modeling he sp ead o ideas in a popula ion, o desc ibing social ne wo ks, o s udy-
ing a ic low in a ne wo k o de ices. A g aph
G= (V
,
E)
wi h e ex se
V
and edge se
E
is used o desc ibe he ne wo k o playe s. Each
∈V
is a playe and
u ∈E
i
u
and
play agains each o he . The o de o
G
,
n=|V|
, p o ides he numbe o playe s, and he
size o
G
,
e=|E|
, ep esen s he numbe o ela ionships. The applica ion o bo h g aph
and game heo e ic ools means ha a wide ange o ques ions abou g aphical games
can be add essed. When he e a e playe s o g ea e in luence in a g aph o playe s alue
some ela ionships mo e han o he s, weigh ed e ices o edges a e used o deno e he
weigh placed on an in e ac ion. Discussions o game play on such g aphs a e necessa ily
gene al, since playe s o ela ionships may only be compa ed ela i e o one ano he . A
s ic analysis is usually impossible.
G aph labelings, howe e , a e de e mined using pa icula ules on a g aph, meaning
ha much mo e is known abou he e ex o edge alues in he g aph. Labels a e p ecisely
de ined and do no need o be de ined ela i e o one ano he . This means ha g aph
labelings can be easonably expec ed o allow o mo e p ecise cha ac e iza ions o g aphical
game ou comes han gene al weigh ed g aphs.
A h eshold p o ocol game (TPG) is a g aphical game used o model he adop ion o
p oduc s o ideas in a popula ion. I is p ima ily applied as an economic model, bu he
Games 2024,15, 42. h ps://doi.o g/10.3390/g15060042 h ps://www.mdpi.com/jou nal/games
Games 2024,15, 42 2 o 27
TPG also p oduces complex dynamics in a g aph ha can be cha ac e ized. In he TPG,
playe s begin in one o wo s a es. The goal o he game is o he mino i y s a e o ake
o e he popula ion. The TPG p esen s a simple game wi h well-known basic p ope ies,
which makes i an ideal amewo k o s udying he e ec s o labelings on gameplay. He e,
a en ion is paid o ou come o he TPG on magic squa e-gene aliza ion labeled g aphs.
Such a labeling desc ibes some cons an le el o in luence ha all playe s expe ience, which
may be dis ibu ed di e en ly among each playe .
Sec ions 2–4p o ide he p elimina ies o he wo k. Sec ion 2desc ibes he necessa y
g aph labeling backg ound, while Sec ion 3 e iews ela ed g aphical game heo y wo k as
con ex o his wo k. Sec ion 4in oduces he TPG, and he app oach used o analyze he
TPG on he labeled g aphs is ou lined in Sec ion 5. Sec ion 6p o ides he esul s o his
wo k on TPGs using labeled g aphs, which a e discussed in Sec ion 7. Final conclusions
and a enues o u u e wo k a e desc ibed in Sec ion 8.
2. Magic Squa e-Gene alizing G aph Labelings
P io o s udying he TPG on labeled g aphs, he necessa y backg ound ega ding
g aph labelings is gi en. Speci ically, he g aph labelings ha gene alize he p ope ies o
magic squa es a e de ined. In each labeling, a s anda d se o g aph objec s (edges and/o
e ices) is speci ied. The sum o he labels on each such se is a cons an .
G aph labelings a e a widely s udied opic in g aph heo y. A g aph labelingis a
mapping
:K→Z
, whe e
K∈ {V
,
E
,
V∪E}
o , less commonly, ano he se o g aph
ea u es. A mapping
:V→Z
is called a e ex labeling, and a mapping
:E→Z
is
called an edge labeling. The e a e ypically s ic ules go e ning he labels o a g aph.
Labelings ha gene alize he p inciple o magic squa es will be used he e.
The mos popula o hese is a magic labeling. An injec i e mapping
:E→Z+
is called a magic labeling o
G
o cons an
k
i
∑u∈N( ) (u ) = k
o all
∈V
, whe e
N( ) = {u∈V:u ∈E}
is he neighbo hood o
. The cons an
k
is called he magic
cons an . A magic g aph is a g aph ha has a magic labeling. A magic labeling is called
supe magic i he edge labels a e consecu i e in ege s, al hough ypically supe magic e e s
o a magic labeling using in ege s 1, 2, . . . , e.
Magic g aphs ge hei name as hey ollow a simila p inciple o magic squa es. Le
Km,p= (X
,
Y)
deno e a comple e bipa i e g aph whe e
|X|=m
,
|Y|=p
. An
m×m
magic squa e can be used o o m a
Km,m
magic g aph wi h magic cons an
k=m(m2+1)
2
.
Fo example, Figu e 1shows how a 3
×
3 magic squa e is used o p oduce a supe magic
K3,3 [1].
Figu e 1. Example o a magic g aph o o de 6 o med om a 3 ×3 magic squa e.
The e is a clea e ex labeling analog o magic labelings. A bijec i e mapping
:
V→ {
1, 2,
. . .
,
n}
is called a
Σ
-labeling o
G
i , o all
∈V
,
∑u∈N( ) (u) = k
o a
cons an
k
. A g aph wi h a
Σ
-labeling is called a
Σ
-labeled g aph and he cons an
k
is called he e ex sum.
Σ
-labeled g aphs a e mo i a ed by magic squa es, like magic
Games 2024,15, 42 3 o 27
g aphs, al hough e ices a e labeled a he han edges. Figu e 2p o ides examples o wo
e ex-labeled g aphs wi h
k=
14 and
k=
21.
Σ
-labeled g aphs can be cons uc ed using
Σ
-pa i ions [
2
]. A
Σ
-pa i ion o
{
1, 2,
. . .
,
n}
pa i ions
{
1, 2,
. . .
,
n}
in o
m
pa s such ha
he sum o each pa is
k′
. Labeled e ices a e g ouped acco ding o he
Σ
-pa i ion in o
subse s V1, . . . , Vm. Two pa s wi h adjacen e ices o m a comple e bipa i e g aph.
(a)k=14, =2
(b)k=21, =3
Figu e 2. Examples o Σ-labeled g aphs.
A hype g aph is a g aph gene aliza ion such ha an edge may connec any numbe
o e ices. Le each pa o a
Σ
-pa i ion o m a e ex o a hype g aph
H
, so
V(H) =
{V1
,
. . .
,
Vm}
and wo e ices in
V(H)
a e adjacen i any o hei elemen s a e adjacen in
G
. Tha is, i
1
,
2∈V(G)
a e such ha
1∈w1
,
2∈w2
,
1 2∈E(G)
,
w1
,
w2∈V(H)
,
hen
w1w2∈E(H)
. I
H
is
- egula ,
G
is a
Σ
-labeled g aph wi h
k= k′
. Figu e 2p o ides
examples wi h k′=7, and =2 in Figu e 2a and =3 in Figu e 2b.
A
Σ′
-labeling is simila o a
Σ
-labeling, bu he labels a e summed o e e e y closed
neighbo hood in he g aph.
N[ ] = N( )∪ { }
deno es he closed neighbo hood o
∈V
. Then, a
Σ′
-labeling is a bijec ion
:V→ {
1, 2,
. . .
,
n}
such ha o all
∈V
,
∑u∈N[ ] (u) = k
, whe e
k
is a cons an called he e ex sum [
2
,
3
]. A g aph wi h a
Σ′
-
labeling is called a Σ′-g aph.
The e a e a ew magic squa e-gene aliza ion labelings on g aph edges and e ices.
A e ex-magic o al labeling is a bijec ion
:V∪E→ {
1, 2,
. . .
,
n+e}
such ha , o all
∈V
,
( ) + ∑u∈N( ) (u ) = k
, whe e
k
is a cons an called he magic cons an . A g aph
wi h a e ex-magic o al labeling is called a e ex-magic o al g aph [4,5].
An a- e ex consecu i e magic labeling is a e ex-magic o al labeling such ha he
labels on
V
a e
{a+
1,
a+
2,
. . .
,
a+n}
o some
a∈ {
0, 1,
. . .
,
e}
. A g aph ha has an
a- e ex consecu i e magic labeling is called a a- e ex consecu i e magic g aph [
5
,
6
].
Games 2024,15, 42 4 o 27
Simila ly, a b-edge consecu i e magic labeling is a e ex-magic o al labeling such ha
he labels on
E
a e
{b+
1,
b+
2,
. . .
,
b+e}
o some
b∈ {
0, 1,
. . .
,
n}
. A g aph ha has a
b-edge consecu i e magic labeling is called a b-edge consecu i e magic g aph [5,6].
Ano he ype o labeling on e ices and edges is an edge-magic o al labeling, which
is a bijec ion
:V∪E→ {
1, 2,
. . .
,
n+e}
such ha , o all
u ∈E
,
(u) + ( ) + (u ) = k
whe e
k
is a cons an called he magic cons an . A g aph wi h an an edge-magic o al
labeling is called an edge-magic o al g aph [5,7].
The inal g aph labeling ha will be men ioned he e is an H-magic labeling. Le
G
and
H
be g aphs such ha each edge in
G
is in a leas one subg aph isomo phic o
H
. An
H-magic labeling is a bijec ion
:V∪E→ {
1, 2,
. . .
,
n+e}
such ha , o all subg aphs
G′
o
G
whe e
G′
is isomo phic o
H
,
∑ ∈V(G′) ( ) + ∑e∈E(G′) (e) = k
[
5
].While each o hese
labelings will be e e enced, he TPG will be analyzed on magic,
Σ
-,
Σ′
-, and e ex-magic
o al g aphs.
3. Rela ed Wo k
The TPG is a coo dina ion and consensus g aphical game. He e, speci ically labeled
g aphs a e conside ed. G aphical games we e in oduced in [
8
] wi h he goal o desc ibing a
game wi h a se o playe s wi h a speci ic se o in e ac ions. De ining an
n
-playe g aphical
game equi es a g aph
G
o
n
e ices, each ep esen ing a playe , and a se
M
o
n
payo
ma ices, each associa ed wi h a playe . A g aphical game is hen de ined as an o de ed
pai (G,M).
The equilib ia o g aphical games a e o p ima y in e es . A popula ion-wide con-
sensus is a s ong equilib ium in a coo dina ion game like he TPG. In a popula ion-wide
consensus, all playe s ake he same s a egy [
9
]. When s udying consensus, i is o en o
in e es a wha a e consensus occu s [
10
–
18
] o whe he a popula ion can be mo i a ed o
each consensus on a pa icula s a e [
19
]. The e a e se e al well-known g aphical game
ea u es ha in luence he a e o consensus, including g aph connec i i y and he e iciency
o a s a egy. The ocus will be on when consensus occu s o he TPG, since he goal o
he game is o ob ain a popula ion-wide consensus on he mino i y s a e. In o de o
consensus o be achie ed, g aphical games a e usually epea ed, wi h playe s’ s a egies
being upda ed upon each epe i ion. I e a ions o he game may occu con inuously [
20
] o
a disc e e ime s eps [
21
]. Wi h disc e e epe i ions, playe s may selec upda ed s a egies
ei he synch onously o asynch onously [
22
–
24
]. The TPG uses synch onous, disc e e
upda es, and is epea ed an in ini e numbe o imes.
Weigh ed g aphs a e use ul when playe s do no alue all ela ionships equally, and a e
applied o a g aphical game in [
25
–
27
]. I can also be said ha playe s in a g aphical game
ha e weigh s, which deno e he le el o in luence a pa icula playe exe s on each o i s
neighbo s. This ype o weigh ing is s udied in [
28
–
33
]. These weigh ings ypically weigh
g aph ea u es ela i e o one ano he , while a mo e uni o m weigh ing can be achie ed
using g aph labelings.
G aph labelings occasionally occu in he g aphical game heo y li e a u e. Whe e
hey do, he games a e used as a way o gene a e g aph labelings, known as “labeling
games.” In hese games, wo playe s ake u ns labeling edges. The winne may be he las
playe who is able o place a label, playe s may ha e compe ing goals, such as c ea ing
o p e en ing a labeling, e c. The e is limi ed esea ch su ounding such games, bu hey
a e s udied in
[34–40]
. The e has no been wo k on he play o g aphical games on labeled
g aphs. Ra he han using gameplay o de elop labelings, his wo k examines he impac
o labelings on gameplay.
The TPG is a h eshold game, which is a ca ego y o games desc ibed in [
41
]. In a
h eshold game, each playe
∈V
has some weigh ha mus be ac ed on i o mo i a e
o change s a e o o allow
o ecei e a payo [
42
]. The e a e many gene aliza ions
o h eshold games, which a e discussed in [
32
,
43
]. These include al e na i e me hods o
agg ega ing he payo
ecei es om playing agains all o i s neighbo s
u∈N( )
[
19
],
o unique o ime-dependen h eshold alues o each playe [
27
,
42
]. The TPG is a s anda d
Games 2024,15, 42 5 o 27
h eshold game, bu hese gene aliza ions can be applied based on he applica ion. A simple
h eshold game ( he TPG) is used so ha he in luence o g aph labelings on game play
emains clea .
4. Th eshold P o ocol Game
The TPG was in oduced in [
44
], and was discussed and expanded on in [
21
,
43
].
As no ed, Re . [
43
] pa icula ly ocused on gene alizing he game, while Re . [
21
] p ima ily
used he game as an illus a i e example o g aphical games.
In he TPG, playe s a e ini ially in s a e
A
o s a e
B
a ime
0
. The game is epea ed
o e in ini e disc e e ime s eps, and a each s ep all playe s simul aneously choose s a e
A
o s a e
B
. Table 1is he payo ma ix o he TPG s age game, and a playe ’s expec ed
payo is based on he agg ega e expec ed payo o playing he s age game agains all
u∈N( )
. Le he deg ee o
∈V
be deno ed
d( ) = |N( )|
. Then,
di
A( )
,
di
B( )
deno e he
numbe o neighbo s o
o s a e
A
and s a e
B
a ime
i
, espec i ely.
Vi
A
,
Vi
B
a e he se s
o e ices o s a e
A
and s a e
B
a
i
, espec i ely, and
|Vi
A|=ni
A
and
|Vi
B|=ni
B
. A ime
i+1
,
∈V
selec s s a e
A
i
qdi
A( )>(
1
−q)di
B( )
and s a e
B
i
qdi
A( )≤(
1
−q)di
B( )
.
This upda e ule is applied as ollows: ∈Vselec s s a e Bi q≤di
B( )
d( )and Ao he wise.
Table 1. TPG s age game payo ma ix.
A B
Aq0
B0 1 −q
The payo ma ix is de e mined by pa ame e
q∈(
0, 1
)
o gene alize he game,
bu playe s a e incen i ized o ag ee wi h hei neighbo s. In gene al, he game does no
include
q=
0 o
q=
1, since i may be assumed ha i
q=
0, all playe s selec
B
, and i
q=1, all playe s selec A.
S a e
B
begins in he mino i y, bu
V0
B
is nonemp y. The TPG may be played on an
in ini e o ini e g aph, so in an in ini e g aph,
n0
B<∞
, and in a ini e g aph,
n0
B<n
2
.
The p e e ed ou come o he TPG is o s a e
B
o sp ead h oughou he whole g aph. This
means he e exis s a ime s ep
i
such ha
Vi
B=V
. I his occu s,
B
is said o be comple ely
con agious in
G
wi h espec o
q
, o jus comple ely con agious when
G
and
q
a e ob ious.
An ini ial se o s a e
B
e ices,
V0
B
, is called con agious in
G
wi h espec o
q
, o jus
con agious, i Bis comple ely con agious om V0
B.
His o ically, he TPG has been s udied exclusi ely on in ini e g aphs. He e, he use o
a TPG will be conside ed exclusi ely on ini e g aphs, since his wo k seeks o cha ac e ize
he TPG on connec ed and labeled (and he e o e ini e) g aphs. Since he TPG is ypically
used o economic models whe e each e ex is a membe o he popula ion, a ini e g aph
also allows o mo e accu a e modeling.
The TPG is de e minis ic, and he game ou come is de e mined using he g aph
G
on
which he game is played, wi h he se o e ices ini ially in s a e
B
,
V0
B
, and he pa ame e
q. A TPG is hen de ined as an o de ed iple (G,V0
B,q).
Since he TPG is de e minis ic o a pa icula
G
,
V0
B
, and
q
, op imiza ion ques ions
a e o g ea e in e es han he ou come o a ixed
(G
,
V0
B
,
q)
. The e a e wo op imiza ion
ques ions o in e es in he TPG:
1. Wha is he smalles con agious V0
B?
2.
Wha is he la ges alue o
q
such ha
B
is comple ely con agious? This alue o
q
is
called he con agion h eshold and is deno ed q∗.
No e ha i is bene icial o he sp ead o s a e
B
o
n0
B
o be la ge and
q
o be small,
bu hese a e o en expensi e ci cums ances o implemen . Hence, i is desi able o
B
o be
comple ely con agious om a small V0
Bwi h la ge q.
Games 2024,15, 42 6 o 27
An example o TPG play is gi en in Figu e 3. Playe 1 has one neighbo , which is
ini ially o s a e
B
. This means playe 1 expec s a payo o ze o om playing
A
and a payo
o 1
−q=2
3
om playing
B
. Playe 2 has ou neighbo s, wo o which a e ini ially o s a e
A
and wo o which a e ini ially o s a e
B
. Thus, playe 2 expec s a payo o
1
3+1
3=2
3
om playing s a e
A
and a payo o
2
3+2
3=4
3
om playing s a e
B
. The g aph and ini ial
s a es a e symme ic, so all playe s o s a e
A
a e in he same si ua ion as playe 1, and all
playe s o s a e
B
a e in he same si ua ion as playe 2. All playe s p e e s a e
B
o s a e
A
,
so Bis comple ely con agious a e one ime s ep.
Figu e 3. Example o TPG play on an unlabeled, ini e g aph wi h q=1
3.
The exis ence o a con agious
V0
B
o a pa icula alue o
q
has been he ocus o
p e ious wo k, wi h play occu ing on in ini e, connec ed, undi ec ed, simple g aphs.
The g aphs conside ed he e di e only in ha hey a e labeled and ini e. Long- e m game
dynamics in a popula ion a e he ocus o his wo k. Excep ions can a ise when he numbe
o playe s is small. Howe e , he dynamics o he game using a small popula ion a e no
gene ally o in e es , ei he in heo y o applica ion. Fo hese easons, assume
n≥
5. All
in e ac ions a e wo-way and a playe does no play agains hemsel es, so
G
is assumed
o be undi ec ed and does no ha e loops. I does no make sense o s udy he sp ead o
s a es on a disconnec ed g aph, so assume Gis connec ed.
5. Me hod o Analyzing End Beha io o he Th eshold P o ocol Game on
Labeled G aphs
In o de o compa e he in luence o di e en ypes o labelings on he ou come o
he TPG, he game is played on g aphs wi h labelings ha gene alize magic squa es. Such
labelings also ha e he clea es in e p e a ion wi hin he game, and a e hus a clea s a ing
place. Se e al o he mos di ec gene aliza ions a e applied. The edge labeling ha is
conside ed is a magic labeling.
Σ
- and
Σ′
-labelings a e e ex labelings ha a e bo h
used, since hese labelings a e suppo ed by di e en g aph opologies. Finally, e ex-
magic o al labeling is used as a labeling on edges and e ices. Comple e, comple e
bipa i e, and simila g aphs a e examined o each labeling as app op ia e. The ixed
g aph opologies a e exploi ed o cha ac e ize he possible ou comes o he TPG played
on he labeled g aphs. Exis ing esul s ega ding he opological ea u es o g aphs wi h
ce ain labelings a e used o de e mine “app op ia ely simila ”.
The ci cums ances unde which
B
is comple ely con agious a e o p ima y in e es ,
bu o seconda y in e es is he long- e m beha io o he game. Say ha
∈V
has s a ic
end beha io i he e exis s
j
such ha , o all
i≥j
,
does no change s a e a
i
. Then,
has s a ic
A
end beha io i
∈Vi
A
and s a ic
B
end beha io i
∈Vi
B
. Al e na i ely,
has 2-pe iodic end beha io i he e exis s
j
such ha , o
i=
0, 1,
. . .
,
∈Vj+2i
A
and
∈Vj+2i+1
B
, meaning
al e na es s a es. The end beha io is a e ex p ope y, bu he
end beha io o all e ices being s a ic
A
is equi alen o
A
being comple ely con agious
in
G
, and all e ices ha ing a s a ic
B
end beha io is equi alen o
B
being comple ely
con agious in G.
Games 2024,15, 42 7 o 27
Along wi h he g aph ea u es, he h eshold alue
q
is key o de e mining he end
beha io o he TPG in any g aph and
q∗
may change based on he g aph labeling. Thus,
he majo i y o de e mina ions ega ding he TPG end beha io a e dependen on hese
componen s. O en, a bound on he alue o
q
is selec ed o mo i a e
B
o be comple ely
con agious. He e, a low, ob ious bound on
q
is p o ided o i s ind a minimum-sized
con agious
V0
B
. When
V0
B
o
G
a e chosen ca e ully, a highe uppe bound on
q
can be
p o ided such ha
B
is comple ely con agious. Whe e possible, his alue is con as ed
wi h a lowe bound on
q
such ha
A
is comple ely con agious, o wi h bounds ha will
allow o an al e na i e end beha io o occu . Clea ly, each bound is applicable only i
i is in
(
0, 1
)
.
G
is ixed wi h a simple opology, such as a comple e o comple e bipa i e
g aph. Then, bounds on
q
ha cause a pa icula end beha io o occu a e p o ided o an
a bi a y
V0
B
in e ms o
V0
B
and he g aph labeling. De ails ega ding he app oaches used
o each g aph labeling a e discussed in he co esponding sec ion.
6. Resul s
The ou come o he TPG is conside ed using magic g aphs,
Σ
-g aphs,
Σ′
-g aphs, and
e ex-magic o al g aphs. Fo each labeling, a comple ely con agious
V0
B
can be iden i ied
o a su icien ly small
q
. I is also shown ha , o each labeling, a cha ac e iza ion o he
TPG ou comes is possible on comple e and comple e bipa i e g aphs in e ms o he g aph
labeling. Some labelings ha e addi ional ea u es ha can be exploi ed o d aw u he
conclusions abou TPG beha io when using he labeled g aphs.
6.1. Th eshold P o ocol Game on Magic G aphs
Le
G
be a weigh ed g aph wi h
λu
deno ing he weigh o
u ∈E
. When he
TPG is played on a weigh ed g aph,
∈V
will ake s a e
B
a
i+1
i
q∑u∈Ni
A( )λu ≤
(1−q)∑u∈Ni
B( )λu , o q≤
∑u∈Ni
B( )λu
∑u∈N( )λu , and Ao he wise.
The de ini ions o g aph labelings mean ha he e a e e y speci ic ules go e ning
a g aph labeling. Taking edge labels as edge weigh s, he TPG can be played on he
esul ing weigh ed g aph. In he case o magic g aphs,
∈V
will ake s a e
B
a
i+1
i
q≤
∑u∈Ni
B( )λu
∑u∈N( )λu =
∑u∈Ni
B( )λu
k
, and
A
o he wise. An example o TPG play on a magic g aph
is p o ided in Figu e 4. The magic g aph has
k=
15 and six playe s, wo o whom begin in
s a e B. Then, wi h q=1
15 ,Bis comple ely con agious a e one ime s ep.
Figu e 4. Example o TPG play on a magic g aph wi h q=1
15 and k=15.
I is i s shown ha , o small enough q, he e exis s a con agious V0
B o all G.
Theo em 1. Le
G
be a magic g aph wi h magic cons an
k
. Le
m=min{λu :u ∈E}
and
q≤m
k.
(a) I G is non-bipa i e, B is comple ely con agious o V0
B={ } o all ∈V.
(b)
I
G= (X
,
Y)
is bipa i e, wi h pa i e se s
X
and
Y
,
B
is comple ely con agious o
V0
B={ 1, 2} o all 1∈X, 2∈Y.
Games 2024,15, 42 8 o 27
P oo .
No e ha o all
∈V
,
q≤m
k≤∑u ∈Fλu
k o all F⊆E
. Thus, i
∈N(Vi
B)
, hen
∈Vi+1
B.
(a)
Suppose
G
is non-bipa i e and
n0
B=
1. No e he common esul ha s a es ha
a g aph is non-bipa i e i and only i i con ains an odd cycle. Le
C
be an odd
cycle in
G
. Since
G
is connec ed and
∈Vi+1
B
i
∈N(Vi
B)
, he e exis s
i1
such
ha he e exis s
∈C
, such ha
∈Vi1
B
. Clea ly,
|C∩Vi1
B|>
1 is mo e con agious
in
C
han
|C∩Vi1
B|=
1, so conside he wo s -case scena io
|C∩Vi1
B|=
1. Since
C
is an odd cycle, he e exis s
i2>i1
such ha
1
,
2∈C
,
1
,
2∈Vi2
B
, and
1∼ 2
.
Fo all
i≥i2
,
1
,
2∈Vi
B
. Then, o all
k∈N
,
N(k)({ 1
,
2})⊆Vi2+k
B
, whe e
N(k)({ 1
,
2}) = N(N(. . . N({ 1
,
2}). . . ))
. Since
G
is connec ed, he e exis s
k′
such ha N(k′)({ 1, 2}) = V. Hence, B is comple ely con agious in G.
(b)
Suppose
G
is bipa i e and
V0
B={ 1
,
2}
wi h
1∈X
,
2∈Y
. No e ha o all
k∈N
,
N(k)( 1)⊆Vk
B
and
N(k)( 2)⊆Vk
B
. Since
G
is connec ed, he e exis s
k′
such
ha
N(k′)( 1) = X
and
N(k′)( 2) = Y
. Then,
Vk′
B=X∪Y=V
, so
B
is comple ely
con agious in G.
Since
n≥
5,
V0
B
in Theo em 1is a mino i y in
G
,
q∗≥min{λu :u ∈E}
k
in a magic g aph.
This heo em desc ibes a bes -case scena io o
n0
B
bu a wo s -case scena io o
q
in e ms o
he op imiza ion ques ions posed abo e. By mo e ca e ully selec ing
V0
B
and
G
, he bound
on qcan be imp o ed.
Comple e and comple e bipa i e g aphs desc ibe a ully egula g aph opology;
hus, he play o he TPG on magic comple e and comple e bipa i e g aphs allows o he
in luence o he g aph labeling on game ou come o be clea ly conside ed. Le
e′=|{u ∈
E: ∈V0
B}| =∑n0
B
i=1(n−i) = n0
B(2n−n0
B−1)
2
deno e he numbe o edges wi h a leas one
e ex in
V0
B
. Le
{λu 1
,
λu 2
,
. . .
,
λu e′}={λu : ∈V0
B}
such ha
λu 1<λu 2<· · · <
λu e′. Finally, le m=∑n0
B−1
i=1λu i,M=∑e′
i=e′−n0
B
λu i.
Theo em 2. Le Knbe a comple e magic g aph.
(a) I n0
B=1, wi h V0
B={ }, and q ≤min{λu :u∈N( )}
k, hen B is comple ely con agious.
(b) I n0
B>1, and q ≤m
k, hen B is comple ely con agious.
(c) I q >M
k, hen A is comple ely con agious.
P oo . Le Knbe a comple e magic g aph.
(a)
Suppose
n0
B=
1, wi h
V0
B={ }
, and
q≤min{λu :u∈N( )}
k
. Since
N( ) = V0
A
,
∈V1
A
.
Fo
u∈V0
A
,
∑w∈N0
B(u)λuw
k=λu
k>min{λu :u∈N( )}
k≥q
, so
u∈V1
B
. Then
V1
A={ }
, so
N( ) = V1
B
, and
∈V2
B
. Fo all
u∈V1
B
,
∑w∈N0
B(u)λuw
k=k−λu
k≥min{λu :u∈N( )}
k≥q
since n≥5, so u∈V2
B. Thus, Bis comple ely con agious a e wo ime s eps.
(b)
Suppose
n0
B>
1, and
q≤m
k
. Fo
∈V0
B
,
∑u∈N0
B( )λu
k=
∑u∈V0
B { }λu
k≥m
k≥q
, so
∈V1
B
. Fo
∈V0
A
,
∑u∈N0
B( )λu
k=
∑u∈V0
B
λu
k≥m
k>q
, so
∈V1
B
. Thus,
V1
B=V
,
and Bis comple ely con agious a e one ime s ep.
(c)
Suppose
q>M
k
,
M<k
. Fo
∈V0
B
,
∑u∈N0
B( )λu
k=
∑u∈V0
B { }λu
k≤M
k<q
, so
∈V1
A
.
Fo
∈V0
A
,
∑u∈N0
B( )λu
k=
∑u∈V0
B
λu
k≤M
k<q
, so
∈V1
A
. Thus,
V1
A=V
, and
A
is
comple ely con agious a e one ime s ep.
Games 2024,15, 42 15 o 27
Figu e 8. Example o TPG play on a Σ′-g aph wi h q=1
14 and k=15.
As p e iously, i s conside he bound on
q
o he minimum con agious
V0
B
in a
Σ′
-
labeled g aph.
Theo em 8. Le G be a Σ-labeled g aph wi h e ex sum k. Le q ≤1
k−1.
(a) I G is non-bipa i e, B is comple ely con agious o V0
B={ } o all ∈V.
(b)
I
G= (X
,
Y)
is bipa i e,
B
is comple ely con agious o
V0
B={ 1
,
2}
o all
1∈X
,
2∈Y.
P oo .
No e ha
q≤1
k−1≤∑ ∈Wλ
k−1≤∑ ∈Wλ
k−λ o all W⊆V
,
∈V
. Thus, i
∈N(Vi
B)
,
hen ∈Vi+1
B, so he p oo s o (a)and (b)a e he same as in he p oo o Theo em 1.
Theo em 8indica es ha
q∗≥1
k−1
in a
Σ′
-labeled g aph. Theo em 13 in Re . [
3
] s a es
ha a comple e
m
-pa i e g aph
Kp1,p2,...,pm
is a
Σ′
-labeled g aph, i and only i ,
pi=
1 o
all
i=
1, 2,
. . .
,
m
, i.e., i
Kp1,p2,...,pm=Kn
. Clea ly, on
Kn
,
k=n(n+1)
2
. Conside he TPG on
aΣ′-labeled Kn.
Theo em 9. Le Knbe a Σ′-labeled comple e g aph.
(a) I n0
B=1such ha V0
B={ }, hen B is comple ely con agious in G i q ≤λ
k−1.
(b)
I
n0
B>
1, hen
B
is comple ely con agious in
G
i
q≤
∑u∈V0
B
λu−m
k−1
, whe e
m=max{λ :
∈V0
B}.
(c) A is comple ely con agious in G i q >
∑u∈V0
B
λu
k−n.
P oo . (a)
Suppose
n0
B=
1 wi h
V0
B={ }
. Then,
∈V1
A
since
N( ) = V0
A
. Fo
w∈V0
A
,
∑u∈N0
B(w)λu
k−λw
=λ
k−λw
≥λ
k−1
≥q
Games 2024,15, 42 16 o 27
so
w∈V1
B
and
V0
A=V1
B
. Conside
V1
A={ }
. Then, o
,
N( ) = V1
B
, so
∈V2
B
.
Fo all w∈V1
B,
∑u∈N0
B(w)λu
k−λw
=∑u∈V { ,w}λu
k−λw
=k−λ −λw
k−λw
≥k−λ −λw
k−1
≥λ
k−1since n≥5
≥q
so
w∈V2
B
. Thus,
V2
B=V
, and
B
is comple ely con agious in
Kn
a e wo ime s eps.
(b) Suppose n0
B>1, and le m=max{λ : ∈V0
B}. Le q≤
∑u∈V0
B
λu−m
k−1.
Fo all ∈V0
A,
∑u∈N0
B( )λu
k−λ
=
∑u∈V0
B
λu
k−λ
≥
∑u∈V0
B
λu
k−1
>
∑u∈V0
B
λu−m
k−1
≥q
so ∈V1
Band V0
B⊆V1
B.
Fo all ∈V0
B,
∑u∈N0
B( )λu
k−λ
=
∑u∈V0
B { }λu
k−λ
=
∑u∈V0
B
λu−λ
k−λ
≥
∑u∈V0
B
λu−m
k−1
≥q
so
∈V1
B
and
V0
A⊆V1
B
. Thus,
V1
B=V
, and
B
is comple ely con agious a e one
ime s ep.
(c) Le q>
∑u∈V0
B
λu
k−n.
Fo all ∈V0
A,
∑u∈N0
B( )λu
k−λ
=
∑u∈V0
B
λu
k−λ
≤
∑u∈V0
B
λu
k−n
<q
Games 2024,15, 42 17 o 27
so ∈V1
Aand V0
B⊆V1
A.
Fo all ∈V0
B,
∑u∈N0
B( )λu
k−λ
=
∑u∈V0
B { }λu
k−λ
=
∑u∈V0
B
λu−λ
k−λ
<
∑u∈V0
B
λu
k−n
<q
so
∈V1
A
and
V0
A⊆V1
A
. Thus,
V1
A=V
, and
A
is comple ely con agious in one
ime s ep.
Since he magic cons an is de e mined by he sum o e each closed neighbo hood,
he esul s o he
Σ′
-labeled g aphs a e less conclusi e han hose o
Σ
-labeled g aphs.
Howe e , hese wo labelings a e also suppo ed by di e en g aph opologies. Fo example,
he e does no exis a
Σ
-labeled comple e g aph, while he only
m
-pa i e
Σ′
-labeled g aphs
ha exis a e comple e.
6.4. Th eshold P o ocol Game on Ve ex-Magic To al G aphs
So a , he TPG on g aphs wi h edge o e ex labelings has been conside ed. The inal
common ype o g aph labeling is on he e ices and edges o
G
. When he TPG is played
using a g aph wi h e ex and edge labels,
∈V
akes s a e
B
in
i+1
i
q∑u∈Ni
A( )(λu+
λu )≤(
1
−q)∑u∈Ni
B( )(λu+λu )
, o
q≤
∑u∈Ni
B( )(λu+λu )
∑u∈N( )(λu+λu )
, and
A
o he wise. Then,
on a e ex-magic o al g aph,
∈V
akes s a e
B
in
i+1
i
q≤
∑u∈Ni
B( )(λu+λu )
∑u∈N( )(λu+λu )=
∑u∈Ni
B( )(λu+λu )
(k−λ )+∑u∈N( )λu
, and
A
o he wise. An example o TPG play wi h a e ex-magic o al
g aph is p esen ed in Figu e 9. This is a pa icula ly nice e ex-magic o al g aph as i is
also a 0-edge consecu i e magic g aph and 4- e ex consecu i e magic g aph. The e ex-
magic o al g aph has
k=
11 and i e playe s, wo o whom begin in s a e
B
. Then, wi h
q=1
4,Bis comple ely con agious a e wo ime s eps.
Figu e 9. Example o TPG play on a e ex-magic o al g aph wi h q=1
4and k=11.
Conside a minimum con agious V0
B o a small q.
Theo em 10. Le
G
be a e ex-magic o al g aph wi h magic cons an
k
. Deno e he maximum
deg ee o G using ∆and m =min{λu+λu :u ∈E}. Le q ≤m
k−1+∆(n+e).
(a) I G is non-bipa i e, B is comple ely con agious o V0
B={ } o all ∈V.
Games 2024,15, 42 18 o 27
(b)
I
G= (X
,
Y)
is bipa i e,
B
is comple ely con agious o
V0
B={ 1
,
2}
o all
1∈X
,
2∈Y.
P oo .
No e ha o all
∈V
,
q≤m
k−1+∆(n+e)<
λ ′+λ ′
(k−λ )+∑u∈N( )λu
, such ha
′∈E
. Thus,
i
∈N(Vi
B)
, hen
∈Vi+1
B
, so he p oo o
(a)
and
(b)
a e he same as in he p oo o
Theo em 1.
Since
n≥
5, Theo em 10 indica es ha
q∗≥min{λu+λu :u ∈E}
k−1+∆(n+e)
in a e ex-magic
o al g aph. In Re . [
47
], i is p o ed ha he e exis s a e ex-magic o al
Kn
o all
n≡
0
(mod
4
)
. Thus, he e exis e ex-magic o al comple e g aphs and he TPG can be
conside ed on e ex-magic o al comple e g aphs.
Theo em 11. Le Knbe a e ex-magic o al comple e g aph. Le K=∑u∈Vλu.
(a) I n0
B=1wi h V0
B={ }, hen B is comple ely con agious i q ≤min{λu+λuw:uw∈E})
k−2+K
(b)
I
n0
B>
1, hen
B
is comple ely con agious i
q≤
∑u∈V0
B
(λu+min{λu : ∈N(u)})−max{λu:u∈V0
B}
k−2+K
(c) A is comple ely con agious i q >
∑u∈V0
B
(λu+max{λu : ∈N(u)})
k−2 max{λu:u∈V}+K
P oo . (a)
Suppose
n0
B=
1,
V0
B={ }
, and
q≤min{λu+λu :u ∈E})
k−2+K
. Fo
such ha
V0
B={ },N( ) = V0
A, so ∈V1
A. Fo w∈V0
A,
∑u∈N0
B(w)(λu+λuw)
k−λw+∑u∈N(w)λu
=λ +λw
k−2λw+K
≥min{λu+λuw :uw ∈E})
k−2+K
≥q
so
w∈V1
B
. Thus,
V0
A=V1
B
and
V1
A={ }
. Thus,
N( ) = V1
B
, so
∈V2
B
. Fo all
w∈V1
B,
∑u∈N0
B(w)(λu+λuw)
k−λw+∑u∈N(w)λu
=∑u∈V(λu+λuw)−(λ +λw )−λw
k−2λw+K
≥min{λu+λuw :uw ∈E})
k−2+Ksince n≥5
≥q
so w∈V2
B. Thus, V2
B=V, so Bis comple ely con agious a e wo ime s eps.
(b) Suppose n0
B>1 and q≤
∑u∈V0
B
(λu+min{λu : ∈N(u)})−max{λu:u∈V0
B}
k−2+K. Fo all ∈V0
A,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=
∑u∈V0
B(λu+λu )
k−2λ +K
≥
∑u∈V0
B(λu+min{λuw :w∈N(u)})
k−2+K
≥
∑u∈V0
B(λu+min{λuw :w∈N(u)})−max{λu:u∈V0
B}
k−2+K
≥q
Games 2024,15, 42 19 o 27
so ∈V1
Band V0
A⊆V1
B. Fo all ∈V0
B,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=∑u∈V0
B(λu+λu )−λ
k−2λ +K
≥∑u∈V0
B(λu+λu )−max{λu:u∈V0
B}
k−2+K
≥∑u∈V0
B(λu+min{λuw :w∈N(u)})−max{λu:u∈V0
B}
k−2+K
≥q
so
∈V1
B
and
V0
B⊆V1
B
. Thus,
V1
B=V
, so
B
is comple ely con agious a e one
ime s ep.
(c) Suppose n0
B>1 and q>
∑u∈V0
B
(λu+max{λu : ∈N(u)})
k−2 max{λu:u∈V}+K. Fo all ∈V0
A,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=
∑u∈V0
B(λu+λu )
k−2λ +K
≤
∑u∈V0
B(λu+max{λuw :w∈N(u)})
k−2 max{λu:u∈V}+K
<q
so ∈V1
Aand V0
A⊆V1
A. Fo all ∈V0
B,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=∑u∈V0
B(λu+λu )−λ
k−2λ +K
≤∑u∈V0
B(λu+max{λuw :w∈N(u)})−λ
k−2 max{λu:u∈V}+K
≤∑u∈V0
B(λu+max{λuw :w∈N(u)})
k−2 max{λu:u∈V}+K
<q
so
∈V1
A
and
V0
A⊆V1
A
. Thus,
V1
A=V
, and
A
is comple ely con agious a e one
ime s ep.
Along wi h he esul s ob ained o e ex-magic o al comple e g aphs, Re . [
47
]
con ains a p oo ha
Kp,p
is he e ex-magic o al o all
p>
1. In a e inemen o his
esul , Re . [
4
] concludes ha
Km,p
is no e ex-magic o al i
|m−p|>
1. Tha said, he e
exis s a e ex-magic o al Km,pon which he TPG can be conside ed.
Theo em 12. Le
Km,p= (X
,
Y)
be a e ex-magic o al comple e bipa i e g aph. Le
X=
∑u∈Xλuand Y=∑u∈Yλu.
(a) B is comple ely con agious i
q≤min{
∑u∈V0
B∩X(λu+min{λu : ∈N(u)})
k−min{λ : ∈Y}+X,
∑u∈V0
B∩Y(λu+min{λu : ∈N(u)})
k−min{λ : ∈X}+Y}.
(b) A is comple ely con agious i
q>max{
∑u∈V0
B∩X(λu+max{λu : ∈N(u)})
k−max{λ : ∈Y}+X,
∑u∈V0
B∩Y(λu+max{λu : ∈N(u)})
k−max{λ : ∈X}+Y}.
(c) The end beha io on Km,pis 2-pe iodic i
Games 2024,15, 42 20 o 27
∑u∈V0
B∩Y(λu+max{λu : ∈N(u)})
k−max{λ : ∈X}+Y}<q≤
∑u∈V0
B∩X(λu+min{λu : ∈N(u)})
k−min{λ : ∈Y}+X
o
∑u∈V0
B∩X(λu+max{λu : ∈N(u)})
k−max{λ : ∈Y}+X<q≤
∑u∈V0
B∩Y(λu+min{λu : ∈N(u)})
k−min{λ : ∈X}+Y}.
P oo . (a) Suppose
q≤min{
∑u∈V0
B∩X(λu+min{λu : ∈N(u)})
k−min{λ : ∈Y}+X,
∑u∈V0
B∩Y(λu+min{λu : ∈N(u)})
k−min{λ : ∈X}+Y}.
Then, o all ∈X,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=
∑u∈V0
B∩Y(λu+λu )
k−λ +Y
≥
∑u∈V0
B∩Y(λu+min{λuw :w∈N(u)})
k−min{λw:w∈X}+Y
≥q
so ∈V1
B. Fo all ∈Y,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=
∑u∈V0
B∩X(λu+λu )
k−λ +X
≥
∑u∈V0
B∩X(λu+min{λuw :w∈N(u)})
k−min{λw:w∈Y}+X
≥q
so ∈V1
B. Thus, V1
B=V, and Bis comple ely con agious a e one ime s ep.
(b) Suppose
q>max{
∑u∈V0
B∩X(λu+max{λu : ∈N(u)})
k−max{λ : ∈Y}+X,
∑u∈V0
B∩Y(λu+max{λu : ∈N(u)})
k−max{λ : ∈X}+Y}.
Then, o all ∈X,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=
∑u∈V0
B∩Y(λu+λu )
k−λ +Y
≤
∑u∈V0
B∩Y(λu+max{λuw :w∈N(u)})
k−max{λw:w∈X}+Y
<q
so ∈V1
A. Fo all ∈Y,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=
∑u∈V0
B∩X(λu+λu )
k−λ +X
≤
∑u∈V0
B∩X(λu+max{λuw :w∈N(u)})
k−max{λw:w∈Y}+X
<q
so ∈V1
A. Thus, V1
A=V, and Ais comple ely con agious a e one ime s ep.
Games 2024,15, 42 21 o 27
(c) Suppose
∑u∈V0
B∩Y(λu+max{λu : ∈N(u)})
k−max{λ : ∈X}+Y}<q≤
∑u∈V0
B∩X(λu+min{λu : ∈N(u)})
k−min{λ : ∈Y}+X.
Then, o all ∈X,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=
∑u∈V0
B∩Y(λu+λu )
k−λ +Y
≤
∑u∈V0
B∩Y(λu+max{λuw :w∈N(u)})
k−max{λw:w∈X}+Y
<q
so ∈V1
A. Fo all ∈Y,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=
∑u∈V0
B∩X(λu+λu )
k−λ +X
≥
∑u∈V0
B∩X(λu+min{λuw :w∈N(u)})
k−min{λw:w∈Y}+X
≥q
so
∈V1
B
. Hence,
X=V1
A
and
Y=V1
B
. Fo all
∈X
,
N( ) = V1
B
, and o all
∈Y
,
N( ) = V1
B
. I e a ing,
X=V2i−1
B
and
Y=V2i−1
A
, while
X=V2i
A
and
Y=V2i
B
,
i=1, 2, . . . . Thus, he end beha io o he TPG is 2-pe iodic.
Al e na i ely, suppose
∑u∈V0
B∩X(λu+max{λu : ∈N(u)})
k−max{λ : ∈Y}+X<q≤
∑u∈V0
B∩Y(λu+min{λu : ∈N(u)})
k−min{λ : ∈X}+Y}.
Then, o all ∈X,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=
∑u∈V0
B∩Y(λu+λu )
k−λ +Y
≥
∑u∈V0
B∩Y(λu+min{λuw :w∈N(u)})
k−min{λw:w∈X}+Y
≥q
so ∈V1
B. Fo all ∈Y,
∑u∈N0
B( )(λu+λu )
k−λ +∑u∈N( )λu
=
∑u∈V0
B∩X(λu+λu )
k−λ +X
≤
∑u∈V0
B∩X(λu+max{λuw :w∈N(u)})
k−max{λw:w∈Y}+X
<q
so
∈V1
A
. Hence,
X=V1
B
and
Y=V1
A
. Fo all
∈X
,
N( ) = V1
A
, and o all
∈Y
,
N( ) = V1
A
. I e a ing,
X=V2i−1
A
and
Y=V2i−1
B
, while
X=V2i
B
and
Y=V2i
A
,
i=1, 2, . . . . Thus, he end beha io o he TPG is 2-pe iodic.
The analysis o a TPG using e ex-magic o al g aphs is unique in his wo k because
o he in luence o labels on bo h he edges and e ices o G. Tha said, esul s analogous
Games 2024,15, 42 22 o 27
o hose ound o edge labelings and e ex labelings a e achie able, al hough comple e
cha ac e iza ion is no possible o an a bi a y V0
B.
6.5. Equi alen and nea Equi alen Labelings
The e a e se e al o he magic squa e-gene aliza ion labelings on he edges and e ices
o g aphs ha should be men ioned. Howe e , TPG gameplay on g aphs wi h hese label-
ings is equi alen o sys ems al eady discussed, so hey will no be s udied
independen ly
.
6.5.1. Th eshold P o ocol Game on a-Ve ex Consecu i e and b-Edge Consecu i e
Magic G aphs
An a- e ex consecu i e magic labeling is a ype o e ex-magic o al labeling. Thus,
esul s ob ained o e ex-magic o al g aphs can be e ined on a- e ex consecu i e magic
g aphs, and Theo ems 10 and 11 can be es a ed in e ms o a- e ex consecu i e magic
g aphs. No e ha pa icula e ex labels e e enced in Theo em 12 canno be u he
speci ied, so he esul s a e no e ined on a- e ex consecu i e magic g aphs.
Theo em 13. Le
G
be an a- e ex consecu i e magic g aph wi h magic cons an
k
. Le
m=
min{λu+λu :u ∈E}and q ≤m
k−a−1+∆(a+n).
(a) I G is non-bipa i e, B is comple ely con agious o V0
B={ } o all ∈V.
(b)
I
G= (X
,
Y)
is bipa i e,
B
is comple ely con agious o
V0
B={ 1
,
2}
o all
1∈X
,
2∈Y.
Theo em 14. Le Knbe an a- e ex consecu i e magic g aph. Le K=∑u∈Vλu=n(2a+n+1)
2.
(a) I n0
B=1wi h V0
B={w}, hen B is comple ely con agious i q ≤min{λu+λu :u ∈E})
k−2(a+1)+K.
(b)
I
n0
B>
1, hen
B
is comple ely con agious i
q≤
∑u∈V0
B
(λu+min{λu : ∈N(u)})−max{λu:u∈V0
B}
k−2(a+1)+K
.
(c) I n0
B>1 hen A is comple ely con agious i q >
∑u∈V0
B
(λu+max{λu : ∈N(u)})
k−2(a+n)+K.
b-edge consecu i e magic labelings a e also a ype o e ex-magic o al labeling.
Thus, esul s o e ex-magic o al g aphs also apply o b-edge consecu i e magic g aphs.
Howe e , Theo ems 10–12 do no ely on he use o pa icula possible edge labels, so he
esul s canno be e ined using b-edge consecu i e magic g aphs.
6.5.2. Th eshold P o ocol Game on Edge-Magic To al G aphs
Conside he play o a TPG on an edge-magic o al g aph. Since an edge-magic o al
labeling is a labeling on bo h he e ices and edges o
G
, a e ex
∈V
akes s a e
B
a
i+1i q≤
∑u∈Ni
B( )(λu+λu )
∑u∈N( )(λu+λu ), which can be e ined on an edge-magic o al g aph as
q≤
∑u∈Ni
B( )(λu+λu )
∑u∈N( )(λu+λu )
=di
B( )(k−λ )
d( )(k−λ )
=di
B( )
d( ).
Thus, he h eshold o he TPG in an edge-magic o al g aph is he same as he h eshold in
a simple g aph, which means ha e ices upda e s a es as in he classic TPG. Hence, he
play o he TPG is equi alen be ween edge-magic o al g aphs and unlabeled g aphs.
Games 2024,15, 42 23 o 27
7. Discussion
The upda e ule o he classic TPG s a es ha
∈V
akes s a e
B
a
i+1
i
q≤di
B( )
d( )
and
A
o he wise. On a labeled g aph, he upda e ule changes based on he ype o labeling.
In an edge labeled g aph,
akes s a e
B
i
q≤
∑u∈Ni
B( )λu
∑u∈N( )λu
, in a e ex labeled g aph i
q≤
∑u∈Ni
B( )λu
∑u∈N( )λu
, and in a g aph wi h e ex and edge labels i
q≤
∑u∈Ni
B( )(λu+λu )
∑u∈N( )(λu+λu )
. The e
may be es ic ions on g aph opology based on he labelings used, bu p ope ies o he
TPG ha do no depend on qhold ega dless o labeling.
Unlike andomly weigh ed g aphs o a bi a y in luence g aphs, a g aph labeling
p o ides a ully speci ied scheme o he weigh s and/o in luence alues. This wo k
demons a es ha he ou come o he TPG may be cha ac e ized in e ms o a g aph
labeling wi h a ew ca ea s. Since a- e ex consecu i e and b-edge consecu i e magic
labelings a e examples o e ex-magic o al labelings, hey will no cu en ly be conside ed
sepa a ely. The e a e ou labelings o p ima y in e es . A magic labeling is an edge labeling,
Σ
- and
Σ′
-labelings a e e ex labelings, and a e ex-magic o al labeling is a labeling
on bo h e ices and edges, bu all ollow a simila p inciple in which he labels o some
subse s o elemen s sum o a cons an .
Two ypes o esul s a e p o ided o each labeling. Fi s , a low (wo s -case) bound
on
q
is p o ided, which allows o a minimum
V0
B
o be con agious in an a bi a y
G
,
whe e es ic ions on
V0
B
a e de e mined only by whe he
G
is non-bipa i e o bipa i e.
This
V0
B
is ad an ageous because i equi es no pa icula selec ion o e ices when
G
is non-bipa i e, and equi es only ha a e ex is selec ed om each pa i e se when
G
is bipa i e. A e sion o his esul is achie able o all he labelings conside ed he e.
Hence, o each o hese ou labelings, he e exis comple ely con agious
V0
B
’s, and a lowe
bound on
q∗
is p o ided by Theo em 1on magic g aphs, Theo em 5on
Σ
-labeled g aphs,
Theo em 8on
Σ′
-labeled g aphs, and Theo em 10 on e ex-magic o al g aphs. A simila
esul can be achie ed o
Σ
-labeled g aphs in e ms o
Σ
-pa i ion hype g aphs, which is
shown in Theo em 6.
Second, a cha ac e iza ion is p o ided o a ia ions on comple e and comple e bipa i e
g aphs, as app op ia e. I is ypical o conside s ongly egula magic g aphs, which
include comple e and comple e bipa i e g aphs. Theo em 4and Co olla y 1desc ibe a
be e bound on
q
han Theo em 1 o a simila
n0
B
, bu some ca e mus be aken in selec ing
V0
B
. Addi ionally, since hey depend on
G
being s ongly egula , hese esul s do no
hold on all magic g aphs. Co olla y 2gene alizes he maximum spanning ee app oach
o all magic g aphs, wi h
n0
B=
2. This esul p o ides a same o sligh ly wo se
n0
B
han
Theo em 1, bu he bound on
q
may be be e . Tha said, he e a e also es ic ions on
V0
B
,
making he esul o Co olla y 2mo e es ic i e han ha o Theo em 1.
While he main goal o he TPG is o mo i a e
B
o be comple ely con agious, he e a e
se s o pa ame e s o which
B
will no be comple ely con agious.
G
,
V0
B
, and
q
each play a
key ole in he end beha io he TPG will exhibi . To s udy he in luence o labelings on
game ou come, which impac easible bounds on
q
,
G
is ixed as a comple e o comple e
bipa i e g aph, and
V0
B
is a bi a y. Theo ems 2and 3cha ac e ize he end beha io
o a TPG on magic comple e and comple e bipa i e g aphs. The e a e no
Σ
-labeled
comple e g aphs, bu Theo em 7cha ac e izes he play o he TPG on
Σ
-labeled comple e
bipa i e g aphs. In con as , he o he e ex labeled g aphs ha we e conside ed,
Σ′
-
labeled g aphs, do no exis o comple e bipa i e g aphs, bu do exis o comple e
g aphs. Thus, Theo em 9cha ac e izes he play o he TPG on
Σ′
-labeled comple e g aphs.
Theo ems 11 and 12
desc ibe he ou comes o he TPG when using e ex-magic o al
comple e and comple e bipa i e g aphs, espec i ely. The bounds on
q
in hese esul s a e
ideal, since hey a e p o ided in e ms o
V0
B
and he g aph labeling, which a e pa s o
he game de ini ion. Fo all comple e labeled g aphs, an uppe bound can be ound on
q
such ha
B
is comple ely con agious and a lowe bound can be ound on
q
such ha
A
is comple ely con agious. This is also ue o comple e bipa i e g aphs, al hough he e
Games 2024,15, 42 24 o 27
may also exis an in e al
I⊆(
0, 1
)
such ha
q∈I
causes a 2-pe iodic end beha io in he
TPG. No e, howe e , ha hese s a emen s hold p o ided he bound(s) all in
(
0, 1
)
. While
gene al cha ac e iza ions a e p o ided, he only labeling conside ed he e o which he
cha ac e iza ion on
Kn
o
Km,p
is comple e is he
Σ
-labeling. A comple e cha ac e iza ion
o he o he labelings would depend on each e ex in
V0
B
, which is nei he easible no
gene al enough o be o in e es .
The e a e a ew addi ional compa isons ha can be d awn be ween he labelings based
on hese esul s. Fi s , he labeling on he edges and e ices o a g aph esul s in he
mos complex upda e ule o he TPG. The upda e ules o edge and e ex labelings
a e simila in e ms o complexi y. This sugges s ha when conside ing o he labelings,
cha ac e iza ions o g aphs wi h labeled e ices and edges may no be possible o he
ex en ha cha ac e iza ions on g aphs wi h e ex labelings o edge labelings can be ound.
Howe e , in he magic-squa e gene aliza ion labelings conside ed in his wo k, he ype
o labeling is no he p ima y ac o in he le el o cha ac e iza ion ha can be achie ed.
No e ha he cons an sum a each
∈V
is independen o
λ
o magic and
Σ
-g aphs,
bu dependen on
λ
o
Σ′
- and e ex-magic o al g aphs. S onge and mo e a ied
cha ac e iza ions o he TPG a e possible when using magic and
Σ
-g aphs han
Σ′
- and
e ex-magic o al g aphs, since he analysis is simpli ied o hese labelings.
8. Conclusions
The TPG is a aluable and simple economic model wi h in e es ing dynamics. The p i-
ma y aim o he TPG is o s udy he ci cums ances unde which a s a e ha begins in
he mino i y will o e ake he popula ion. His o ically, his game has been s udied using
unweigh ed g aphs and unlabeled playe s. This means ha he ou come o he TPG is
s udied when all playe s and he ela ionships be ween hem ha e equal alue in he
game. In con as , playing he game wi h a labeled g aph equi es accoun ing o he
pa icula scheme o alues applied o each playe and/o ela ionship. A magic squa e-
gene aliza ion labeling desc ibes he dis ibu ion o weigh s when he e is some cons an
le el o in luence el by each playe .
He e, labelings we e conside ed on he edges, e ices, and edges and e ices o a
g aph, as hese ansla e di ec ly o he p ope ies o he game. A magic labeling se ed
as a iable edge labeling,
Σ
- and
Σ′
-labelings as e ex labelings, and a e ex-magic o al
labeling as a labeling on bo h edges and e ices. In all cases, i was possible o ind a
minimum con agious
V0
B
o a su icien ly small
q
in e ms o he labeling. To unde s and
he ex en o which cha ac e iza ion in e ms o a g aph labeling is possible, comple e and
comple e bipa i e g aphs we e used o ix
G
, and he selec ion o
V0
B
was a bi a y. Then
he end beha io o he TPG can be cha ac e ized by bounds on
q
in e ms o he labeling
o G, he opology o G, and V0
B.
The playing o g aphical games using labeled g aphs has no been conside ed p e i-
ously and p esen s a new a enue o explo e he union be ween g aph ea u es and g aphical
game ou come. In p ac ice, magic squa e-gene aliza ion labelings a e a highly egula ed
ep esen a ion o a no malized le el o in luence expe ienced by each playe . Th ough
gene alizing his concep on a social ne wo k, playe s could expe ience a cons an le el
o in luence om ela ionships o o he playe s, bu a pe ec g aph labeling is unlikely
o a ise. This wo k indica es ha such an app oach o a social ne wo k would allow o
he game ou come o be cha ac e ized mo e speci ically han unde gene al weigh ing and
pe haps mo e ealis ically han on a simple g aph. Howe e , he le el o cha ac e iza ion
ha g aph labelings allow o would likely no be possible.
The impac o g aph labels on he game appea s in he upda e ules, whe e playe s
weigh he con ibu ion o each neighbo di e en ly. Howe e , his is me ely a linea
weigh ing, meaning ha de e mining he ou come o he TPG on labeled g aphs has he
same compu a ional complexi y as on unlabeled g aphs.
