Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn dynamic monopolies of graphs: the average and strict majority thresholds
209
0
0.0
(
0
)
Added by
Manouchehr Zaker
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $G$ be a graph and ${mathcal{tau}}: V(G)rightarrow Bbb{N}cup {0}$ be an assignment of thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a dynamic monopoly corresponding to $(G, tau)$ if the vertices of $G$ can be partitioned into subsets $D_0, D_1,..., D_k$ such that $D_0=D$ and for any $iin {0, ..., k-1}$, each vertex $v$ in $D_{i+1}$ has at least $tau(v)$ neighbors in $D_0cup ... cup D_i$. Dynamic monopolies are in fact modeling the irreversible spread of influence in social networks. In this paper we first obtain a lower bound for the smallest size of any dynamic monopoly in terms of the average threshold and the order of graph. Also we obtain an upper bound in terms of the minimum vertex cover of graphs. Then we derive the upper bound $|G|/2$ for the smallest size of any dynamic monopoly when the graph $G$ contains at least one odd vertex, where the threshold of any vertex $v$ is set as $lceil (deg(v)+1)/2 rceil$ (i.e. strict majority threshold). This bound improves the best known bound for strict majority threshold. We show that the latter bound can be achieved by a polynomial time algorithm. We also show that $alpha(G)+1$ is an upper bound for the size of strict majority dynamic monopoly, where $alpha(G)$ stands for the matching number of $G$. Finally, we obtain a basic upper bound for the smallest size of any dynamic monopoly, in terms of the average threshold and vertex degrees. Using this bound we derive some other upper bounds.
rate research
Read More
Let $G$ be a graph and $tau$ be an assignment of nonnegative integer thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a $tau$-dynamic monopoly, if $V(G)$ can be partitioned into subsets $D_0, D_1, ldots, D_k$ such that $D_0=D$ and for any $iin {0, ldots, k-1}$, each vertex $v$ in $D_{i+1}$ has at least $tau(v)$ neighbors in $D_0cup ldots cup D_i$. Denote the size of smallest $tau$-dynamic monopoly by $dyn_{tau}(G)$ and the average of thresholds in $tau$ by $overline{tau}$. We show that the values of $dyn_{tau}(G)$ over all assignments $tau$ with the same average threshold is a continuous set of integers. For any positive number $t$, denote the maximum $dyn_{tau}(G)$ taken over all threshold assignments $tau$ with $overline{tau}leq t$, by $Ldyn_t(G)$. In fact, $Ldyn_t(G)$ shows the worst-case value of a dynamic monopoly when the average threshold is a given number $t$. We investigate under what conditions on $t$, there exists an upper bound for $Ldyn_{t}(G)$ of the form $c|G|$, where $c<1$. Next, we show that $Ldyn_t(G)$ is coNP-hard for planar graphs but has polynomial-time solution for forests.
Let $G$ be a directed graph such that the in-degree of any vertex $G$ is at least one. Let also ${mathcal{tau}}: V(G)rightarrow Bbb{N}$ be an assignment of thresholds to the vertices of $G$. A subset $M$ of vertices of $G$ is called a dynamic monopoly for $(G,tau)$ if the vertex set of $G$ can be partitioned into $D_0cup... cup D_t$ such that $D_0=M$ and for any $igeq 1$ and any $vin D_i$, the number of edges from $D_0cup... cup D_{i-1}$ to $v$ is at least $tau(v)$. One of the most applicable and widely studied threshold assignments in directed graphs is strict majority threshold assignment in which for any vertex $v$, $tau(v)=lceil (deg^{in}(v)+1)/2 rceil$, where $deg^{in}(v)$ stands for the in-degree of $v$. By a strict majority dynamic monopoly of a graph $G$ we mean any dynamic monopoly of $G$ with strict majority threshold assignment for the vertices of $G$. In this paper we first discuss some basic upper and lower bounds for the size of dynamic monopolies with general threshold assignments and then obtain some hardness complexity results concerning the smallest size of dynamic monopolies in directed graphs. Next we show that any directed graph on $n$ vertices and with positive minimum in-degree admits a strict majority dynamic monopoly with $n/2$ vertices. We show that this bound is achieved by a polynomial time algorithm. This upper bound improves greatly the best known result. The final note of the paper deals with the possibility of the improvement of the latter $n/2$ bound.
Suppose that the vertices of a graph $G$ are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists) if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by $m(G)$. It was shown by Saks and Werman that $m(K_n)=n-b(n)$, where $b(n)$ is the number of 1s in the binary representation of $n$. In this paper, we initiate the study of the problem for general graphs. The obvious bounds for a connected graph $G$ on $n$ vertices are $n-b(n)le m(G)le n-1$. We show that for any tree $T$ on an even number of vertices we have $m(T)=n-1$ and that for any tree $T$ on an odd number of vertices, we have $n-65le m(T)le n-2$. Our proof uses results about the weighted version of the problem for $K_n$, which may be of independent interest. We also exhibit a sequence $G_n$ of graphs with $m(G_n)=n-b(n)$ such that $G_n$ has $O(nb(n))$ edges and $n$ vertices.
Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, ODonnel, Tamuz and Tan conjectured that, in the ErdH{o}s--Renyi random graph $G(n,p)$, the random initial $pm 1$-assignment converges to a $99%$-agreement with high probability whenever $p=omega(1/n)$. This conjecture was first confirmed for $pgeqlambda n^{-1/2}$ for a large constant $lambda$ by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for $p< lambda n^{-1/2}$. We break this $Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n,p)$, where $lambda n^{-3/5}log n leq p leq lambda n^{-1/2}$ with a large constant $lambda>0$.
Let $G$ be a finite, undirected $d$-regular graph and $A(G)$ its normalized adjacency matrix, with eigenvalues $1 = lambda_1(A)geq dots ge lambda_n ge -1$. It is a classical fact that $lambda_n = -1$ if and only if $G$ is bipartite. Our main result provides a quantitative separation of $lambda_n$ from $-1$ in the case of Cayley graphs, in terms of their expansion. Denoting $h_{out}$ by the (outer boundary) vertex expansion of $G$, we show that if $G$ is a non-bipartite Cayley graph (constructed using a group and a symmetric generating set of size $d$) then $lambda_n ge -1 + ch_{out}^2/d^2,,$ for $c$ an absolute constant. We exhibit graphs for which this result is tight up to a factor depending on $d$. This improves upon a recent result by Biswas and Saha who showed $lambda_n ge -1 + h_{out}^4/(2^9d^8),.$ We also note that such a result could not be true for general non-bipartite graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
