Source author record

Christian Löwenstein

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

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Independence in Uniform Linear Triangle-free Hypergraphs

The independence number $α(H)$ of a hypergraph $H$ is the maximum cardinality of a set of vertices of $H$ that does not contain an edge of $H$ . Generalizing Shearer's classical lower bound on the independence number of triangle-free graphs (J. Comb. Theory, Ser. B 53 (1991) 300-307), and considerably improving recent results of Li and Zang (SIAM J. Discrete Math. 20 (2006) 96-104) and Chishti et al. (Acta Univ. Sapientiae, Informatica 6 (2014) 132-158), we show that $α(H)\geq \sum_{u\in V(H)}f_r(d_H(u))$ for an $r$ -uniform linear triangle-free hypergraph $H$ with $r\geq 2$ , where \begin{eqnarray*} f_r(0)&=&1\mbox{, and }\\ f_r(d)&=&\frac{1+\Big((r-1)d^2-d\Big)f_r(d-1)}{1+(r-1)d^2}\mbox{ for $d\geq 1$ .} \end{eqnarray*}

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

A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem

For $k \ge 2$ , let $H$ be a $k$ -uniform hypergraph on $n$ vertices and $m$ edges. The transversal number $τ(H)$ of $H$ is the minimum number of vertices that intersect every edge. Chvátal and McDiarmid [Combinatorica 12 (1992), 19--26] proved that $τ(H)\le ( n + \left\lfloor \frac k2 \right\rfloor m )/ ( \left\lfloor \frac{3k}2 \right\rfloor )$ . When $k = 3$ , the connected hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem were characterized by Henning and Yeo [J. Graph Theory 59 (2008), 326--348]. In this paper, we characterize the connected hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem for $k = 2$ and for all $k \ge 4$ .

preprint2014arXiv

Induced 2-Regular Subgraphs in k-Chordal Cubic Graphs

We show that a cubic graph $G$ of order $n$ has an induced $2$ -regular subgraph of order at least a) $\frac{n-2}{4-\frac{4}{k}}$ , if $G$ has no induced cycle of length more than $k$ , b) $\frac{5n+6}{8}$ , if $G$ has no induced cycle of length more than $4$ , and $n>6$ , and c) $\left(\frac{1}{4}+ε\right)n$ , if the independence number of $G$ is at most $\left(\frac{3}{8}-ε\right)n$ . To show the second result we give a precise structural description of cubic $4$ -chordal 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.

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.

Christian Löwenstein

Research overview

Is this your work?

5 publications

Independence in Uniform Linear Triangle-free Hypergraphs

Locating-dominating sets in twin-free graphs

A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem

Induced 2-Regular Subgraphs in k-Chordal Cubic Graphs

Induced Cycles in Graphs

See the researcher in context

Building this map preview