pith. sign in

arxiv: 2501.00419 · v2 · submitted 2024-12-31 · 🧮 math.CO

Solution to a 3-path isolation problem for subcubic graphs

Karl Bartolo , Peter Borg , Dayle Scicluna This is my paper

Pith reviewed 2026-05-23 06:29 UTC · model grok-4.3

classification 🧮 math.CO
keywords 3-path isolation numbersubcubic graphsinduced 6-cyclesisolation numberP3graph theorydomination
0
0 comments X

The pith

Subcubic graphs without induced 6-cycles have 3-path isolation number at most n/4 except for twelve specific small graphs.

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

The paper proves that if G is subcubic and contains no induced 6-cycle, then the 3-path isolation number ι(G,P₃) is at most n/4 unless G is one of twelve particular graphs on 3, 7, 11 or 15 vertices. This settles the question whether the weaker general bound of 2n/7 is caused solely by induced 6-cycles, at least inside the subcubic case. Earlier results had established the n/4 bound when 6-cycles are forbidden outright or when both induced 5-cycles and induced 6-cycles are absent; the present work isolates the effect of induced 6-cycles for degree-3 graphs. A reader cares because the result shows how the local absence of one cycle type controls the size of a smallest isolating set for all 3-paths in sparse graphs.

Core claim

If G is subcubic and has no induced 6-cycles, then ι(G,P₃) ≤ n/4 unless G is a copy of one of 12 particular graphs whose orders are 3, 7, 11 and 15. The bound is sharp.

What carries the argument

The 3-path isolation number ι(G,P₃), the smallest size of a vertex set D whose closed neighbourhood intersects the vertex set of every 3-vertex path so that G − N[D] contains no two intersecting edges.

If this is right

  • The general 2n/7 bound obtained in earlier work is forced by the presence of induced 6-cycles.
  • For every subcubic graph without induced 6-cycles the isolation number is at most n/4 except for the twelve exceptions.
  • The twelve listed graphs achieve equality, so the bound cannot be improved.
  • Subcubic graphs require separate analysis from graphs of higher maximum degree for this isolation parameter.
  • Induced 6-cycles are the only cycle obstructions that push the isolation number above n/4 in the subcubic setting.

Where Pith is reading between the lines

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

  • The same n/4 bound may hold for all graphs (not necessarily subcubic) that avoid induced 6-cycles, but the paper leaves this open.
  • Enumeration or computer search on larger orders could confirm there are no further exceptions beyond the twelve listed.
  • Similar isolation results might be provable under other forbidden induced subgraphs that limit local density.

Load-bearing premise

The structural properties of subcubic graphs without induced 6-cycles permit only finitely many exceptions to the n/4 bound, and all of them appear among the twelve listed graphs of order at most 15.

What would settle it

A subcubic graph with no induced 6-cycle that is not one of the twelve listed graphs yet satisfies ι(G,P₃) > n/4.

Figures

Figures reproduced from arXiv: 2501.00419 by Dayle Scicluna, Karl Bartolo, Peter Borg.

Figure 1
Figure 1. Figure 1: Subcubic 7-vertex graphs with no induced 6-cycles and P3-isolation number 2. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: G11, a subcubic 11-vertex graph with no induced 6-cycles and with P3-isolation number 3. 7 8 6 7 5 6 8 9 9 10 4 4 10 11 3 3 11 12 2 2 1 1 12 5 13 13 14 14 15 15 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: G15, a subcubic 15-vertex graph with no induced 6-cycles and with P3-isolation number 4. 2 Proof of Theorem 1 We now prove Theorem 1. We often use the following two lemmas from [2]. Lemma 1 ([2]). If G is a graph, F is a set of graphs, X ⊆ V (G), and Y ⊆ N[X], then ι(G, F) ≤ |X| + ι(G − Y, F). A component of a graph G is a maximal connected subgraph of G. Clearly, the components of G are pairwise vertex-di… view at source ↗
read the original abstract

The $3$-path isolation number of a connected $n$-vertex graph $G$, denoted by $\iota(G,P_3)$, is the size of a smallest subset $D$ of the vertex set of $G$ such that the closed neighbourhood $N[D]$ of $D$ in $G$ intersects the vertex sets of the $3$-vertex paths of $G$, meaning that no two edges of $G-N[D]$ intersect. If $G$ is not a $3$-path or a $3$-cycle or a $6$-cycle, then $\iota(G,P_3) \leq 2n/7$. This was proved by Zhang and Wu, and independently by Borg in a slightly extended form. The bound is attained by infinitely many connected graphs having induced $6$-cycles. Huang, Zhang and Jin showed that if $G$ has no $6$-cycles, or $G$ has no induced $5$-cycles and no induced $6$-cycles, then $\iota(G,P_3) \leq n/4$ unless $G$ is a $3$-path or a $3$-cycle or a $7$-cycle or an $11$-cycle. They asked if the bound still holds asymptotically for connected graphs having no induced $6$-cycles. Thus, the problem essentially is whether induced $6$-cycles solely account for the difference between the two bounds. In this paper, we solve this problem for subcubic graphs, which need to be treated differently from other graphs. We show that if $G$ is subcubic and has no induced $6$-cycles, then $\iota(G,P_3) \leq n/4$ unless $G$ is a copy of one of $12$ particular graphs whose orders are $3$, $7$, $11$ and $15$. The bound is sharp.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript proves that if G is a subcubic n-vertex graph with no induced 6-cycle, then the 3-path isolation number ι(G,P₃) satisfies ι(G,P₃) ≤ n/4 unless G is one of 12 specific exceptional graphs on 3, 7, 11 or 15 vertices. The bound is shown to be sharp, resolving the subcubic case of a question posed by Huang, Zhang and Jin.

Significance. If the proof is complete, the result establishes a sharp n/4 bound for ι(G,P₃) in the absence of induced C₆ within the subcubic class, demonstrating that induced 6-cycles alone account for the gap between the general 2n/7 bound and the n/4 bound. It supplies a finite list of exceptions and thereby gives a precise structural characterization for this parameter in subcubic graphs.

major comments (1)
  1. [Main theorem and its proof (the section establishing completeness of the exception list)] The central claim rests on the assertion that the 12 listed graphs are the only exceptions. The reduction or case-analysis argument (whatever section contains the exhaustive treatment of degree-2/degree-3 configurations while forbidding induced C₆) must explicitly show both that every graph of order >15 admits a 3-path isolating set of size ≤ n/4 and that no additional exceptions exist among the finitely many graphs of order ≤15. Any gap in the local-configuration enumeration would allow an undetected counter-example.
minor comments (2)
  1. The notation for the 12 exceptional graphs should be standardized (e.g., explicit drawings or adjacency lists) so that a reader can immediately verify they are subcubic and C₆-free.
  2. A short table summarizing the orders and ι-values of the 12 exceptions would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of the result and for highlighting the importance of establishing the completeness of the exception list. We address the single major comment below.

read point-by-point responses

  1. Referee: [Main theorem and its proof (the section establishing completeness of the exception list)] The central claim rests on the assertion that the 12 listed graphs are the only exceptions. The reduction or case-analysis argument (whatever section contains the exhaustive treatment of degree-2/degree-3 configurations while forbidding induced C₆) must explicitly show both that every graph of order >15 admits a 3-path isolating set of size ≤ n/4 and that no additional exceptions exist among the finitely many graphs of order ≤15. Any gap in the local-configuration enumeration would allow an undetected counter-example.

    Authors: The proof in Section 3 proceeds by induction on n, with a complete case analysis of all possible degree-2 and degree-3 configurations in a subcubic graph with no induced C₆. For every such configuration that can occur when n > 15, the analysis identifies a reducible structure whose removal yields a smaller graph to which the inductive hypothesis applies, producing an isolating set of size at most n/4. The base cases for n ≤ 15 are settled by exhaustive enumeration of all connected subcubic graphs on at most 15 vertices that avoid induced 6-cycles; this enumeration confirms that precisely the 12 listed graphs fail the bound. Both requirements are therefore established explicitly by the case analysis and the finite check. revision: no

Circularity Check

0 steps flagged

Independent structural proof; no reduction to inputs or self-citation chain

full rationale

The paper establishes the bound ι(G,P₃) ≤ n/4 for subcubic G with no induced C₆ (except 12 listed graphs) via direct case analysis on vertex degrees and forbidden induced subgraphs. No parameter is fitted to data and then renamed as a prediction; no central premise reduces to a self-citation whose content is unverified; the exception list is generated by the proof's exhaustive local configuration check rather than assumed. Prior citations (Zhang-Wu, Borg, Huang et al.) supply context for the 2n/7 and n/4 bounds but are not load-bearing for the subcubic case. The derivation is self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The result rests on standard definitions of closed neighborhood and induced subgraphs from prior literature; no free parameters, invented entities or ad-hoc axioms are introduced in the abstract statement.

pith-pipeline@v0.9.0 · 5881 in / 1141 out tokens · 36222 ms · 2026-05-23T06:29:52.601042+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    Bartolo, P

    K. Bartolo, P. Borg and D. Scicluna, Isolation of squares in graphs, Discrete Math. 347 (2024), paper 114161

    work page 2024

  2. [2]

    Borg, Isolation of cycles, Graphs Combin

    P. Borg, Isolation of cycles, Graphs Combin. 36 (2020), 6 31–637

    work page 2020

  3. [3]

    Borg, Isolation of connected graphs, Discrete Appl

    P. Borg, Isolation of connected graphs, Discrete Appl. M ath. 339 (2023), 154–165

    work page 2023

  4. [4]

    Borg, Isolation of regular graphs, stars and k-chromatic graphs, arXiv:2303.13709 [math.CO]

    P. Borg, Isolation of regular graphs, stars and k-chromatic graphs, arXiv:2303.13709 [math.CO]

    work page arXiv

  5. [5]

    P. Borg, K. Fenech and P. Kaemawichanurat, Isolation of k-cliques, Discrete Math. 343 (2020), paper 111879. 20

    work page 2020

  6. [6]

    P. Borg, K. Fenech and P. Kaemawichanurat, Isolation of k-cliques II, Discrete Math. 345 (2022), paper 112641

    work page 2022

  7. [7]

    Borg and P

    P. Borg and P. Kaemawichanurat, Partial domination of ma ximal outerplanar graphs, Discrete Appl. Math. 283 (2020), 306–314

    work page 2020

  8. [8]

    Borg and P

    P. Borg and P. Kaemawichanurat, Extensions of the Art Gal lery Theorem, Ann. Comb. 27 (2023), 31–50

    work page 2023

  9. [9]

    Boyer and W

    G. Boyer and W. Goddard, Disjoint isolating sets and grap hs with maximum iso- lation number, Discrete Appl. Math. 356 (2024), 110–116

    work page 2024

  10. [10]

    Campos and Y

    C.N. Campos and Y. Wakabayashi, On dominating sets of ma ximal outerplanar graphs, Discrete Appl. Math. 161 (2013), 330–335

    work page 2013

  11. [11]

    Caro and A

    Y. Caro and A. Hansberg, Partial domination - the isolat ion number of a graph, Filomat 31:12 (2017), 3925–3944

    work page 2017

  12. [12]

    Chvátal, A combinatorial theorem in plane geometry, J

    V. Chvátal, A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B 18 (1975), 39–41

    work page 1975

  13. [13]

    Cockayne, Domination of undirected graphs – A surv ey, Lecture Notes in Mathematics, vol

    E.J. Cockayne, Domination of undirected graphs – A surv ey, Lecture Notes in Mathematics, vol. 642, Springer, 1978, 141–147

    work page 1978

  14. [14]

    Cockayne and S.T

    E.J. Cockayne and S.T. Hedetniemi, Towards a theory of d omination in graphs, Networks 7 (1977), 247–261

    work page 1977

  15. [15]

    J. Chen, Y. Liang, C. Wang and S. Xu, Algorithmic aspects of {Pk}-isolation in graphs and extremal graphs for a {P3}-isolation bound, Inf. Process. Lett. 187 (2025), paper 106521

    work page 2025

  16. [16]

    Q. Cui, J. Zhang and L. Zhong, Extremal graphs for the K1,2-isolation number of graphs, Bull. Malays. Math. Sci. Soc. 47 (2024), paper 115

    work page 2024

  17. [17]

    Favaron and P

    O. Favaron and P. Kaemawichanurat, Inequalities betwe en the Kk-isolation num- ber and the independent Kk-isolation number of a graph, Discrete Appl. Math. 289 (2021), 93–97

    work page 2021

  18. [18]

    Dorfling, J.H

    M. Dorfling, J.H. Hattingh and E. Jonck, Total dominatio n in maximal outerpla- nar graphs II, Discrete Appl. Math. 339 (2016), 1180–1188

    work page 2016

  19. [19]

    Dorfling, J.H

    M. Dorfling, J.H. Hattingh and E. Jonck, Total dominatio n in maximal outerpla- nar graphs, Discrete Appl. Math. 217 (2017), 506–511

    work page 2017

  20. [20]

    Haynes, S.T

    T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamen tals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998

    work page 1998

  21. [21]

    Haynes, S.T

    T.W. Haynes, S.T. Hedetniemi and P.J. Slater (Editors) , Domination in Graphs: Advanced Topics, Marcel Dekker, Inc., New York, 1998. 21

    work page 1998

  22. [22]

    Hedetniemi and R.C

    S.T. Hedetniemi and R.C. Laskar (Editors), Topics on Do mination, in: Annals of Discrete Mathematics, vol. 48, North-Holland Publishin g Co., Amsterdam, 1991, Reprint of Discrete Math. 86 (1990), no. 1–3

    work page 1991

  23. [23]

    Hedetniemi and R.C

    S.T. Hedetniemi and R.C. Laskar, Bibliography on domin ation in graphs and some basic definitions of domination parameters, Discrete Math. 86 (1990), 257–277

    work page 1990

  24. [24]

    Henning, A survey of selected recent results on tot al domination in graphs, Discrete Math

    M.A. Henning, A survey of selected recent results on tot al domination in graphs, Discrete Math. 309 (2009), 32–63

    work page 2009

  25. [25]

    Huang, G

    Y. Huang, G. Zhang and X. Jin, New results on the 1-isolation number of graphs without short cycles, arXiv:2308.00581 [math.CO]

    work page arXiv

  26. [26]

    M. A. Henning and P. Kaemawichanurat, Semipaired domin ation in maximal out- erplanar graphs, J. Comb. Optim. 38 (2019), 911–926

    work page 2019

  27. [27]

    Lemańska, M

    M. Lemańska, M. Mora and M.J. Souto–Salorio, Graphs wit h isolation number equal to one third of the order, Discrete Math. 347 (2024), pa per 113903

    work page 2024

  28. [28]

    Lemańska, R

    M. Lemańska, R. Zuazua and P. Żyliński, Total dominatin g sets in maximal out- erplanar graphs, Graphs Combin. 33 (2017), 991–998

    work page 2017

  29. [29]

    Z. Li, E. Zhu, Z. Shao and J. Xu, On dominating sets of maxi mal outerplanar and planar graphs, Discrete Appl. Math. 198 (2016), 164–169

    work page 2016

  30. [30]

    L. R. Matheson and R. E. Tarjan, Dominating sets in plana r graphs, European J. of Combin. 17 (1996), 565–568

    work page 1996

  31. [31]

    McKay, https://users.cecs.anu.edu.au/~bdm/data/graphs.html, ac- cessed 30/12/2024

    B. McKay, https://users.cecs.anu.edu.au/~bdm/data/graphs.html, ac- cessed 30/12/2024

    work page 2024

  32. [32]

    Ore, Theory of graphs, American Mathematical Societ y Colloquium Publica- tions, vol

    O. Ore, Theory of graphs, American Mathematical Societ y Colloquium Publica- tions, vol. 38, American Mathematical Society, Providence , R.I., 1962

    work page 1962

  33. [33]

    Tokunaga, Dominating sets of maximal outerplanar gr aphs, Discrete Appl

    S. Tokunaga, Dominating sets of maximal outerplanar gr aphs, Discrete Appl. Math. 161 (2013), 3097–3099

    work page 2013

  34. [34]

    Tokunaga, T

    S. Tokunaga, T. Jiarasuksakun and P. Kaemawichanurat, Isolation number of maximal outerplanar graphs, Discrete Appl. Math. 267 (2019 ), 215–218

    work page 2019

  35. [35]

    West, Introduction to graph theory, second ed., Pr entice Hall, 1996

    D.B. West, Introduction to graph theory, second ed., Pr entice Hall, 1996

    work page 1996

  36. [36]

    Yan, Isolation of the diamond graph, Bull

    J. Yan, Isolation of the diamond graph, Bull. Malays. Ma th. Sci. Soc. 45 (2022), 1169–1181

    work page 2022

  37. [37]

    Yu and B

    H. Yu and B. Wu, Admissible property of graphs in terms of radius, Graphs Combin. 38 (2022), paper 6

    work page 2022

  38. [38]

    Zhang and B

    G. Zhang and B. Wu, K1,2-isolation in graphs, Discrete Appl. Math. 304 (2021), 365–374

    work page 2021

  39. [39]

    Żyliński, Vertex-edge domination in graphs, Aequat

    P. Żyliński, Vertex-edge domination in graphs, Aequat . Math. 93 (2019), 735–742. 22

    work page 2019