Source author record

Erik Friese

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

ResearcherUnclaimed source record

Catalog footprint

Research overview

2works
4topics
3close collaborators

Published work

2 publications

preprint2015arXiv

Affine Symmetries of Orbit Polytopes

An orbit polytope is the convex hull of an orbit under a finite group G≤GL⁡(d,R)G \leq \operatorname{GL}(d,\mathbb{R}). We develop a general theory of possible affine symmetry groups of orbit polytopes. For every group, we define an open and dense set of generic points such that the orbit polytopes of generic points have conjugated affine symmetry groups. We prove that the symmetry group of a generic orbit polytope is again GG if GG is itself the affine symmetry group of some orbit polytope, or if GG is absolutely irreducible. On the other hand, we describe some general cases where the affine symmetry group grows. We apply our theory to representation polytopes (the convex hull of a finite matrix group) and show that their affine symmetries can be computed effectively from a certain character. We use this to construct counterexamples to a conjecture of Baumeister et~al.\ on permutation polytopes [Advances in Math. 222 (2009), 431--452, Conjecture~5.4].

preprint2015arXiv

Efficient Domination for Some Subclasses of P6P_6-Free Graphs in Polynomial Time

Let GG be a finite undirected graph. A vertex {\em dominates} itself and all its neighbors in GG. A vertex set DD is an {\em efficient dominating set} (\emph{e.d.}\ for short) of GG if every vertex of GG is dominated by exactly one vertex of DD. The \emph{Efficient Domination} (ED) problem, which asks for the existence of an e.d.\ in GG, is known to be \NP-complete even for very restricted graph classes such as P7P_7-free chordal graphs. The ED problem on a graph GG can be reduced to the Maximum Weight Independent Set (MWIS) problem on the square of GG. The complexity of the ED problem is an open question for P6P_6-free graphs and was open even for the subclass of P6P_6-free chordal graphs. In this paper, we show that squares of P6P_6-free chordal graphs that have an e.d. are chordal; this even holds for the larger class of (P6P_6, house, hole, domino)-free graphs. This implies that ED/WeightedED is solvable in polynomial time for (P6P_6, house, hole, domino)-free graphs; in particular, for P6P_6-free chordal graphs. Moreover, based on our result that squares of P6P_6-free graphs that have an e.d. are hole-free and some properties concerning odd antiholes, we show that squares of (P6P_6, house)-free graphs ((P6P_6, bull)-free graphs, respectively) that have an e.d. are perfect. This implies that ED/WeightedED is solvable in polynomial time for (P6P_6, house)-free graphs and for (P6P_6, bull)-free graphs (the time bound for (P6P_6, house, hole, domino)-free graphs is better than that for (P6P_6, house)-free graphs). The complexity of the ED problem for P6P_6-free graphs remains an open question.

Research graph

See the researcher in context

Open full explorer

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.