Skip to main content
Department of Mathematics

Volume 10 (2006) No. 1

Volume 10 (2006) No. 1 imagen

A unified approach to continuous-time discounted Markov control processes

Tomás Prieto-Rumeau and Onésimo Hernández-Lerma


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


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.