论文标题
在严格的棕褐色上
On Strict Brambles
论文作者
论文摘要
严格的图形$ g $的严格武器是一系列成对的切割连接的子图的集合。 $g。$严格的bramble $ g $的严格bramble数字可以看作是扩展过环的概念的一种方式，而不是（非空）无环形图完全是每个严格的bramble订单的图形。我们通过提供三个替代定义来启动此图参数的研究，每个定义都揭示了不同的结构特征。第一个是最小的定理，声称$ {\ sf sbn}（g）$等于$ g $的最低$ k $是一棵树和$ k $ vertices上的词汇量的少数$ k $（也称为$ k $ decturetices（也称为词素树产品编号）。第二个特征是根据一种称为宽树分解的树的新变体。我们证明，$ {\ sf sbn}（g）$等于最多$ g $ w宽的最小$ k $，最多$ k。$ $ $k。$第三个特征在极端图中。为此，我们为每个$ k（$ $ k $ domino-tree的概念）定义，我们证明，最多$ k $的每个边缘最大图形是$ k $ -domino-tree。我们还标识了三个构成最多有两个具有严格烤制数字的图形类别的图表集的图。我们通过证明了一些$ g $和$ k来完成我们的结果，$确定$ {\ sf sbn}（g）\ leq k $是$ {\ sf np} $ - 完整问题。
A strict bramble of a graph $G$ is a collection of pairwise-intersecting connected subgraphs of $G.$ The order of a strict bramble ${\cal B}$ is the minimum size of a set of vertices intersecting all sets of ${\cal B}.$ The strict bramble number of $G,$ denoted by ${\sf sbn}(G),$ is the maximum order of a strict bramble in $G.$ The strict bramble number of $G$ can be seen as a way to extend the notion of acyclicity, departing from the fact that (non-empty) acyclic graphs are exactly the graphs where every strict bramble has order one. We initiate the study of this graph parameter by providing three alternative definitions, each revealing different structural characteristics. The first is a min-max theorem asserting that ${\sf sbn}(G)$ is equal to the minimum $k$ for which $G$ is a minor of the lexicographic product of a tree and a clique on $k$ vertices (also known as the lexicographic tree product number). The second characterization is in terms of a new variant of a tree decomposition called lenient tree decomposition. We prove that ${\sf sbn}(G)$ is equal to the minimum $k$ for which there exists a lenient tree decomposition of $G$ of width at most $k.$ The third characterization is in terms of extremal graphs. For this, we define, for each $k,$ the concept of a $k$-domino-tree and we prove that every edge-maximal graph of strict bramble number at most $k$ is a $k$-domino-tree. We also identify three graphs that constitute the minor-obstruction set of the class of graphs with strict bramble number at most two. We complete our results by proving that, given some $G$ and $k,$ deciding whether ${\sf sbn}(G) \leq k$ is an ${\sf NP}$-complete problem.
