Volume 10 (2006) No. 1
Volume 10 (2006) No. 1 
A unified approach to continuous-time discounted Markov control processes
Tomás Prieto-Rumeau and Onésimo Hernández-Lerma
Abstract:
In this paper we consider continuous-time Markov control processes with Borel state and action spaces. The performance criterion is the expected discounted reward over a finite or an infinite time horizon. The reward rates and the transition rates of the system are allowed to be unbounded. We propose conditions ensuring that the optimal discounted reward of both the finite and the infinite horizon problem satisfy a dynamic programming optimality equation, and we also prove the existence of $\varepsilon$-optimal and optimal strategies. Finite horizon approximations to the infinite horizon problem are discussed. We illustrate our results by showing that our hypotheses are satisfied by some classes of controlled Markov chains and controlled diffusions.
On bounds for the stability number of graphs
Isidoro Gitler and Carlos E. Valencia
Abstract:
Let $G$ be a graph without isolated vertices and let $\alpha(G)$ be its stability number and $\tau(G)$ its covering number. In this paper we study the minimum number of edges a connected graph can have as a function of $\alpha(G)$ and $\tau(G)$. In particular we obtain the following lower bound:
$$ q(G) \geq \alpha(G)-c(G)+ \Gamma(\alpha(G), \tau(G)), $$
where $c(G)$ is the number of connected components of $G$ and
$$\Gamma(a,t)= \min\left\{\sum_{i=1}^{a}\binom{z_i}{2} \Bigg| \begin{array}{l} z_1+\cdots+z_{a}= a+ t\\ \mbox{and } z_i \geq 0 \quad \forall \, i=1,\ldots, a \end{array}\right\}$$
for $a$ and $t$ two arbitrary natural numbers.
Also we prove that $\alpha(G)\leq \tau(G)[1+\delta(G)]$, where $\delta(G) = \alpha(G)-\sigma_{v}(G)$ and $\sigma_{v}(G)$ is the $\sigma_{v}$-cover number of a graph, that is, the maximum natural number $m$ such that every vertex of $G$ belongs to a maximal independent set with at least $m$ vertices.