Pith. sign in

REVIEW 2 major objections 4 minor 42 references

This paper proves exact worst-case neighbourhood-complexity formulas for graphs of bounded treewidth and pathwidth, replacing earlier double-exponential bounds with linear-in-k constants.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 19:39 UTC pith:FL53I4IT

load-bearing objection Tight constants for neighbourhood complexity on treewidth/pathwidth, but the pathwidth upper bound has a load-bearing unproved normalization step. the 2 major comments →

arxiv 2607.16889 v1 pith:FL53I4IT submitted 2026-07-18 cs.DM math.CO

Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth

Ga\'etan Berthe , Florent Foucaud , Tuomo Lehtil\"a , Aline Parreau This is my paper
classification cs.DM math.CO MSC 05C6905C8568R10
keywords neighbourhood complexitytreewidthpathwidthidentifying codeslocating-dominating setstight boundskernelizationstructural graph theory
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Fix a k-vertex set S in a graph. Each vertex sees the intersection of its closed neighbourhood with S, and the neighbourhood complexity nc(G,k) is the largest number of distinct such intersections over all choices of S. This paper proves that for treewidth w≥2 the worst case is exactly (k−w+1)2^w + w, and for pathwidth w≥2 it is exactly (k−w+2)2^{w−1} + 2k − w − 2, whenever k is large enough relative to w. For forests, which have width 1, the exact worst case is floor(7k/3), attained even by caterpillars of maximum degree 3. These linear-in-k bounds with width-dependent constants replace earlier double-exponential-in-w upper bounds, and they carry over to identifying codes and locating-dominating sets as bounds on the number of vertices.

Core claim

The paper claims that the neighbourhood complexity of a graph is determined by the size profile of the bags in an optimal tree- or path-decomposition. Via a normalisation argument, every non-S vertex can be assigned to the first S-root bag whose subtree contains it, so that the vertex's whole S-neighbourhood lies inside that bag and contains the bag's representative S-vertex. Each such bag of size b can then host at most 2^{b−1} vertices with distinct neighbourhoods (fewer if b = w+1), and summing over the bag-size profile of a width-w decomposition yields the two formulas. The companion constructions—cliques S_i with layered vertex sets—have every vertex with a unique S-neighbourhood, so th

What carries the argument

The central object is a rooted tree-decomposition with a distinguished S-root node per S-vertex: the first node (closest to the root) whose bag contains that S-vertex. The paper shows that such a decomposition can be normalised so that (a) all S-root nodes have distinct bags, (b) no non-S vertex appears in any S-root bag, and (c) every non-S vertex assigned to an S-root node is adjacent to that node's S-vertex. Then each such vertex's entire S-neighbourhood is contained in the root bag, so at most 2^{|bag|−1} vertices can live there with distinct neighbourhoods. The counting step orders the S-root bags by size and charges each bag by its size; the same machinery, with first-appearance orderi

Load-bearing premise

In the pathwidth upper-bound proof, the step asserting that a vertex x can be assumed adjacent to its assigned S-vertex s_i—because otherwise x could be moved to a new bag just before p_{s_i}—is not justified: moving x there may disconnect x's appearance interval or violate pathwidth, and the counting that halves the number of possible neighbourhoods relies on that adjacency.

What would settle it

Compute nc(G,S) for all connected graphs on up to 9 vertices with pathwidth 2 and all 5-vertex subsets S; if any graph exceeds 16 = (5−2+2)2^{1} + 2·5 − 2 − 2, the pathwidth formula fails. Similarly, for treewidth w=2 and k=5, any graph with nc(G,S) > 18 = (5−2+1)2^2 + 2 would falsify the treewidth formula.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • If correct, the treewidth bound implies a graph of treewidth w with an identifying code of size k has at most (k−w+1)2^w + w − 1 vertices, with analogous order bounds for locating-dominating sets.
  • The construction G_{w,k} has treewidth exactly w and every vertex has a unique S-neighbourhood, so it serves as a tight example for the identification-number bounds as well.
  • For forests, the tight constant floor(7k/3), attained by degree-3 caterpillars, sharpens the previously known 3k bound for trees and transfers to identifying codes on trees.
  • Kernelization and model-checking algorithms that rely on linear neighbourhood complexity inherit explicit small constants rather than the prior double-exponential-in-w factors.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A direct exhaustive search over small pathwidth-2 graphs (e.g., k=5, threshold 16) would provide an immediate computational check of the suspect normalisation step.
  • The root-bag charging argument should extend to distance-r neighbourhood complexity, giving explicit O_w(r^w k) bounds; the paper leaves the exact dependence on r and w open.
  • The extremal treewidth construction is caterpillar-shaped, suggesting that very sparse subclasses can already saturate the bound; for w=1, degree-3 caterpillars do exactly that.
  • The identification-code corollaries give order upper bounds that are tight for the same constructions, so algorithms seeking an identifying code of size k on treewidth-w graphs can treat (k−w+1)2^w + w − 1 as a hard ceiling on the graph order.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies the maximum number of distinct intersections of closed neighbourhoods with a k-vertex set S, denoted nc(G,k), for graphs of bounded treewidth and pathwidth. It claims tight linear bounds: for treewidth w>=2, nc(G,k) <= (k-w+1)2^w + w; for pathwidth w>=2, nc(G,k) <= (k-w+2)2^{w-1} + 2k-w-2; and for forests (width 1), nc(F,k) <= floor(7k/3). Explicit extremal constructions are given for k >= 2w+1 (treewidth) and k >= 2w-1 (pathwidth), together with applications to locating-dominating sets and identifying codes.

Significance. If the results are correct, they determine the exact constants for neighbourhood complexity of bounded-treewidth and bounded-pathwidth graphs, improving on double-exponential bounds in w and resolving the width-1 case. The paper also gives explicit constructions with exact vertex counts and connects the bounds to identification problems. These are valuable contributions. However, the pathwidth upper bound contains a load-bearing unproved normalization, and the treewidth proof has a questionable edge-minimality step; until these are repaired, the main theorems are not established.

major comments (2)
  1. [Section 4.2 (Theorem 4)] The proof asserts 'we can assume that x is adjacent to s_i' and justifies it by removing x from all bags and adding a node just before p_{s_i} with bag (X(p_{s_i})\{s_i})∪{x}. This operation does not add the edge xs_i; it only relocates x when no such edge exists. If the edge is added instead, the displayed bag omits s_i and fails to cover it, while adding s_i would make the bag size w+2 when |X(p_{s_i})|=w+1. Moreover, if the exceptional vertex s' in the definition of S_i equals s_i, then s_i disappears at p_{s_i}, so no vertex in V_i can be adjacent to s_i at all. Without the adjacency, only |V_i|≤2^{|S_i|} follows, and the bound (k-w+2)2^{w-1}+2k-w-2 is not established. This is a load-bearing gap; a proof analogous to Claim C of Section 4.1 is needed.
  2. [Section 4.1 (Claim B)] In the proof of Claim B, the step 'there should be a vertex y with neighbourhood {s1,s2}, otherwise we could remove all edges between x and S\{s1,s2}, contradicting the minimality of the number of edges' is not valid. Removing those edges also removes the unique S-neighbourhood N(x) of x, so nc(G,k) decreases regardless of y; edge-minimality only forbids deletions that preserve nc, and a decrease is allowed. The existence of y with {s1,s2} would not preserve the intermediate neighbourhoods either. This invalidates the conclusion N(x)={s1,s2}, which is used to construct the decomposition transformation that removes x from Z. The normalization Z=S is therefore unproven.
minor comments (4)
  1. [Section 4.1] Typo: 'tree-decompositon' should be 'tree-decomposition'.
  2. [Section 5.1] The notation 'G w,k' appears with a space in several places; it should be G_{w,k}.
  3. [Section 4.2] The phrase 'both excluded' after defining V_i^* is confusing: the interval for V_i^* includes p_{s_i}, while the argument about first appearances uses both endpoints differently. Please clarify the interval conventions.
  4. [Section 6 (Theorem 10)] The proof of Theorem 10 is sketched very briefly. Please spell out the final counting for locating-dominating sets and identifying codes, since it differs from the neighbourhood-complexity counting in Theorem 4.

Circularity Check

0 steps flagged

No significant circularity: the upper bounds are derived from decomposition structure and explicit counting, and the lower-bound constructions are independently verified.

full rationale

The paper's central derivations (Theorems 2, 3, and 4) are self-contained: they fix an extremal graph, choose a tree/path-decomposition, partition the non-S vertices into sets V_s or V_i, and count distinct S-neighbourhoods via combinatorial bounds on subsets of bags. No parameter is fitted to the target quantity and renamed as a prediction; the counting inequalities are derived from the decomposition properties (e.g., Claim A, Claim B, Claim C) and from Lemma 5. The lower-bound constructions in Section 5 are explicit graphs whose neighbourhood complexity is verified by direct counting, and the pathwidth lower bound in Theorem 8 uses Theorem 4 only as a general upper bound to rule out pathwidth w-1, which is a legitimate tightness argument, not a circular import. The forest tightness construction is imported from [4], an external paper by different authors, so it is independent support. Self-citations ([2], [8], [25]) appear only in the introduction for context and are not load-bearing for the main results. The reader-flagged pathwidth step, where the proof says 'we can assume that x is adjacent to s_i' and proposes a bag-insertion operation, is a potential rigor gap in the proof of Theorem 4, but it is not a circularity: the claimed upper bound is not defined in terms of itself, nor is any fitted quantity relabelled as a prediction. Accordingly, the paper does not exhibit the specific reduction patterns required to establish circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

No fitted or hand-chosen numeric parameters appear; the only free symbols are the theorem parameters w and k. The paper introduces example graphs G_{w,k} and a pathwidth construction, but these are explicit objects obtained by recipes, not ad hoc entities invoked to force the conclusion. The main external dependency is the [4] tree construction used for tightness of the w=1 bound.

axioms (2)
  • standard math Connectedness property of tree/path decompositions: if a vertex appears in bags of two nodes, it appears in every bag on the path between them.
    Used throughout Section 4 (Claims A/B and pathwidth partitioning) to reason about when vertices and S-root nodes co-occur.
  • domain assumption The tree construction of [4] has floor(7k/3) vertices with all S-neighbourhoods distinct.
    Theorem 2 tightness is based on this construction; the present paper says 'it is not difficult to see' but does not provide a full verification or machine check.

pith-pipeline@v1.3.0-alltime-deepseek · 18296 in / 26141 out tokens · 259746 ms · 2026-08-01T19:39:40.349302+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth." pith.science (2026). https://pith.science/paper/FL53I4IT

@misc{pith2026260716889,
  author       = {Pith},
  title        = {Pith review of: Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FL53I4IT}},
  note         = {Machine review of arXiv:2607.16889}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The neighbourhood complexity $nc(G,k)$ of a graph $G$ is a quantity measuring, for a graph $G$ and an integer $k$, the maximum possible number (over all vertex subsets $S$ of size $k$) $|\{N[v]\cap S, v\in V(G)\}|$ of $S$-neighbourhoods in $G$. This notion is important in structural graph theory and algorithm design (especially in parameterized complexity, in particular model checking and kernelization). While generally $nc(G,k)\leq 2^k$ and this bound can be achieved, it is known that sparse graphs and structured dense graphs have linear neighbourhood complexity, that is, $nc(G,k)\in O(k)$ for any such graph $G$. However, for many graph classes, the best possible constants are not known. We focus on graphs of bounded treewidth and pathwidth, showing that (when $k\geq w+1$) (i) if $G$ has treewidth $w\geq 2$, then $nc(G,k)\leq (k-w+1)2^{w}+w$, and (ii) if $G$ has pathwidth $w\geq 2$, then $nc(G,k)\leq (k-w+2)2^{w-1}+2k-w-2$. Moreover, we provide constructions that reach these bounds, whenever $w\geq 2$ and $k\geq 2w+1$ ($k\geq 2w-1$ for pathwidth). Interestingly, in contrast, we also have the tight bound $nc(G,k)\leq \frac{7}{3}k$, for graphs $G$ with pathwidth 1 or treewidth 1.

Figures

Figures reproduced from arXiv: 2607.16889 by Aline Parreau, Florent Foucaud, Ga\'etan Berthe, Tuomo Lehtil\"a.

Figure 1
Figure 1. Figure 1: The trees Ti for 3 ≤ i ≤ 5 used in the proof of Theorem 2. The vertices of Si are in black. Remark 6. We remark that Theorem 3 would give nc(G, k) ≤ 2k + 1 for w = 1 if it was defined in that case. However, we have the tight upper bound of nc(G, k) ≤ ⌊ 7 3 k⌋ for w = 1 and 2k + 1 < ⌊ 7 3 k⌋ 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example of a tree T with k = 12 and nc(T, k) = 28, as constructed in Theorem 2. The vertices in S are the dark ones. when k ≥ 6. Hence, the neighbourhood complexity behaves differently for the cases of tw(G) = 1 and tw(G) ≥ 2. 4 Upper bounds for widths at least 2 We now proceed with the main results of the paper: the upper bounds for graphs of treewidth and pathwidth at least 2. 4.1 Treewidth In the follow… view at source ↗
Figure 3
Figure 3. Figure 3: Notations for the proof of Theorem 3, with a graph [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A tree-decomposition of graph G of [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the construction of Gw,k for treewidth w = 2 and k = 6. All the neighbour￾hoods to the black vertices are unique. 5 Tight constructions for widths at least 2 In this section, we give for each w ≥ 2 and k ≥ 2w ± 1 the constructions which show that our upper bounds are tight for both tree- and pathwidth. We begin by describing the construction for treewidth. 5.1 Treewidth In this section, for… view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of the construction of G in the proof of Theorem 8 for pathwidth w = 3 and k = 6. All the neighbourhoods to the black vertices are distinct. Removing the five gray vertices, we obtain the graph G2,6 of [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 2 linked inside Pith

  1. [1]

    N. Alon, G. Moshkovitz, and N. Solomon. Traces of hypergraphs.Journal of the London Mathematical Society, 100(2):498–517, 2019

    2019

  2. [2]

    Beaudou, J

    L. Beaudou, J. Bok, F. Foucaud, D. A. Quiroz, and J.-F. Raymond. Profile and neighbourhood complexity of graphs with excluded minors and tree-structured graphs.arXiv preprint, 2025. https://arxiv.org/abs/2501.08895

    arXiv 2025

  3. [3]

    Berthe, M

    G. Berthe, M. Bougeret, D. Gon¸ calves, and J. Raymond. Subexponential algorithms in geometric graphs via the subquadratic grid minor property: The role of local radius. In H. L. Bodlaender, editor,Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), June 12-14, 2024, Helsinki, Finland, volume 294 ofLIPIcs, pages 1...

    2024

  4. [4]

    Bertrand, I

    N. Bertrand, I. Charon, O. Hudry, and A. Lobstein. 1-identifying codes on trees.Australasian Journal of Combinatorics, 31:21–36, 2005

    2005

  5. [5]

    H. L. Bodlaender. Treewidth: Characterizations, applications, and computations. In F. V. Fomin, editor,Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006), Bergen, Norway, June 22-24, 2006, Lecture Notes in Computer Science, pages 1–14. Springer, 2006

    2006

  6. [6]

    Bonamy and C

    M. Bonamy and C. Geniet.χ-boundedness and neighbourhood complexity of bounded merge- width graphs.arXiv preprint, 2025.https://arxiv.org/abs/2504.08266

    Pith/arXiv arXiv 2025

  7. [7]

    J. A. Bondy. Induced subsets.Journal of Combinatorial Theory, Series B, 12(2):201–202, 1972

    1972

  8. [8]

    Bonnet, F

    ´E. Bonnet, F. Foucaud, T. Lehtil¨ a, and A. Parreau. Neighbourhood complexity of graphs of bounded twin-width.European Journal of Combinatorics, 115:103772, 2024

    2024

  9. [9]

    Bousquet, A

    N. Bousquet, A. Lagoutte, Z. Li, A. Parreau, and S. Thomass´ e. Identifying codes in hereditary classes of graphs and VC-dimension.SIAM Journal on Discrete Mathematics, 29(4):2047–2064, 2015

    2047

  10. [10]

    Bousquet and S

    N. Bousquet and S. Thomass´ e. VC-dimension and Erd˝ os-P´ osa property.Discrete Mathematics, 338(12):2302–2317, 2015

    2015

  11. [11]

    Chakraborty, F

    D. Chakraborty, F. Foucaud, A. Parreau, and A. Wagler. On three domination-based identifi- cation problems in block graphs.Fundamenta Informaticae, 191(3-4):197–229, 2024

    2024

  12. [12]

    Chepoi, B

    V. Chepoi, B. Estellon, and Y. Vax` es. Covering planar graphs with a fixed number of balls. Discrete & Computational Geometry, 37(2):237–244, 2007

    2007

  13. [13]

    Chudnovsky, A

    M. Chudnovsky, A. Reinald, and S. Thomass´ e. Forbidding anticomplete planar minors: Induced Erd˝ os–P´ osa property and maximum independent set in QP.arXiv preprint, 2026.https: //arxiv.org/abs/2607.09646

    Pith/arXiv arXiv 2026

  14. [14]

    Coudert, M

    D. Coudert, M. Csik´ os, G. Ducoffe, and L. Viennot. Practical computation of graph VC- dimension. In L. Liberti, editor,Proceedings of the 22nd International Symposium on Experi- mental Algorithms (SEA 2024), July 23-26, 2024, Vienna, Austria, volume 301 ofLIPIcs, pages 8:1–8:20. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024

    2024

  15. [15]

    Courcelle

    B. Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12–75, 1990

    1990

  16. [16]

    Cygan, F

    M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.Parameterized algorithms. Springer, 2015

    2015

  17. [17]

    Dreier, I

    J. Dreier, I. Eleftheriadis, N. M¨ ahlmann, R. McCarty, M. Pilipczuk, and S. Torunczyk. First- order model checking on monadically stable graph classes. InProceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2024), Chicago, IL, USA, Oc- tober 27-30, 2024, pages 21–30. IEEE, 2024. 15

    2024

  18. [18]

    Dreier, J

    J. Dreier, J. Gajarsk` y, and M. Pilipczuk. Efficient reversal of transductions of sparse graph classes. InProceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), pages 1180–1191, 2026

    2026

  19. [19]

    Dreier and S

    J. Dreier and S. Torunczyk. Merge-width and first-order model checking. In M. Kouck´ y and N. Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), Prague, Czechia, June 23-27, 2025, pages 1944–1955. ACM, 2025

    2025

  20. [20]

    Eickmeyer, A

    K. Eickmeyer, A. C. Giannopoulou, S. Kreutzer, O. Kwon, M. Pilipczuk, R. Rabinovich, and S. Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In I. Chatzigiannakis, P. Indyk, F. Kuhn, and A. Muscholl, editors,Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), July 1...

    2017

  21. [21]

    Foucaud, S

    F. Foucaud, S. Gravier, R. Naserasr, A. Parreau, and P. Valicov. Identifying codes in line graphs. Journal of Graph Theory, 73(4):425–448, 2013

    2013

  22. [22]

    Foucaud, G

    F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov. Identification, location- domination and metric dimension on interval and permutation graphs. I. bounds.Theoretical Computer Science, 668:43–58, 2017

    2017

  23. [23]

    P. Frankl. On the trace of finite sets.Journal of Combinatorial Theory, Series A, 34(1):41–45, 1983

    1983

  24. [24]

    Gajarsk´ y, P

    J. Gajarsk´ y, P. Hlinˇ en´ y, J. Obdrˇ z´ alek, S. Ordyniak, F. Reidl, P. Rossmanith, F. S´ anchez Vil- laamil, and S. Sikdar. Kernelization using structural parameters on sparse graph classes.Journal of Computer and System Sciences, 84:219–242, 2017

    2017

  25. [25]

    Jacob and M

    H. Jacob and M. Pilipczuk. Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. In M. A. Bekos and M. Kaufmann, editors,Proceedings of the 48th Inter- national Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022), T¨ ubingen, Germany, June 22-24, 2022, Lecture Notes in Computer Science, pages 287–299. Springer, 2022

    2022

  26. [26]

    Jean and A

    D. Jean and A. Lobstein. Watching systems, identifying, locating-dominating and discriminating codes in graphs: a bibliography.Published electronically athttps: // dragazo. github. io/ bibdom/ main. pdf, 2026

    2026

  27. [27]

    Joret and C

    G. Joret and C. Rambaud. Neighborhood complexity of planar graphs.Combinatorica, 44(5):1115–1148, 2024

    2024

  28. [28]

    D. Y. Kang, O. Kwon, T. J. F. Strømme, and J. A. Telle. A width parameter useful for chordal and co-comparability graphs.Theoretical Computer Science, 704:1–17, 2017

    2017

  29. [29]

    M. G. Karpovsky, K. Chakrabarty, and L. B. Levitin. On a new class of codes for identifying vertices in graphs.IEEE Transactions on Information Theory, 44(2):599–611, 1998

    1998

  30. [30]

    Kranakis, D

    E. Kranakis, D. Krizanc, B. Ruf, J. Urrutia, and G. J. Woeginger. The VC-dimension of set systems defined by graphs.Discrete Applied Mathematics, 77(3):237–257, 1997

    1997

  31. [31]

    M. Lampis. First order logic on pathwidth revisited again. In K. Etessami, U. Feige, and G. Puppis, editors,Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), Paderborn, Germany, July 10-14, 2023, LIPIcs, pages 132:1– 132:17. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2023

    2023

  32. [32]

    Lobstein, O

    A. Lobstein, O. Hudry, and I. Charon. Locating-domination and identification.Topics in Dom- ination in Graphs (editors: T. W. Haynes, M. A. Henning, S. T. Hedetniemi), pages 251–299, 2023. 16

    2023

  33. [33]

    Lokshtanov, F

    D. Lokshtanov, F. Panolan, S. Saurabh, J. Xue, and M. Zehavi. Subexponential parameterized algorithms on disk graphs. In J. S. Naor and N. Buchbinder, editors,Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), Virtual Conference / Alexandria, V A, USA, January 9 - 12, 2022, pages 2005–2031. SIAM, 2022

    2022

  34. [34]

    D. F. Rall and P. J. Slater. On location-domination numbers for certain classes of graphs. Congressus Numerantium, 45:97–106, 1984

    1984

  35. [35]

    Reidl, F

    F. Reidl, F. S. Villaamil, and K. S. Stavropoulos. Characterising bounded expansion by neigh- bourhood complexity.European Journal of Combinatorics, 75:152–168, 2019

    2019

  36. [36]

    A. R´ enyi. On random generating elements of a finite Boolean algebra.Acta Scientiarum Math- ematicarum Szeged, 22:75–81, 1961

    1961

  37. [37]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph minors. XX. Wagner’s conjecture.Journal of Combi- natorial Theory, Series B, 92(2):325–357, 2004

    2004

  38. [38]

    N. Sauer. On the density of families of sets.Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972

    1972

  39. [39]

    S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific Journal of Mathematics, 41(1):247–261, 1972

    1972

  40. [40]

    P. J. Slater. Domination and location in acyclic graphs.Networks, 17(1):55–64, 1987

    1987

  41. [41]

    P. J. Slater. Dominating and reference sets in a graph.Journal of Mathematical and Physical Sciences, 22(4):445–455, 1988

    1988

  42. [42]

    V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities.Theory of Probability & Its Applications, 16(2):264–280, 1971. 17

    1971