Source author record

Manouchehr Zaker

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

8works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A note concerning the Grundy and ${\rm b}$ -chromatic number of graphs

The Grundy number of a graph $G$ is the maximum number of colors used by the First-Fit coloring of $G$ and is denoted by $Γ(G)$ . Similarly, the ${\rm b}$ -chromatic number ${\rm{b}}(G)$ of $G$ expresses the worst case behavior of another well-known coloring procedure i.e. color-dominating coloring of $G$ . We obtain some families of graphs $\mathcal{F}$ for which there exists a function $f(x)$ such that $Γ(G)\leq f({\rm{b}}(G))$ , for each graph $G$ from the family. Call any such family $(Γ,b)$ -bounded family. We conjecture that the family of ${\rm b}$ -monotone graphs is $(Γ,b)$ -bounded and validate the conjecture for some families of graphs.

preprint2016arXiv

$(δ, χ_{_{\sf FF}})$ -bounded families of graphs

For any graph $G$ , the First-Fit (or Grundy) chromatic number of $G$ , denoted by $χ_{_{\sf FF}}(G)$ , is defined as the maximum number of colors used by the First-Fit (greedy) coloring of the vertices of $G$ . We call a family $\mathcal{F}$ of graphs $(δ, χ_{_{\sf FF}})$ -bounded if there exists a function $f(x)$ with $f(x)\rightarrow \infty$ as $x\rightarrow \infty$ such that for any graph $G$ from the family one has $χ_{_{\sf FF}}(G)\geq f(δ(G))$ , where $δ(G)$ is the minimum degree of $G$ . We first give some results concerning $(δ, χ_{_{\sf FF}})$ -bounded families and obtain a few such families. Then we prove that for any positive integer $\ell$ , $Forb(K_{\ell,\ell})$ is $(δ, χ_{_{\sf FF}})$ -bounded, where $K_{\ell,\ell}$ is complete bipartite graph. We conjecture that if $G$ is any $C_4$ -free graph then $χ_{_{\sf FF}}(G)\geq δ(G)+1$ . We prove the validity of this conjecture for chordal graphs, complement of bipartite graphs and graphs with low minimum degree.

preprint2015arXiv

Lower bounds for independence and $k$ -independence number of graphs using the concept of degenerate degrees

Let $G$ be a graph and $v$ any vertex of $G$ . We define the degenerate degree of $v$ , denoted by $ζ(v)$ as $ζ(v)={\max}_{H: v\in H}~δ(H)$ , where the maximum is taken over all subgraphs of $G$ containing the vertex $v$ . We show that the degenerate degree sequence of any graph can be determined by an efficient algorithm. A $k$ -independent set in $G$ is any set $S$ of vertices such that $Δ(G[S])\leq k$ . The largest cardinality of any $k$ -independent set is denoted by $α_k(G)$ . For $k\in \{1, 2, 3\}$ , we prove that $α_{k-1}(G)\geq {\sum}_{v\in G} \min \{1, 1/(ζ(v)+(1/k))\}$ . Using the concept of cheap vertices we strengthen our bound for the independence number. The resulting lower bounds improve greatly the famous Caro-Wei bound and also the best known bounds for $α_1(G)$ and $α_2(G)$ for some families of graphs. We show that the equality in our bound for independence number happens for a large class of graphs. Our bounds are achieved by Cheap-Greedy algorithms for $α_k(G)$ which are designed by the concept of cheap sets. At the end, a bound for $α_k(G)$ is presented, where $G$ is a forest and $k$ an arbitrary non-negative integer.

preprint2014arXiv

On the largest dynamic monopolies of graphs with a given average threshold

Let $G$ be a graph and $τ$ be an assignment of nonnegative integer thresholds to the vertices of $G$ . A subset of vertices $D$ is said to be a $τ$ -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 $i\in \{0, \ldots, k-1\}$ , each vertex $v$ in $D_{i+1}$ has at least $τ(v)$ neighbors in $D_0\cup \ldots \cup D_i$ . Denote the size of smallest $τ$ -dynamic monopoly by $dyn_τ(G)$ and the average of thresholds in $τ$ by $\overlineτ$ . We show that the values of $dyn_τ(G)$ over all assignments $τ$ with the same average threshold is a continuous set of integers. For any positive number $t$ , denote the maximum $dyn_τ(G)$ taken over all threshold assignments $τ$ with $\overlineτ\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.

preprint2012arXiv

Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks

Let $G$ be a directed graph such that the in-degree of any vertex $G$ is at least one. Let also ${\mathcalτ}: 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,τ)$ if the vertex set of $G$ can be partitioned into $D_0\cup... \cup D_t$ such that $D_0=M$ and for any $i\geq 1$ and any $v\in D_i$ , the number of edges from $D_0\cup... \cup D_{i-1}$ to $v$ is at least $τ(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$ , $τ(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.

preprint2012arXiv

Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs

A graph $G$ is said to be a $k$ -degenerate graph if any subgraph of $G$ contains a vertex of degree at most $k$ . Let $κ$ be any non-negative function on the vertex set of $G$ . We first define a $κ$ -degenerate graph. Next we give an efficient algorithm to determine whether a graph is $κ$ -degenerate. We revisit the concept of dynamic monopolies in graphs. The latter notion is used in formulation and analysis of spread of influence such as disease or opinion in social networks. We consider dynamic monopolies with (not necessarily positive) but integral threshold assignments. We obtain a sufficient and necessary relationship between dynamic monopolies and generalized degeneracy. As applications of the previous results we consider the problem of determining the maximum size of $κ$ -degenerate (or $k$ -degenerate) induced subgraphs in any graph. We obtain some upper and lower bounds for the maximum size of any $κ$ -degenerate induced subgraph in general and regular graphs. All of our bounds are constructive.

preprint2012arXiv

On dynamic monopolies of graphs: the average and strict majority thresholds

Let $G$ be a graph and ${\mathcalτ}: 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, τ)$ if the vertices of $G$ can be partitioned into subsets $D_0, D_1,..., D_k$ such that $D_0=D$ and for any $i\in {0, ..., k-1}$ , each vertex $v$ in $D_{i+1}$ has at least $τ(v)$ neighbors in $D_0\cup ... \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 $α'(G)+1$ is an upper bound for the size of strict majority dynamic monopoly, where $α'(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.

preprint2011arXiv

On dynamic monopolies of graphs with general thresholds

Let $G$ be a graph and ${\mathcalτ}: V(G)\rightarrow \Bbb{N}$ be an assignment of thresholds to the vertices of $G$ . A subset of vertices $D$ is said to be dynamic monopoly (or simply dynamo) if the vertices of $G$ can be partitioned into subsets $D_0, D_1,..., D_k$ such that $D_0=D$ and for any $i=1,..., k-1$ each vertex $v$ in $D_{i+1}$ has at least $t(v)$ neighbors in $D_0\cup ...\cup D_i$ . Dynamic monopolies are in fact modeling the irreversible spread of influence such as disease or belief in social networks. We denote the smallest size of any dynamic monopoly of $G$ , with a given threshold assignment, by $dyn(G)$ . In this paper we first define the concept of a resistant subgraph and show its relationship with dynamic monopolies. Then we obtain some lower and upper bounds for the smallest size of dynamic monopolies in graphs with different types of thresholds. Next we introduce dynamo-unbounded families of graphs and prove some related results. We also define the concept of a homogenious society that is a graph with probabilistic thresholds satisfying some conditions and obtain a bound for the smallest size of its dynamos. Finally we consider dynamic monopoly of line graphs and obtain some bounds for their sizes and determine the exact values in some special cases.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Manouchehr Zaker

Research overview

Is this your work?

8 publications

A note concerning the Grundy and ${\rm b}$ -chromatic number of graphs

$(δ, χ_{_{\sf FF}})$ -bounded families of graphs

Lower bounds for independence and $k$ -independence number of graphs using the concept of degenerate degrees

On the largest dynamic monopolies of graphs with a given average threshold

Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks

Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs

On dynamic monopolies of graphs: the average and strict majority thresholds

On dynamic monopolies of graphs with general thresholds

See the researcher in context

Building this map preview

Manouchehr Zaker

Research overview

Is this your work?

8 publications

A note concerning the Grundy and b{\rm b}b-chromatic number of graphs

(δ,χFF)(δ, χ_{_{\sf FF}})(δ,χFF​​)-bounded families of graphs

Lower bounds for independence and kkk-independence number of graphs using the concept of degenerate degrees

On the largest dynamic monopolies of graphs with a given average threshold

Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks

Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs

On dynamic monopolies of graphs: the average and strict majority thresholds

On dynamic monopolies of graphs with general thresholds

See the researcher in context

Building this map preview

A note concerning the Grundy and ${\rm b}$ -chromatic number of graphs

$(δ, χ_{_{\sf FF}})$ -bounded families of graphs

Lower bounds for independence and $k$ -independence number of graphs using the concept of degenerate degrees