Source author record

Erik Friese

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

ResearcherUnclaimed source record

Catalog footprint

What is connected

2works
4topics
3close collaborators

Actions

Connect this record

Log in to claim

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.

Published work

2 published item(s)

preprint2015arXiv

Affine Symmetries of Orbit Polytopes

An orbit polytope is the convex hull of an orbit under a finite group $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 $G$ if $G$ is itself the affine symmetry group of some orbit polytope, or if $G$ 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 $P_6$-Free Graphs in Polynomial Time

Let $G$ be a finite undirected graph. A vertex {\em dominates} itself and all its neighbors in $G$. A vertex set $D$ is an {\em efficient dominating set} (\emph{e.d.}\ for short) of $G$ if every vertex of $G$ is dominated by exactly one vertex of $D$. The \emph{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 such as $P_7$-free chordal graphs. The ED problem on a graph $G$ can be reduced to the Maximum Weight Independent Set (MWIS) problem on the square of $G$. The complexity of the ED problem is an open question for $P_6$-free graphs and was open even for the subclass of $P_6$-free chordal graphs. In this paper, we show that squares of $P_6$-free chordal graphs that have an e.d. are chordal; this even holds for the larger class of ($P_6$, house, hole, domino)-free graphs. This implies that ED/WeightedED is solvable in polynomial time for ($P_6$, house, hole, domino)-free graphs; in particular, for $P_6$-free chordal graphs. Moreover, based on our result that squares of $P_6$-free graphs that have an e.d. are hole-free and some properties concerning odd antiholes, we show that squares of ($P_6$, house)-free graphs (($P_6$, bull)-free graphs, respectively) that have an e.d. are perfect. This implies that ED/WeightedED is solvable in polynomial time for ($P_6$, house)-free graphs and for ($P_6$, bull)-free graphs (the time bound for ($P_6$, house, hole, domino)-free graphs is better than that for ($P_6$, house)-free graphs). The complexity of the ED problem for $P_6$-free graphs remains an open question.