Expand all Collapse all | Results 1 - 4 of 4 |
1. CMB Online first
On the largest dynamic monopolies of graphs with a given average threshold 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 $i\in \{0, \ldots, k-1\}$, each vertex $v$ in $D_{i+1}$
has at least $\tau(v)$ neighbors in $D_0\cup \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\lt 1$. Next, we show that $Ldyn_t(G)$ is coNP-hard for planar
graphs but has polynomial-time solution for forests.
Keywords:spread of influence in graphs, irreversible dynamic monopolies, target set selection Categories:05C69, 05C85 |
2. CMB Online first
On domination of zero-divisor graphs of matrix rings We study domination in zero-divisor graphs of matrix rings over a
commutative ring with $1$.
Keywords:vector space, linear transformation, zero-divisor graph, domination, local ring Category:05C69 |
3. CMB 2013 (vol 57 pp. 141)
Size, Order, and Connected Domination We give a sharp upper bound on the size of a
triangle-free graph of a given order and connected domination. Our
bound, apart from
strengthening an old classical theorem of Mantel and of
TurÃ¡n , improves on a theorem of Sanchis.
Further, as corollaries, we settle a long standing
conjecture of Graffiti on the leaf number and local independence for
triangle-free graphs and answer a question of Griggs, Kleitman and
Shastri on a lower bound of the leaf number in
triangle-free graphs.
Keywords:size, connected domination, local independence number, leaf number Category:05C69 |
4. CMB 2011 (vol 56 pp. 407)
On Domination in Zero-Divisor Graphs We first determine the domination number for the zero-divisor
graph of the product of two commutative rings with $1$. We then
calculate the domination number for the zero-divisor graph of any
commutative artinian ring. Finally, we extend some of the results
to non-commutative rings in which an element is a left
zero-divisor if and only if it is a right zero-divisor.
Keywords:zero-divisor graph, domination Categories:13AXX, 05C69 |