Threshold protocol game on graphs with magic square-generalization labelings

Fedrigo, Alexandra Article Threshold protocol game on graphs with magic squaregeneralization labelings Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Fedrigo, Alexandra (2024) : Threshold protocol game on graphs with magic square-generalization labelings, Games, ISSN 2073-4336, MDPI, Basel, Vol. 15, Iss. 6, pp. 1-27, https://doi.org/10.3390/g15060042 This Version is available at: https://hdl.handle.net/10419/330111 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Citation: Fedrigo, A. Threshold Protocol Game on Graphs with Magic Square-Generalization Labelings. Games 2024,15, 42. https://doi.org/ 10.3390/g15060042 Academic Editor: Ulrich Berger Received: 27 September 2024 Revised: 22 November 2024 Accepted: 29 November 2024 Published: 3 December 2024 Copyright: © 2024 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). games Article Threshold Protocol Game on Graphs with Magic Square-Generalization Labelings Alexandra Fedrigo Department of Mathematical Sciences, University of Alabama in Huntsville, 301 Sparkman Drive, Huntsville, AL 35899, USA; [email protected] Abstract: Graphical games describe strategic interactions among a specified network of players. The threshold protocol game is a graphical game that models the adoption of a lesser-used product in a population when individuals benefit by using the same product. The threshold protocol game has historically been considered using infinite, simple graphs. In general, however, players might value some relationships more than others or may have different levels of influence in the graph. These traits are described by weights on graph edges or vertices, respectively. Relative comparisons on arbitrarily weighted graphs have been studied for a variety of graphical games. Alternatively, graph labelings are functions that assign values to the edges and vertices of graphs based on a particular set of rules. This work demonstrates that the outcome of the threshold protocol game can be characterized on a magic square-generalization labeled graph. There are a variety of graph labelings that generalize the concept of magic squares. In each, the labels on similar sets of graph elements sum to a constant. The constant sums of magic square-generalization labelings mean that each player experiences a constant level of influence without needing to specify the value of players relative to one another. The game outcome is compared across different types and features of labelings. Keywords: threshold; coordination; labelings; magic graph; sigma graph; sigma’ graph; vertex-magic total graph 1. Introduction The aim of graphical game theory is to model strategic interactions between players with a specific network of relationships. There is a variety of applications for such systems, from modeling the spread of ideas in a population, to describing social networks, to studying traffic flow in a network of devices. A graph G= (V , E) with vertex set V and edge set E is used to describe the network of players. Each v∈V is a player and uv ∈E if u and v play against each other. The order of G , n=|V| , provides the number of players, and the size of G , e=|E| , represents the number of relationships. The application of both graph and game theoretic tools means that a wide range of questions about graphical games can be addressed. When there are players of greater influence in a graph or players value some relationships more than others, weighted vertices or edges are used to denote the weight placed on an interaction. Discussions of game play on such graphs are necessarily general, since players or relationships may only be compared relative to one another. A strict analysis is usually impossible. Graph labelings, however, are determined using particular rules on a graph, meaning that much more is known about the vertex or edge values in the graph. Labels are precisely defined and do not need to be defined relative to one another. This means that graph labelings can be reasonably expected to allow for more precise characterizations of graphical game outcomes than general weighted graphs. A threshold protocol game (TPG) is a graphical game used to model the adoption of products or ideas in a population. It is primarily applied as an economic model, but the Games 2024,15, 42. https://doi.org/10.3390/g15060042 https://www.mdpi.com/journal/games Games 2024,15, 42 2 of 27 TPG also produces complex dynamics in a graph that can be characterized. In the TPG, players begin in one of two states. The goal of the game is for the minority state to take over the population. The TPG presents a simple game with well-known basic properties, which makes it an ideal framework for studying the effects of labelings on gameplay. Here, attention is paid to outcome of the TPG on magic square-generalization labeled graphs. Such a labeling describes some constant level of influence that all players experience, which may be distributed differently among each player. Sections 2–4provide the preliminaries of the work. Section 2describes the necessary graph labeling background, while Section 3reviews related graphical game theory work as context for this work. Section 4introduces the TPG, and the approach used to analyze the TPG on the labeled graphs is outlined in Section 5. Section 6provides the results of this work on TPGs using labeled graphs, which are discussed in Section 7. Final conclusions and avenues of future work are described in Section 8. 2. Magic Square-Generalizing Graph Labelings Prior to studying the TPG on labeled graphs, the necessary background regarding graph labelings is given. Specifically, the graph labelings that generalize the properties of magic squares are defined. In each labeling, a standard set of graph objects (edges and/or vertices) is specified. The sum of the labels on each such set is a constant. Graph labelings are a widely studied topic in graph theory. A graph labelingis a mapping f:K→Z , where K∈ {V , E , V∪E} or, less commonly, another set of graph features. A mapping f:V→Z is called a vertex labeling, and a mapping f:E→Z is called an edge labeling. There are typically strict rules governing the labels of a graph. Labelings that generalize the principle of magic squares will be used here. The most popular of these is a magic labeling. An injective mapping f:E→Z+ is called a magic labeling of G for constant k if ∑u∈N(v)f(uv) = k for all v∈V , where N(v) = {u∈V:uv ∈E} is the neighborhood of v . The constant k is called the magic constant. A magic graph is a graph that has a magic labeling. A magic labeling is called supermagic if the edge labels are consecutive integers, although typically supermagic refers to a magic labeling using integers 1, 2, . . . , e. Magic graphs get their name as they follow a similar principle to magic squares. Let Km,p= (X , Y) denote a complete bipartite graph where |X|=m , |Y|=p . An m×m magic square can be used to form a Km,m magic graph with magic constant k=m(m2+1) 2 . For example, Figure 1shows how a 3 × 3 magic square is used to produce a supermagic K3,3 [1]. Figure 1. Example of a magic graph of order 6 formed from a 3 ×3 magic square. There is a clear vertex labeling analog to magic labelings. A bijective mapping f: V→ { 1, 2, . . . , n} is called a Σ -labeling of G if, for all v∈V , ∑u∈N(v)f(u) = k for a constant k . A graph with a Σ -labeling is called a Σ -labeled graph and the constant k is called the vertex sum. Σ -labeled graphs are motivated by magic squares, like magic Games 2024,15, 42 3 of 27 graphs, although vertices are labeled rather than edges. Figure 2provides examples of two vertex-labeled graphs with k= 14 and k= 21. Σ -labeled graphs can be constructed using Σ -partitions [ 2 ]. A Σ -partition of { 1, 2, . . . , n} partitions { 1, 2, . . . , n} into m parts such that the sum of each part is k′ . Labeled vertices are grouped according to the Σ -partition into subsets V1, . . . , Vm. Two parts with adjacent vertices form a complete bipartite graph. (a)k=14, r=2 (b)k=21, r=3 Figure 2. Examples of Σ-labeled graphs. A hypergraph is a graph generalization such that an edge may connect any number of vertices. Let each part of a Σ -partition form a vertex of a hypergraph H , so V(H) = {V1 , . . . , Vm} and two vertices in V(H) are adjacent if any of their elements are adjacent in G . That is, if v1 , v2∈V(G) are such that v1∈w1 , v2∈w2 , v1v2∈E(G) , w1 , w2∈V(H) , then w1w2∈E(H) . If H is r -regular, G is a Σ -labeled graph with k=rk′ . Figure 2provides examples with k′=7, and r=2 in Figure 2a and r=3 in Figure 2b. A Σ′ -labeling is similar to a Σ -labeling, but the labels are summed over every closed neighborhood in the graph. N[v] = N(v)∪ {v} denotes the closed neighborhood of v∈V . Then, a Σ′ -labeling is a bijection f:V→ { 1, 2, . . . , n} such that for all v∈V , ∑u∈N[v]f(u) = k , where k is a constant called the vertex sum [ 2 , 3 ]. A graph with a Σ′ - labeling is called a Σ′-graph. There are a few magic square-generalization labelings on graph edges and vertices. A vertex-magic total labeling is a bijection f:V∪E→ { 1, 2, . . . , n+e} such that, for all v∈V , f(v) + ∑u∈N(v)f(uv) = k , where k is a constant called the magic constant. A graph with a vertex-magic total labeling is called a vertex-magic total graph [4,5]. An a-vertex consecutive magic labeling is a vertex-magic total labeling such that the labels on V are {a+ 1, a+ 2, . . . , a+n} for some a∈ { 0, 1, . . . , e} . A graph that has an a-vertex consecutive magic labeling is called a a-vertex consecutive magic graph [ 5 , 6 ]. Games 2024,15, 42 4 of 27 Similarly, a b-edge consecutive magic labeling is a vertex-magic total labeling such that the labels on E are {b+ 1, b+ 2, . . . , b+e} for some b∈ { 0, 1, . . . , n} . A graph that has a b-edge consecutive magic labeling is called a b-edge consecutive magic graph [5,6]. Another type of labeling on vertices and edges is an edge-magic total labeling, which is a bijection f:V∪E→ { 1, 2, . . . , n+e} such that, for all uv ∈E , f(u) + f(v) + f(uv) = k where k is a constant called the magic constant. A graph with an an edge-magic total labeling is called an edge-magic total graph [5,7]. The final graph labeling that will be mentioned here is an H-magic labeling. Let G and H be graphs such that each edge in G is in at least one subgraph isomorphic to H . An H-magic labeling is a bijection f:V∪E→ { 1, 2, . . . , n+e} such that, for all subgraphs G′ of G where G′ is isomorphic to H , ∑v∈V(G′)f(v) + ∑e∈E(G′)f(e) = k [ 5 ].While each of these labelings will be referenced, the TPG will be analyzed on magic, Σ -, Σ′ -, and vertex-magic total graphs. 3. Related Work The TPG is a coordination and consensus graphical game. Here, specifically labeled graphs are considered. Graphical games were introduced in [ 8 ] with the goal of describing a game with a set of players with a specific set of interactions. Defining an n -player graphical game requires a graph G of n vertices, each representing a player, and a set M of n payoff matrices, each associated with a player. A graphical game is then defined as an ordered pair (G,M). The equilibria of graphical games are of primary interest. A population-wide consensus is a strong equilibrium in a coordination game like the TPG. In a population-wide consensus, all players take the same strategy [ 9 ]. When studying consensus, it is often of interest at what rate consensus occurs [ 10 – 18 ] or whether a population can be motivated to reach consensus on a particular state [ 19 ]. There are several well-known graphical game features that influence the rate of consensus, including graph connectivity and the efficiency of a strategy. The focus will be on when consensus occurs for the TPG, since the goal of the game is to obtain a population-wide consensus on the minority state. In order for consensus to be achieved, graphical games are usually repeated, with players’ strategies being updated upon each repetition. Iterations of the game may occur continuously [ 20 ] or at discrete time steps [ 21 ]. With discrete repetitions, players may select updated strategies either synchronously or asynchronously [ 22 – 24 ]. The TPG uses synchronous, discrete updates, and is repeated an infinite number of times. Weighted graphs are useful when players do not value all relationships equally, and are applied to a graphical game in [ 25 – 27 ]. It can also be said that players in a graphical game have weights, which denote the level of influence a particular player exerts on each of its neighbors. This type of weighting is studied in [ 28 – 33 ]. These weightings typically weight graph features relative to one another, while a more uniform weighting can be achieved using graph labelings. Graph labelings occasionally occur in the graphical game theory literature. Where they do, the games are used as a way to generate graph labelings, known as “labeling games.” In these games, two players take turns labeling edges. The winner may be the last player who is able to place a label, players may have competing goals, such as creating or preventing a labeling, etc. There is limited research surrounding such games, but they are studied in [34–40] . There has not been work on the play of graphical games on labeled graphs. Rather than using gameplay to develop labelings, this work examines the impact of labelings on gameplay. The TPG is a threshold game, which is a category of games described in [ 41 ]. In a threshold game, each player v∈V has some weight that must be acted on it to motivate v to change state or to allow v to receive a payoff [ 42 ]. There are many generalizations of threshold games, which are discussed in [ 32 , 43 ]. These include alternative methods of aggregating the payoff v receives from playing against all of its neighbors u∈N(v) [ 19 ], or unique or time-dependent threshold values for each player [ 27 , 42 ]. The TPG is a standard Games 2024,15, 42 5 of 27 threshold game, but these generalizations can be applied based on the application. A simple threshold game (the TPG) is used so that the influence of graph labelings on game play remains clear. 4. Threshold Protocol Game The TPG was introduced in [ 44 ], and was discussed and expanded on in [ 21 , 43 ]. As noted, Ref. [ 43 ] particularly focused on generalizing the game, while Ref. [ 21 ] primarily used the game as an illustrative example of graphical games. In the TPG, players are initially in state A or state B at time t0 . The game is repeated over infinite discrete time steps, and at each step all players simultaneously choose state A or state B . Table 1is the payoff matrix of the TPG stage game, and a player’s expected payoff is based on the aggregate expected payoff of playing the stage game against all u∈N(v) . Let the degree of v∈V be denoted d(v) = |N(v)| . Then, di A(v) , di B(v) denote the number of neighbors of v of state A and state B at time ti , respectively. Vi A , Vi B are the sets of vertices of state A and state B at ti , respectively, and |Vi A|=ni A and |Vi B|=ni B . At time ti+1 , v∈V selects state A if qdi A(v)>( 1 −q)di B(v) and state B if qdi A(v)≤( 1 −q)di B(v) . This update rule is applied as follows: v∈Vselects state Bif q≤di B(v) d(v)and Aotherwise. Table 1. TPG stage game payoff matrix. A B Aq0 B0 1 −q The payoff matrix is determined by parameter q∈( 0, 1 ) to generalize the game, but players are incentivized to agree with their neighbors. In general, the game does not include q= 0 or q= 1, since it may be assumed that if q= 0, all players select B , and if q=1, all players select A. State B begins in the minority, but V0 B is nonempty. The TPG may be played on an infinite or finite graph, so in an infinite graph, n0 B<∞ , and in a finite graph, n0 B<n 2 . The preferred outcome of the TPG is for state B to spread throughout the whole graph. This means there exists a time step ti such that Vi B=V . If this occurs, B is said to be completely contagious in G with respect to q , or just completely contagious when G and q are obvious. An initial set of state B vertices, V0 B , is called contagious in G with respect to q , or just contagious, if Bis completely contagious from V0 B. Historically, the TPG has been studied exclusively on infinite graphs. Here, the use of a TPG will be considered exclusively on finite graphs, since this work seeks to characterize the TPG on connected and labeled (and therefore finite) graphs. Since the TPG is typically used for economic models where each vertex is a member of the population, a finite graph also allows for more accurate modeling. The TPG is deterministic, and the game outcome is determined using the graph G on which the game is played, with the set of vertices initially in state B , V0 B , and the parameter q. A TPG is then defined as an ordered triple (G,V0 B,q). Since the TPG is deterministic for a particular G , V0 B , and q , optimization questions are of greater interest than the outcome of a fixed (G , V0 B , q) . There are two optimization questions of interest in the TPG: 1. What is the smallest contagious V0 B? 2. What is the largest value of q such that B is completely contagious? This value of q is called the contagion threshold and is denoted q∗. Note that it is beneficial to the spread of state B for n0 B to be large and q to be small, but these are often expensive circumstances to implement. Hence, it is desirable for B to be completely contagious from a small V0 Bwith large q. Games 2024,15, 42 6 of 27 An example of TPG play is given in Figure 3. Player 1 has one neighbor, which is initially of state B . This means player 1 expects a payoff of zero from playing A and a payoff of 1 −q=2 3 from playing B . Player 2 has four neighbors, two of which are initially of state A and two of which are initially of state B . Thus, player 2 expects a payoff of 1 3+1 3=2 3 from playing state A and a payoff of 2 3+2 3=4 3 from playing state B . The graph and initial states are symmetric, so all players of state A are in the same situation as player 1, and all players of state B are in the same situation as player 2. All players prefer state B to state A , so Bis completely contagious after one time step. Figure 3. Example of TPG play on an unlabeled, finite graph with q=1 3. The existence of a contagious V0 B for a particular value of q has been the focus of previous work, with play occurring on infinite, connected, undirected, simple graphs. The graphs considered here differ only in that they are labeled and finite. Long-term game dynamics in a population are the focus of this work. Exceptions can arise when the number of players is small. However, the dynamics of the game using a small population are not generally of interest, either in theory or application. For these reasons, assume n≥ 5. All interactions are two-way and a player does not play against themselves, so G is assumed to be undirected and does not have loops. It does not make sense to study the spread of states on a disconnected graph, so assume Gis connected. 5. Method for Analyzing End Behavior of the Threshold Protocol Game on Labeled Graphs In order to compare the influence of different types of labelings on the outcome of the TPG, the game is played on graphs with labelings that generalize magic squares. Such labelings also have the clearest interpretation within the game, and are thus a clear starting place. Several of the most direct generalizations are applied. The edge labeling that is considered is a magic labeling. Σ - and Σ′ -labelings are vertex labelings that are both used, since these labelings are supported by different graph topologies. Finally, vertexmagic total labeling is used as a labeling on edges and vertices. Complete, complete bipartite, and similar graphs are examined for each labeling as appropriate. The fixed graph topologies are exploited to characterize the possible outcomes of the TPG played on the labeled graphs. Existing results regarding the topological features of graphs with certain labelings are used to determine “appropriately similar”. The circumstances under which B is completely contagious are of primary interest, but of secondary interest is the long-term behavior of the game. Say that v∈V has static end behavior if there exists tj such that, for all i≥j , v does not change state at ti . Then, v has static A end behavior if v∈Vi A and static B end behavior if v∈Vi B . Alternatively, v has 2-periodic end behavior if there exists tj such that, for i= 0, 1, . . . , v∈Vj+2i A and v∈Vj+2i+1 B , meaning v alternates states. The end behavior is a vertex property, but the end behavior of all vertices being static A is equivalent to A being completely contagious in G , and all vertices having a static B end behavior is equivalent to B being completely contagious in G. Games 2024,15, 42 7 of 27 Along with the graph features, the threshold value q is key to determining the end behavior of the TPG in any graph and q∗ may change based on the graph labeling. Thus, the majority of determinations regarding the TPG end behavior are dependent on these components. Often, a bound on the value of q is selected to motivate B to be completely contagious. Here, a low, obvious bound on q is provided to first find a minimum-sized contagious V0 B . When V0 B or G are chosen carefully, a higher upper bound on q can be provided such that B is completely contagious. Where possible, this value is contrasted with a lower bound on q such that A is completely contagious, or with bounds that will allow for an alternative end behavior to occur. Clearly, each bound is applicable only if it is in ( 0, 1 ) . G is fixed with a simple topology, such as a complete or complete bipartite graph. Then, bounds on q that cause a particular end behavior to occur are provided for an arbitrary V0 B in terms of V0 B and the graph labeling. Details regarding the approaches used for each graph labeling are discussed in the corresponding section. 6. Results The outcome of the TPG is considered using magic graphs, Σ -graphs, Σ′ -graphs, and vertex-magic total graphs. For each labeling, a completely contagious V0 B can be identified for a sufficiently small q . It is also shown that, for each labeling, a characterization of the TPG outcomes is possible on complete and complete bipartite graphs in terms of the graph labeling. Some labelings have additional features that can be exploited to draw further conclusions about TPG behavior when using the labeled graphs. 6.1. Threshold Protocol Game on Magic Graphs Let G be a weighted graph with λuv denoting the weight of uv ∈E . When the TPG is played on a weighted graph, v∈V will take state B at ti+1 if q∑u∈Ni A(v)λuv ≤ (1−q)∑u∈Ni B(v)λuv, or q≤ ∑u∈Ni B(v)λuv ∑u∈N(v)λuv , and Aotherwise. The definitions of graph labelings mean that there are very specific rules governing a graph labeling. Taking edge labels as edge weights, the TPG can be played on the resulting weighted graph. In the case of magic graphs, v∈V will take state B at ti+1 if q≤ ∑u∈Ni B(v)λuv ∑u∈N(v)λuv = ∑u∈Ni B(v)λuv k , and A otherwise. An example of TPG play on a magic graph is provided in Figure 4. The magic graph has k= 15 and six players, two of whom begin in state B. Then, with q=1 15 ,Bis completely contagious after one time step. Figure 4. Example of TPG play on a magic graph with q=1 15 and k=15. It is first shown that, for small enough q, there exists a contagious V0 Bfor all G. Theorem 1. Let G be a magic graph with magic constant k . Let m=min{λuv :uv ∈E} and q≤m k. (a) If G is non-bipartite, B is completely contagious for V0 B={v}for all v ∈V. (b) If G= (X , Y) is bipartite, with partite sets X and Y , B is completely contagious for V0 B={v1,v2}for all v1∈X, v2∈Y. Games 2024,15, 42 8 of 27 Proof. Note that for all v∈V , q≤m k≤∑uv∈Fλuv kfor all F⊆E . Thus, if v∈N(Vi B) , then v∈Vi+1 B. (a) Suppose G is non-bipartite and n0 B= 1. Note the common result that states that a graph is non-bipartite if and only if it contains an odd cycle. Let C be an odd cycle in G . Since G is connected and v∈Vi+1 B if v∈N(Vi B) , there exists i1 such that there exists v∈C , such that v∈Vi1 B . Clearly, |C∩Vi1 B|> 1 is more contagious in C than |C∩Vi1 B|= 1, so consider the worst-case scenario |C∩Vi1 B|= 1. Since C is an odd cycle, there exists i2>i1 such that v1 , v2∈C , v1 , v2∈Vi2 B , and v1∼v2 . For all i≥i2 , v1 , v2∈Vi B . Then, for all k∈N , N(k)({v1 , v2})⊆Vi2+k B , where N(k)({v1 , v2}) = N(N(. . . N({v1 , v2}). . . )) . Since G is connected, there exists k′ such that N(k′)({v1,v2}) = V. Hence, B is completely contagious in G. (b) Suppose G is bipartite and V0 B={v1 , v2} with v1∈X , v2∈Y . Note that for all k∈N , N(k)(v1)⊆Vk B and N(k)(v2)⊆Vk B . Since G is connected, there exists k′ such that N(k′)(v1) = X and N(k′)(v2) = Y . Then, Vk′ B=X∪Y=V , so B is completely contagious in G. Since n≥ 5, V0 B in Theorem 1is a minority in G , q∗≥min{λuv:uv∈E} k in a magic graph. This theorem describes a best-case scenario for n0 B but a worst-case scenario for q in terms of the optimization questions posed above. By more carefully selecting V0 B and G , the bound on qcan be improved. Complete and complete bipartite graphs describe a fully regular graph topology; thus, the play of the TPG on magic complete and complete bipartite graphs allows for the influence of the graph labeling on game outcome to be clearly considered. Let e′=|{uv ∈ E:v∈V0 B}| =∑n0 B i=1(n−i) = n0 B(2n−n0 B−1) 2 denote the number of edges with at least one vertex in V0 B . Let {λuv1 , λuv2 , . . . , λuve′}={λuv :v∈V0 B} such that λuv1<λuv2<· · · < λuve′. Finally, let m=∑n0 B−1 i=1λuvi,M=∑e′ i=e′−n0 B λuvi. Theorem 2. Let Knbe a complete magic graph. (a) If n0 B=1, with V0 B={v}, and q ≤min{λuv:u∈N(v)} k, then B is completely contagious. (b) If n0 B>1, and q ≤m k, then B is completely contagious. (c) If q >M k, then A is completely contagious. Proof. Let Knbe a complete magic graph. (a) Suppose n0 B= 1, with V0 B={v} , and q≤min{λuv:u∈N(v)} k . Since N(v) = V0 A , v∈V1 A . For u∈V0 A , ∑w∈N0 B(u)λuw k=λuv k>min{λuv:u∈N(v)} k≥q , so u∈V1 B . Then V1 A={v} , so N(v) = V1 B , and v∈V2 B . For all u∈V1 B , ∑w∈N0 B(u)λuw k=k−λuv k≥min{λuv:u∈N(v)} k≥q since n≥5, so u∈V2 B. Thus, Bis completely contagious after two time steps. (b) Suppose n0 B> 1, and q≤m k . For v∈V0 B , ∑u∈N0 B(v)λuv k= ∑u∈V0 B\{v}λuv k≥m k≥q , so v∈V1 B . For v∈V0 A , ∑u∈N0 B(v)λuv k= ∑u∈V0 B λuv k≥m k>q , so v∈V1 B . Thus, V1 B=V , and Bis completely contagious after one time step. (c) Suppose q>M k , M<k . For v∈V0 B , ∑u∈N0 B(v)λuv k= ∑u∈V0 B\{v}λuv k≤M k<q , so v∈V1 A . For v∈V0 A , ∑u∈N0 B(v)λuv k= ∑u∈V0 B λuv k≤M k<q , so v∈V1 A . Thus, V1 A=V , and A is completely contagious after one time step. Games 2024,15, 42 15 of 27 Figure 8. Example of TPG play on a Σ′-graph with q=1 14 and k=15. As previously, first consider the bound on q for the minimum contagious V0 B in a Σ′ - labeled graph. Theorem 8. Let G be a Σ-labeled graph with vertex sum k. Let q ≤1 k−1. (a) If G is non-bipartite, B is completely contagious for V0 B={v}for all v ∈V. (b) If G= (X , Y) is bipartite, B is completely contagious for V0 B={v1 , v2} for all v1∈X , v2∈Y. Proof. Note that q≤1 k−1≤∑v∈Wλv k−1≤∑v∈Wλv k−λvfor all W⊆V , v∈V . Thus, if v∈N(Vi B) , then v∈Vi+1 B, so the proofs of (a)and (b)are the same as in the proof of Theorem 1. Theorem 8indicates that q∗≥1 k−1 in a Σ′ -labeled graph. Theorem 13 in Ref. [ 3 ] states that a complete m -partite graph Kp1,p2,...,pm is a Σ′ -labeled graph, if and only if, pi= 1 for all i= 1, 2, . . . , m , i.e., if Kp1,p2,...,pm=Kn . Clearly, on Kn , k=n(n+1) 2 . Consider the TPG on aΣ′-labeled Kn. Theorem 9. Let Knbe a Σ′-labeled complete graph. (a) If n0 B=1such that V0 B={v}, then B is completely contagious in G if q ≤λv k−1. (b) If n0 B> 1, then B is completely contagious in G if q≤ ∑u∈V0 B λu−m k−1 , where m=max{λv: v∈V0 B}. (c) A is completely contagious in G if q > ∑u∈V0 B λu k−n. Proof. (a) Suppose n0 B= 1 with V0 B={v} . Then, v∈V1 A since N(v) = V0 A . For w∈V0 A , ∑u∈N0 B(w)λu k−λw =λv k−λw ≥λv k−1 ≥q Games 2024,15, 42 16 of 27 so w∈V1 B and V0 A=V1 B . Consider V1 A={v} . Then, for v , N(v) = V1 B , so v∈V2 B . For all w∈V1 B, ∑u∈N0 B(w)λu k−λw =∑u∈V\{v,w}λu k−λw =k−λv−λw k−λw ≥k−λv−λw k−1 ≥λv k−1since n≥5 ≥q so w∈V2 B . Thus, V2 B=V , and B is completely contagious in Kn after two time steps. (b) Suppose n0 B>1, and let m=max{λv:v∈V0 B}. Let q≤ ∑u∈V0 B λu−m k−1. For all v∈V0 A, ∑u∈N0 B(v)λu k−λv = ∑u∈V0 B λu k−λv ≥ ∑u∈V0 B λu k−1 > ∑u∈V0 B λu−m k−1 ≥q so v∈V1 Band V0 B⊆V1 B. For all v∈V0 B, ∑u∈N0 B(v)λu k−λv = ∑u∈V0 B\{v}λu k−λv = ∑u∈V0 B λu−λv k−λv ≥ ∑u∈V0 B λu−m k−1 ≥q so v∈V1 B and V0 A⊆V1 B . Thus, V1 B=V , and B is completely contagious after one time step. (c) Let q> ∑u∈V0 B λu k−n. For all v∈V0 A, ∑u∈N0 B(v)λu k−λv = ∑u∈V0 B λu k−λv ≤ ∑u∈V0 B λu k−n <q Games 2024,15, 42 17 of 27 so v∈V1 Aand V0 B⊆V1 A. For all v∈V0 B, ∑u∈N0 B(v)λu k−λv = ∑u∈V0 B\{v}λu k−λv = ∑u∈V0 B λu−λv k−λv < ∑u∈V0 B λu k−n <q so v∈V1 A and V0 A⊆V1 A . Thus, V1 A=V , and A is completely contagious in one time step. Since the magic constant is determined by the sum over each closed neighborhood, the results for the Σ′ -labeled graphs are less conclusive than those of Σ -labeled graphs. However, these two labelings are also supported by different graph topologies. For example, there does not exist a Σ -labeled complete graph, while the only m -partite Σ′ -labeled graphs that exist are complete. 6.4. Threshold Protocol Game on Vertex-Magic Total Graphs So far, the TPG on graphs with edge or vertex labelings has been considered. The final common type of graph labeling is on the vertices and edges of G . When the TPG is played using a graph with vertex and edge labels, v∈V takes state B in ti+1 if q∑u∈Ni A(v)(λu+ λuv)≤( 1 −q)∑u∈Ni B(v)(λu+λuv) , or q≤ ∑u∈Ni B(v)(λu+λuv) ∑u∈N(v)(λu+λuv) , and A otherwise. Then, on a vertex-magic total graph, v∈V takes state B in ti+1 if q≤ ∑u∈Ni B(v)(λu+λuv) ∑u∈N(v)(λu+λuv)= ∑u∈Ni B(v)(λu+λuv) (k−λv)+∑u∈N(v)λu , and A otherwise. An example of TPG play with a vertex-magic total graph is presented in Figure 9. This is a particularly nice vertex-magic total graph as it is also a 0-edge consecutive magic graph and 4-vertex consecutive magic graph. The vertexmagic total graph has k= 11 and five players, two of whom begin in state B . Then, with q=1 4,Bis completely contagious after two time steps. Figure 9. Example of TPG play on a vertex-magic total graph with q=1 4and k=11. Consider a minimum contagious V0 Bfor a small q. Theorem 10. Let G be a vertex-magic total graph with magic constant k . Denote the maximum degree of G using ∆and m =min{λu+λuv :uv ∈E}. Let q ≤m k−1+∆(n+e). (a) If G is non-bipartite, B is completely contagious for V0 B={v}for all v ∈V. Games 2024,15, 42 18 of 27 (b) If G= (X , Y) is bipartite, B is completely contagious for V0 B={v1 , v2} for all v1∈X , v2∈Y. Proof. Note that for all v∈V , q≤m k−1+∆(n+e)< λv′+λvv′ (k−λv)+∑u∈N(v)λu , such that vv′∈E . Thus, if v∈N(Vi B) , then v∈Vi+1 B , so the proof of (a) and (b) are the same as in the proof of Theorem 1. Since n≥ 5, Theorem 10 indicates that q∗≥min{λu+λuv:uv∈E} k−1+∆(n+e) in a vertex-magic total graph. In Ref. [ 47 ], it is proved that there exists a vertex-magic total Kn for all n≡ 0 (mod 4 ) . Thus, there exist vertex-magic total complete graphs and the TPG can be considered on vertex-magic total complete graphs. Theorem 11. Let Knbe a vertex-magic total complete graph. Let K=∑u∈Vλu. (a) If n0 B=1with V0 B={v}, then B is completely contagious if q ≤min{λu+λuw:uw∈E}) k−2+K (b) If n0 B> 1, then B is completely contagious if q≤ ∑u∈V0 B (λu+min{λuv:v∈N(u)})−max{λu:u∈V0 B} k−2+K (c) A is completely contagious if q > ∑u∈V0 B (λu+max{λuv:v∈N(u)}) k−2 max{λu:u∈V}+K Proof. (a) Suppose n0 B= 1, V0 B={v} , and q≤min{λu+λuv:uv∈E}) k−2+K . For v such that V0 B={v},N(v) = V0 A, so v∈V1 A. For w∈V0 A, ∑u∈N0 B(w)(λu+λuw) k−λw+∑u∈N(w)λu =λv+λwv 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={v} . Thus, N(v) = V1 B , so v∈V2 B . For all w∈V1 B, ∑u∈N0 B(w)(λu+λuw) k−λw+∑u∈N(w)λu =∑u∈V(λu+λuw)−(λv+λwv)−λ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 completely contagious after two time steps. (b) Suppose n0 B>1 and q≤ ∑u∈V0 B (λu+min{λuv:v∈N(u)})−max{λu:u∈V0 B} k−2+K. For all v∈V0 A, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu = ∑u∈V0 B(λu+λuv) k−2λv+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 of 27 so v∈V1 Band V0 A⊆V1 B. For all v∈V0 B, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu =∑u∈V0 B(λu+λuv)−λv k−2λv+K ≥∑u∈V0 B(λu+λuv)−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 v∈V1 B and V0 B⊆V1 B . Thus, V1 B=V , so B is completely contagious after one time step. (c) Suppose n0 B>1 and q> ∑u∈V0 B (λu+max{λuv:v∈N(u)}) k−2 max{λu:u∈V}+K. For all v∈V0 A, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu = ∑u∈V0 B(λu+λuv) k−2λv+K ≤ ∑u∈V0 B(λu+max{λuw :w∈N(u)}) k−2 max{λu:u∈V}+K <q so v∈V1 Aand V0 A⊆V1 A. For all v∈V0 B, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu =∑u∈V0 B(λu+λuv)−λv k−2λv+K ≤∑u∈V0 B(λu+max{λuw :w∈N(u)})−λv 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 v∈V1 A and V0 A⊆V1 A . Thus, V1 A=V , and A is completely contagious after one time step. Along with the results obtained for vertex-magic total complete graphs, Ref. [ 47 ] contains a proof that Kp,p is the vertex-magic total for all p> 1. In a refinement of this result, Ref. [ 4 ] concludes that Km,p is not vertex-magic total if |m−p|> 1. That said, there exists a vertex-magic total Km,pon which the TPG can be considered. Theorem 12. Let Km,p= (X , Y) be a vertex-magic total complete bipartite graph. Let X= ∑u∈Xλuand Y=∑u∈Yλu. (a) B is completely contagious if q≤min{ ∑u∈V0 B∩X(λu+min{λuv :v∈N(u)}) k−min{λv:v∈Y}+X, ∑u∈V0 B∩Y(λu+min{λuv :v∈N(u)}) k−min{λv:v∈X}+Y}. (b) A is completely contagious if q>max{ ∑u∈V0 B∩X(λu+max{λuv :v∈N(u)}) k−max{λv:v∈Y}+X, ∑u∈V0 B∩Y(λu+max{λuv :v∈N(u)}) k−max{λv:v∈X}+Y}. (c) The end behavior on Km,pis 2-periodic if Games 2024,15, 42 20 of 27 ∑u∈V0 B∩Y(λu+max{λuv :v∈N(u)}) k−max{λv:v∈X}+Y}<q≤ ∑u∈V0 B∩X(λu+min{λuv :v∈N(u)}) k−min{λv:v∈Y}+X or ∑u∈V0 B∩X(λu+max{λuv :v∈N(u)}) k−max{λv:v∈Y}+X<q≤ ∑u∈V0 B∩Y(λu+min{λuv :v∈N(u)}) k−min{λv:v∈X}+Y}. Proof. (a) Suppose q≤min{ ∑u∈V0 B∩X(λu+min{λuv :v∈N(u)}) k−min{λv:v∈Y}+X, ∑u∈V0 B∩Y(λu+min{λuv :v∈N(u)}) k−min{λv:v∈X}+Y}. Then, for all v∈X, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu = ∑u∈V0 B∩Y(λu+λuv) k−λv+Y ≥ ∑u∈V0 B∩Y(λu+min{λuw :w∈N(u)}) k−min{λw:w∈X}+Y ≥q so v∈V1 B. For all v∈Y, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu = ∑u∈V0 B∩X(λu+λuv) k−λv+X ≥ ∑u∈V0 B∩X(λu+min{λuw :w∈N(u)}) k−min{λw:w∈Y}+X ≥q so v∈V1 B. Thus, V1 B=V, and Bis completely contagious after one time step. (b) Suppose q>max{ ∑u∈V0 B∩X(λu+max{λuv :v∈N(u)}) k−max{λv:v∈Y}+X, ∑u∈V0 B∩Y(λu+max{λuv :v∈N(u)}) k−max{λv:v∈X}+Y}. Then, for all v∈X, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu = ∑u∈V0 B∩Y(λu+λuv) k−λv+Y ≤ ∑u∈V0 B∩Y(λu+max{λuw :w∈N(u)}) k−max{λw:w∈X}+Y <q so v∈V1 A. For all v∈Y, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu = ∑u∈V0 B∩X(λu+λuv) k−λv+X ≤ ∑u∈V0 B∩X(λu+max{λuw :w∈N(u)}) k−max{λw:w∈Y}+X <q so v∈V1 A. Thus, V1 A=V, and Ais completely contagious after one time step. Games 2024,15, 42 21 of 27 (c) Suppose ∑u∈V0 B∩Y(λu+max{λuv :v∈N(u)}) k−max{λv:v∈X}+Y}<q≤ ∑u∈V0 B∩X(λu+min{λuv :v∈N(u)}) k−min{λv:v∈Y}+X. Then, for all v∈X, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu = ∑u∈V0 B∩Y(λu+λuv) k−λv+Y ≤ ∑u∈V0 B∩Y(λu+max{λuw :w∈N(u)}) k−max{λw:w∈X}+Y <q so v∈V1 A. For all v∈Y, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu = ∑u∈V0 B∩X(λu+λuv) k−λv+X ≥ ∑u∈V0 B∩X(λu+min{λuw :w∈N(u)}) k−min{λw:w∈Y}+X ≥q so v∈V1 B . Hence, X=V1 A and Y=V1 B . For all v∈X , N(v) = V1 B , and for all v∈Y , N(v) = V1 B . Iterating, X=V2i−1 B and Y=V2i−1 A , while X=V2i A and Y=V2i B , i=1, 2, . . . . Thus, the end behavior of the TPG is 2-periodic. Alternatively, suppose ∑u∈V0 B∩X(λu+max{λuv :v∈N(u)}) k−max{λv:v∈Y}+X<q≤ ∑u∈V0 B∩Y(λu+min{λuv :v∈N(u)}) k−min{λv:v∈X}+Y}. Then, for all v∈X, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu = ∑u∈V0 B∩Y(λu+λuv) k−λv+Y ≥ ∑u∈V0 B∩Y(λu+min{λuw :w∈N(u)}) k−min{λw:w∈X}+Y ≥q so v∈V1 B. For all v∈Y, ∑u∈N0 B(v)(λu+λuv) k−λv+∑u∈N(v)λu = ∑u∈V0 B∩X(λu+λuv) k−λv+X ≤ ∑u∈V0 B∩X(λu+max{λuw :w∈N(u)}) k−max{λw:w∈Y}+X <q so v∈V1 A . Hence, X=V1 B and Y=V1 A . For all v∈X , N(v) = V1 A , and for all v∈Y , N(v) = V1 A . Iterating, X=V2i−1 A and Y=V2i−1 B , while X=V2i B and Y=V2i A , i=1, 2, . . . . Thus, the end behavior of the TPG is 2-periodic. The analysis of a TPG using vertex-magic total graphs is unique in this work because of the influence of labels on both the edges and vertices of G. That said, results analogous Games 2024,15, 42 22 of 27 to those found for edge labelings and vertex labelings are achievable, although complete characterization is not possible for an arbitrary V0 B. 6.5. Equivalent and near Equivalent Labelings There are several other magic square-generalization labelings on the edges and vertices of graphs that should be mentioned. However, TPG gameplay on graphs with these labelings is equivalent to systems already discussed, so they will not be studied independently . 6.5.1. Threshold Protocol Game on a-Vertex Consecutive and b-Edge Consecutive Magic Graphs An a-vertex consecutive magic labeling is a type of vertex-magic total labeling. Thus, results obtained for vertex-magic total graphs can be refined on a-vertex consecutive magic graphs, and Theorems 10 and 11 can be restated in terms of a-vertex consecutive magic graphs. Note that particular vertex labels referenced in Theorem 12 cannot be further specified, so the results are not refined on a-vertex consecutive magic graphs. Theorem 13. Let G be an a-vertex consecutive magic graph with magic constant k . Let m= min{λu+λuv :uv ∈E}and q ≤m k−a−1+∆(a+n). (a) If G is non-bipartite, B is completely contagious for V0 B={v}for all v ∈V. (b) If G= (X , Y) is bipartite, B is completely contagious for V0 B={v1 , v2} for all v1∈X , v2∈Y. Theorem 14. Let Knbe an a-vertex consecutive magic graph. Let K=∑u∈Vλu=n(2a+n+1) 2. (a) If n0 B=1with V0 B={w}, then B is completely contagious if q ≤min{λu+λuv:uv∈E}) k−2(a+1)+K. (b) If n0 B> 1, then B is completely contagious if q≤ ∑u∈V0 B (λu+min{λuv:v∈N(u)})−max{λu:u∈V0 B} k−2(a+1)+K . (c) If n0 B>1then A is completely contagious if q > ∑u∈V0 B (λu+max{λuv:v∈N(u)}) k−2(a+n)+K. b-edge consecutive magic labelings are also a type of vertex-magic total labeling. Thus, results for vertex-magic total graphs also apply to b-edge consecutive magic graphs. However, Theorems 10–12 do not rely on the use of particular possible edge labels, so the results cannot be refined using b-edge consecutive magic graphs. 6.5.2. Threshold Protocol Game on Edge-Magic Total Graphs Consider the play of a TPG on an edge-magic total graph. Since an edge-magic total labeling is a labeling on both the vertices and edges of G , a vertex v∈V takes state B at ti+1if q≤ ∑u∈Ni B(v)(λu+λuv) ∑u∈N(v)(λu+λuv), which can be refined on an edge-magic total graph as q≤ ∑u∈Ni B(v)(λu+λuv) ∑u∈N(v)(λu+λuv) =di B(v)(k−λv) d(v)(k−λv) =di B(v) d(v). Thus, the threshold of the TPG in an edge-magic total graph is the same as the threshold in a simple graph, which means that vertices update states as in the classic TPG. Hence, the play of the TPG is equivalent between edge-magic total graphs and unlabeled graphs. Games 2024,15, 42 23 of 27 7. Discussion The update rule of the classic TPG states that v∈V takes state B at ti+1 if q≤di B(v) d(v) and A otherwise. On a labeled graph, the update rule changes based on the type of labeling. In an edge labeled graph, v takes state B if q≤ ∑u∈Ni B(v)λuv ∑u∈N(v)λuv , in a vertex labeled graph if q≤ ∑u∈Ni B(v)λu ∑u∈N(v)λu , and in a graph with vertex and edge labels if q≤ ∑u∈Ni B(v)(λu+λuv) ∑u∈N(v)(λu+λuv) . There may be restrictions on graph topology based on the labelings used, but properties of the TPG that do not depend on qhold regardless of labeling. Unlike randomly weighted graphs or arbitrary influence graphs, a graph labeling provides a fully specified scheme of the weights and/or influence values. This work demonstrates that the outcome of the TPG may be characterized in terms of a graph labeling with a few caveats. Since a-vertex consecutive and b-edge consecutive magic labelings are examples of vertex-magic total labelings, they will not currently be considered separately. There are four labelings of primary interest. A magic labeling is an edge labeling, Σ - and Σ′ -labelings are vertex labelings, and a vertex-magic total labeling is a labeling on both vertices and edges, but all follow a similar principle in which the labels of some subsets of elements sum to a constant. Two types of results are provided for each labeling. First, a low (worst-case) bound on q is provided, which allows for a minimum V0 B to be contagious in an arbitrary G , where restrictions on V0 B are determined only by whether G is non-bipartite or bipartite. This V0 B is advantageous because it requires no particular selection of vertices when G is non-bipartite, and requires only that a vertex is selected from each partite set when G is bipartite. A version of this result is achievable for all the labelings considered here. Hence, for each of these four labelings, there exist completely contagious V0 B ’s, and a lower bound on q∗ is provided by Theorem 1on magic graphs, Theorem 5on Σ -labeled graphs, Theorem 8on Σ′ -labeled graphs, and Theorem 10 on vertex-magic total graphs. A similar result can be achieved for Σ -labeled graphs in terms of Σ -partition hypergraphs, which is shown in Theorem 6. Second, a characterization is provided of variations on complete and complete bipartite graphs, as appropriate. It is typical to consider strongly regular magic graphs, which include complete and complete bipartite graphs. Theorem 4and Corollary 1describe a better bound on q than Theorem 1for a similar n0 B , but some care must be taken in selecting V0 B . Additionally, since they depend on G being strongly regular, these results do not hold on all magic graphs. Corollary 2generalizes the maximum spanning tree approach to all magic graphs, with n0 B= 2. This result provides a same or slightly worse n0 B than Theorem 1, but the bound on q may be better. That said, there are also restrictions on V0 B , making the result of Corollary 2more restrictive than that of Theorem 1. While the main goal of the TPG is to motivate B to be completely contagious, there are sets of parameters for which B will not be completely contagious. G , V0 B , and q each play a key role in the end behavior the TPG will exhibit. To study the influence of labelings on game outcome, which impact feasible bounds on q , G is fixed as a complete or complete bipartite graph, and V0 B is arbitrary. Theorems 2and 3characterize the end behavior of a TPG on magic complete and complete bipartite graphs. There are no Σ -labeled complete graphs, but Theorem 7characterizes the play of the TPG on Σ -labeled complete bipartite graphs. In contrast, the other vertex labeled graphs that were considered, Σ′ - labeled graphs, do not exist for complete bipartite graphs, but do exist for complete graphs. Thus, Theorem 9characterizes the play of the TPG on Σ′ -labeled complete graphs. Theorems 11 and 12 describe the outcomes of the TPG when using vertex-magic total complete and complete bipartite graphs, respectively. The bounds on q in these results are ideal, since they are provided in terms of V0 B and the graph labeling, which are parts of the game definition. For all complete labeled graphs, an upper bound can be found on q such that B is completely contagious and a lower bound can be found on q such that A is completely contagious. This is also true of complete bipartite graphs, although there Games 2024,15, 42 24 of 27 may also exist an interval I⊆( 0, 1 ) such that q∈I causes a 2-periodic end behavior in the TPG. Note, however, that these statements hold provided the bound(s) fall in ( 0, 1 ) . While general characterizations are provided, the only labeling considered here for which the characterization on Kn or Km,p is complete is the Σ -labeling. A complete characterization of the other labelings would depend on each vertex in V0 B , which is neither feasible nor general enough to be of interest. There are a few additional comparisons that can be drawn between the labelings based on these results. First, the labeling on the edges and vertices of a graph results in the most complex update rule for the TPG. The update rules for edge and vertex labelings are similar in terms of complexity. This suggests that when considering other labelings, characterizations of graphs with labeled vertices and edges may not be possible to the extent that characterizations on graphs with vertex labelings or edge labelings can be found. However, in the magic-square generalization labelings considered in this work, the type of labeling is not the primary factor in the level of characterization that can be achieved. Note that the constant sum at each v∈V is independent of λv for magic and Σ -graphs, but dependent on λv for Σ′ - and vertex-magic total graphs. Stronger and more varied characterizations of the TPG are possible when using magic and Σ -graphs than Σ′ - and vertex-magic total graphs, since the analysis is simplified for these labelings. 8. Conclusions The TPG is a valuable and simple economic model with interesting dynamics. The primary aim of the TPG is to study the circumstances under which a state that begins in the minority will overtake the population. Historically, this game has been studied using unweighted graphs and unlabeled players. This means that the outcome of the TPG is studied when all players and the relationships between them have equal value in the game. In contrast, playing the game with a labeled graph requires accounting for the particular scheme of values applied to each player and/or relationship. A magic squaregeneralization labeling describes the distribution of weights when there is some constant level of influence felt by each player. Here, labelings were considered on the edges, vertices, and edges and vertices of a graph, as these translate directly to the properties of the game. A magic labeling served as a viable edge labeling, Σ - and Σ′ -labelings as vertex labelings, and a vertex-magic total labeling as a labeling on both edges and vertices. In all cases, it was possible to find a minimum contagious V0 B for a sufficiently small q in terms of the labeling. To understand the extent to which characterization in terms of a graph labeling is possible, complete and complete bipartite graphs were used to fix G , and the selection of V0 B was arbitrary. Then the end behavior of the TPG can be characterized by bounds on q in terms of the labeling of G, the topology of G, and V0 B. The playing of graphical games using labeled graphs has not been considered previously and presents a new avenue to explore the union between graph features and graphical game outcome. In practice, magic square-generalization labelings are a highly regulated representation of a normalized level of influence experienced by each player. Through generalizing this concept on a social network, players could experience a constant level of influence from relationships or other players, but a perfect graph labeling is unlikely to arise. This work indicates that such an approach to a social network would allow for the game outcome to be characterized more specifically than under general weighting and perhaps more realistically than on a simple graph. However, the level of characterization that graph labelings allow for would likely not be possible. The impact of graph labels on the game appears in the update rules, where players weight the contribution of each neighbor differently. However, this is merely a linear weighting, meaning that determining the outcome of the TPG on labeled graphs has the same computational complexity as on unlabeled graphs.