Source author record

Thomas Sasse

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Locating-dominating sets in twin-free graphs

A locating-dominating set of a graph $G$ is a dominating set $D$ of $G$ with the additional property that every two distinct vertices outside $D$ have distinct neighbors in $D$ ; that is, for distinct vertices $u$ and $v$ outside $D$ , $N(u) \cap D \ne N(v) \cap D$ where $N(u)$ denotes the open neighborhood of $u$ . A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-domination number of $G$ , denoted $γ_L(G)$ , is the minimum cardinality of a locating-dominating set in $G$ . It is conjectured [D. Garijo, A. González and A. Márquez. The difference between the metric dimension and the determining number of a graph. Applied Mathematics and Computation 249 (2014), 487--501] that if $G$ is a twin-free graph of order $n$ without isolated vertices, then $γ_L(G)\le \frac{n}{2}$ . We prove the general bound $γ_L(G)\le \frac{2n}{3}$ , slightly improving over the $\lfloor\frac{2n}{3}\rfloor+1$ bound of Garijo et al. We then provide constructions of graphs reaching the $\frac{n}{2}$ bound, showing that if the conjecture is true, the family of extremal graphs is a very rich one. Moreover, we characterize the trees $G$ that are extremal for this bound. We finally prove the conjecture for split graphs and co-bipartite graphs.

preprint2014arXiv

Induced Cycles in Graphs

The maximum cardinality of an induced $2$ -regular subgraph of a graph $G$ is denoted by $c_{\rm ind}(G)$ . We prove that if $G$ is an $r$ -regular graph of order $n$ , then $c_{\rm ind}(G) \geq \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}$ and we prove that if $G$ is a cubic claw-free graph on order $n$ , then $c_{\rm ind}(G) > 13n/20$ and this bound is asymptotically best possible.

preprint2013arXiv

Induced Matchings in Subcubic Graphs

We prove that a cubic graph with $m$ edges has an induced matching with at least $m/9$ edges. Our result generalizes a result for planar graphs due to Kang, Mnich, and Müller (Induced matchings in subcubic planar graphs, SIAM J. Discrete Math. 26 (2012) 1383-1411) and solves a conjecture of Henning and Rautenbach (Induced matchings in subcubic graphs without short cycles, to appear in Discrete Math.).

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.