اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Firebreak Problem
72
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Suppose we have a network that is represented by a graph $G$. Potentially a fire (or other type of contagion) might erupt at some vertex of $G$. We are able to respond to this outbreak by establishing a firebreak at $k$ other vertices of $G$, so that the fire cannot pass through these fortified vertices. The question that now arises is which $k$ vertices will result in the greatest number of vertices being saved from the fire, assuming that the fire will spread to every vertex that is not fully behind the $k$ vertices of the firebreak. This is the essence of the {sc Firebreak} decision problem, which is the focus of this paper. We establish that the problem is intractable on the class of split graphs as well as on the class of bipartite graphs, but can be solved in linear time when restricted to graphs having constant-bounded treewidth, or in polynomial time when restricted to intersection graphs. We also consider some closely related problems.
قيم البحث
اقرأ أيضاً
We prove that any quasirandom dense large graph in which all degrees are equal and even can be decomposed into any given collection of two-factors (2-regular spanning subgraphs). A special case of this result gives a new solution to the Oberwolfach problem.
Classical questions in extremal graph theory concern the asymptotics of $operatorname{ex}(G, mathcal{H})$ where $mathcal{H}$ is a fixed family of graphs and $G=G_n$ is taken from a `standard increasing sequence of host graphs $(G_1, G_2, dots)$, most
often $K_n$ or $K_{n,n}$. Inverting the question, we can instead ask how large $e(G)$ can be with respect to $operatorname{ex}(G,mathcal{H})$. We show that the standard sequences indeed maximize $e(G)$ for some choices of $mathcal{H}$, but not for others. Many interesting questions and previous results arise very naturally in this context, which also, unusually, gives rise to sensible extremal questions concerning multigraphs and non-uniform hypergraphs.
The famous $n$-queens problem asks how many ways there are to place $n$ queens on an $n times n$ chessboard so that no two queens can attack one another. The toroidal $n$-queens problem asks the same question where the board is considered on the surf
ace of the torus and was asked by P{o}lya in 1918. Let $Q(n)$ denote the number of $n$-queens configurations on the classical board and $T(n)$ the number of toroidal $n$-queens configurations. P{o}lya showed that $T(n)>0$ if and only if $n equiv 1,5 mod 6$ and much more recently, in 2017, Luria showed that $T(n)leq ((1+o(1))ne^{-3})^n$ and conjectured equality when $n equiv 1,5 mod 6$. Our main result is a proof of this conjecture, thus answering P{o}lyas question asymptotically. Furthermore, we also show that $Q(n)geq((1+o(1))ne^{-3})^n$ for all $n$ sufficiently large, which was independently proved by Luria and Simkin. Combined with our main result and an upper bound of Luria, this completely settles a conjecture of Rivin, Vardi and Zimmmerman from 1994 regarding both $Q(n)$ and $T(n)$. Our proof combines a random greedy algorithm to count almost configurations with a complex absorbing strategy that uses ideas from the recently developed methods of randomised algebraic construction and iterative absorption.
In this paper we investigate an extremal problem on binary phylogenetic trees. Given two such trees $T_1$ and $T_2$, both with leaf-set ${1,2,...,n}$, we are interested in the size of the largest subset $S subseteq {1,2,...,n}$ of leaves in a common
subtree of $T_1$ and $T_2$. We show that any two binary phylogenetic trees have a common subtree on $Omega(sqrt{log{n}})$ leaves, thus improving on the previously known bound of $Omega(loglog n)$ due to M. Steel and L. Szekely. To achieve this improved bound, we first consider two special cases of the problem: when one of the trees is balanced or a caterpillar, we show that the largest common subtree has $Omega(log n)$ leaves. We then handle the general case by proving and applying a Ramsey-type result: that every binary tree contains either a large balanced subtree or a large caterpillar. We also show that there are constants $c, alpha > 0$ such that, when both trees are balanced, they have a common subtree on $c n^alpha$ leaves. We conjecture that it is possible to take $alpha = 1/2$ in the unrooted case, and both $c = 1$ and $alpha = 1/2$ in the rooted case.
The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given $2$-factor. We show that this can be achieved for all large $n$. We actually prove a significantly more general result, whic
h allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton-Waterloo problem for large $n$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
