TY - JOUR

T1 - On Strict Brambles

AU - Lardas, Emmanouil

AU - Protopapas, Evangelos

AU - Thilikos, Dimitrios M.

AU - Zoros, Dimitris

N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Nature Japan KK, part of Springer Nature.

PY - 2023/4

Y1 - 2023/4

N2 - A strict bramble of a graph G is a collection of pairwise-intersecting connected subgraphs of G. The order of a strict bramble B is the minimum size of a set of vertices intersecting all sets of B. The strict bramble number of G, denoted by 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 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 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 sbn(G) ≤ k is an NP-complete problem.

AB - A strict bramble of a graph G is a collection of pairwise-intersecting connected subgraphs of G. The order of a strict bramble B is the minimum size of a set of vertices intersecting all sets of B. The strict bramble number of G, denoted by 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 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 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 sbn(G) ≤ k is an NP-complete problem.

KW - Bramble

KW - Lenient tree decomposition

KW - Lexicographic tree product number

KW - Obstruction set

KW - Strict bramble

KW - Tree decomposition

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85148533329&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85148533329&partnerID=8YFLogxK

U2 - 10.1007/s00373-023-02618-y

DO - 10.1007/s00373-023-02618-y

M3 - Article

AN - SCOPUS:85148533329

SN - 0911-0119

VL - 39

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 2

M1 - 24

ER -