Vida Dujmović, Cyril Gavoille, Gwenaël Joret, Piotr Micek, Pat Morin, David R. Wood
原文摘要
We show that, for every fixed proper minor-closed graph class $\mathcal{G}$ and every positive integer $n$, there exists a graph $U_n$ with $n^{1+o(1)}$ vertices and edges such that every $n$-vertex graph in $\mathcal{G}$ is isomorphic to an induced subgraph of $U_n$. This result generalizes and unifies the results of Dujmović et al. (J. ACM 2021) on induced-universal graphs and the results of Esperet, Joret, and Morin (J. London Math. Soc. 2023) on sparse induced-universal graphs from planar graphs to all proper minor-closed graph classes. It simultaneously improves the previous bounds for the number of vertices in induced-universal graphs (previously $O(n^2)$ obtained as a corollary of a result of DeVos et al. (J. Comb. Theory, Ser. {B} 2004) and a result of Gavoille and Labourel (ESA 2007)) and the number of edges in subgraph-universal graphs (previously $O(n^{3/2})$ by Babai et al. (Theory and Practice of Combinatorics 1982)).
Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, Pat Morin, Saeed Odak
原文摘要
A dominating set of a graph $G$ is \emph{connected} if it induces a connected graph in $G$. For planar triangulations, it has been known since 1990 that every $n$-vertex triangulation with $n\ge4$ admits a connected dominating set of size at most $n/2 - 1$, and no improvement to this bound was known for over three decades. We break this longstanding barrier by showing that every $n$-vertex triangulation has a connected dominating set of size at most $10n/21$. Equivalently, every triangulation admits a spanning tree with at least $11n/21$ leaves. This result has graph drawing applications, establishing a bound for one-bend free sets and improving the known bound for simultaneous planar embeddings. The connected dominating set results extend readily to show that an $n$-vertex triangulation of a surface of Euler genus $g$ has a connected dominating set of size at most $10n/21+O(\sqrt{gn})$.