Source author record

Ragnar Nevries

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Towards a Characterization of Leaf Powers by Clique Arrangements

The class ${\cal L}_k$ of $k$ -leaf powers consists of graphs $G=(V,E)$ that have a $k$ -leaf root, that is, a tree $T$ with leaf set $V$ , where $xy \in E$ , if and only if the $T$ -distance between $x$ and $y$ is at most $k$ . Structure and linear time recognition algorithms have been found for $2$ -, $3$ -, $4$ -, and, to some extent, $5$ -leaf powers, and it is known that the union of all $k$ -leaf powers, that is, the graph class ${\cal L} = \bigcup_{k=2}^\infty {\cal L}_k$ , forms a proper subclass of strongly chordal graphs. Despite from that, no essential progress has been made lately. In this paper, we use the new notion of clique arrangements to suggest that leaf powers are a natural special case of strongly chordal graphs. The clique arrangement ${\cal A}(G)$ of a chordal graph $G$ is a directed graph that represents the intersections between maximal cliques of $G$ by nodes and the mutual inclusion of these vertex subsets by arcs. Recently, strongly chordal graphs have been characterized as the graphs that have a clique arrangement without bad $k$ -cycles for $k \geq 3$ . We show that the clique arrangement of every graph of ${\cal L}$ is free of bad $2$ -cycles. The question whether this characterizes the class ${\cal L}$ exactly remains open.

preprint2013arXiv

New Polynomial Cases of the Weighted Efficient Domination Problem

Let G be a finite undirected graph. A vertex dominates itself and all its neighbors in G. A vertex set D is an efficient dominating set (e.d. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d. in G, is known to be NP-complete even for very restricted graph classes. In particular, the ED problem remains NP-complete for 2P3-free graphs and thus for P7-free graphs. We show that the weighted version of the problem (abbreviated WED) is solvable in polynomial time on various subclasses of 2P3-free and P7-free graphs, including (P2+P4)-free graphs, P5-free graphs and other classes. Furthermore, we show that a minimum weight e.d. consisting only of vertices of degree at most 2 (if one exists) can be found in polynomial time. This contrasts with our NP-completeness result for the ED problem on planar bipartite graphs with maximum degree 3.

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.