Source author record

David Gajser

David Gajser appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.CA math.CO

Catalog footprint

What is connected

3works

4topics

2close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2016arXiv

Minimal normal graph covers

A graph is normal if it admits a clique cover $\mathcal C$ and a stable set cover $\mathcal S$ such that each clique in $\mathcal C$ and each stable set in $\mathcal S$ have a vertex in common. The pair $(\mathcal{C,S})$ is a normal cover of the graph. We present the following extremal property of normal covers. For positive integers $c,s$, if a graph with $n$ vertices admits a normal cover with cliques of sizes at most $c$ and stable sets of sizes at most $s$, then $c+s\geq\log_2(n)$. For infinitely many $n$, we also give a construction of a graph with $n$ vertices that admits a normal cover with cliques and stable sets of sizes less than $0.87\log_2(n)$. Furthermore, we show that for all $n$, there exists a normal graph with $n$ vertices, clique number $Θ(\log_2(n))$ and independence number $Θ(\log_2(n))$. When $c$ or $s$ are very small, we can describe all normal graphs with the largest possible number of vertices that allow a normal cover with cliques of sizes at most $c$ and stable sets of sizes at most $s$. However, such extremal graphs remain elusive even for moderately small values of $c$ and $s$.

preprint2015arXiv

Simple PTAS's for families of graphs excluding a minor

We show that very simple algorithms based on local search are polynomial-time approximation schemes for Maximum Independent Set, Minimum Vertex Cover and Minimum Dominating Set, when the input graphs have a fixed forbidden minor.

preprint2014arXiv

The limit of binomial means of a sequence

For a sequence $\{a_n\}_{n\geq 0}$ of real numbers and for a parameter $0<p<1$, we define the sequence of its arithmetic means $\{a^*_n\}_{n\geq 0}$ and the sequence of its $p$-binomial means $\{a^p_n\}_{n\geq 0}$ as \begin{align*} a^*_n=\frac{1}{n+1}\sum_{i=0}^n a_i & & \textrm{and} && a^p_n=\sum_{i=0}^n\binom{n}{i}p^i(1-p)^{n-i} a_i. \end{align*} We compare the convergence of sequences $\{a_n\}_{n\geq 0}$, $\{a_n^*\}_{n\geq 0}$ and $\{a_n^p\}_{n\geq 0}$ for various $0<p<1$, i.e. we analyze when the convergence of one sequence implies the convergence of the other. While the sequence $\{a^*_n\}_{n\geq 0}$, known also as the sequence of Cesàro means of a sequence, is well studied in the literature, the results about $\{a^p_n\}_{n\geq 0}$ are hard to find. Our main result shows that, if $\{a_n\}_{n\geq 0}$ is a sequence of non-negative real numbers such that $\{a^p_n\}_{n\geq 0}$ converges to $a\in\mathbb{R}\cup\{\infty\}$ for some $0<p<1$, then $\{a^*_n\}_{n\geq 0}$ also converges to $a$. We give an application of this result on finite Markov chains.