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
Coloring Four-uniform Hypergraphs on Nine Vertices Every 4-uniform hypergraph on 9 vertices
with at most 25 edges has property B.
This gives the answer $m_9(4)=26$ to a question
raised in 1968 by ErdÅs.
Keywords:property B, coloring hypergraphs Category:05C15 |
3. CMB 2011 (vol 56 pp. 265)
Embedding Distributions of Generalized Fan Graphs Total embedding distributions have been known for a few classes of graphs.
Chen, Gross, and Rieper
computed it for necklaces, close-end ladders and cobblestone
paths. Kwak and Shim computed it for bouquets of circles and
dipoles. In this paper, a splitting theorem is generalized
and the embedding distributions of
generalized fan graphs are obtained.
Keywords:total embedding distribution, splitting theorem, generalized fan graphs Category:05C10 |
4. CMB 1998 (vol 41 pp. 348)
Characterizing continua by disconnection properties We study Hausdorff continua in which every set of certain
cardinality contains a subset which disconnects the space. We show
that such continua are rim-finite. We give characterizations of
this class among metric continua. As an application of our
methods, we show that continua in which each countably infinite set
disconnects are generalized graphs. This extends a result of
Nadler for metric continua.
Keywords:disconnection properties, rim-finite continua, graphs Categories:54D05, 54F20, 54F50 |