Cyclic Neighborhoods in Digraphs

Dieter Rautenbach; Thilo Hartel

REVIEW 2 major objections 5 minor 15 references

Cyclic Neighborhoods in Digraphs

T0 review · 2 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read In every strongly connected digraph where each vertex has a cyclic out-neighborhood and in-neighborhood, the arc count must be at least 7n/3, and strong 2-connectivity pushes the floor to 8n/3; both bounds are best-possible.

desk verdict Two genuinely new tight bounds for neighborhood-cyclic digraphs, with a fixable but load-bearing gap in the Theorem 3 proof. read the letter →

arxiv 2607.26606 v1 pith:LOVV2LCX submitted 2026-07-29 math.CO

Thilo Hartel , Dieter Rautenbach This is my paper · ORCID

classification math.CO MSC 05C2005C3505C40

keywords sparseseparatorsvertexcutscyclicneighborhoodsdigraphsstrongconnectivity2-connectivityextremalboundsdischargingmethod

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Let D be a digraph whose out-neighborhood and in-neighborhood at every vertex each contain a directed cycle. The paper establishes two tight lower bounds on the number of arcs of such a digraph: if D is strongly connected and has n≥5 vertices, then m≥7n/3, and if D is strongly 2-connected and n≥9, then m≥8n/3. Both bounds are best-possible, and the first has a complete equality characterization: extremal digraphs are built from disjoint complete digraphs of order 3 arranged in a directed cycle, with one arc between consecutive blocks. The motivation is the search for sparse separators: a digraph in which every neighborhood is cyclic is the natural obstruction to having an acyclic vertex cut, and these results show how strong connectivity combines with that obstruction to force density.

What carries the argument

The proof mechanism is discharging. Vertices are grouped by total degree into classes V4, V5, etc. For Theorem 2, each vertex of degree at least 5 sends a fraction of its excess charge to its neighbors in V4, and the local analysis of the possible shapes of D[V4]—isolated vertices, directed cycles, and directed paths—shows every vertex finishes with charge at least 14/3. Since total initial charge is 2m, this gives m≥7n/3. For Theorem 3, a four-phase discharging scheme defines 'demanding' pairs (u, σ) for vertices of degree 4 or 5 with out-degree or in-degree 2, and high-degree vertices send their demands along specific arcs so that every final charge is at least 16/3. The key structural inp

What would settle it

A concrete way to test the paper's central claim is to search for a strongly 2-connected neighborhood-cyclic digraph with n≥9 and m<8n/3; any such digraph would refute Theorem 3. More locally, one can try to construct a strongly 2-connected neighborhood-cyclic digraph containing a directed path P=u0...uℓ inside V4 with a single external vertex x=y and d_D(v)≤2ℓ+5, which would directly contradict the unproved degree estimate in Claim 2.

Watch

Extended reading notes

Core claim

The central claim, on the paper's own terms, is that the neighborhood-cyclic condition is strong enough to force linear density once connectivity is imposed. A neighborhood-cyclic digraph has minimum out-degree and in-degree at least 2, so m≥2n trivially; the paper proves that strong connectivity raises this to m≥7n/3 for n≥5, with equality characterized by the family D, and that strong 2-connectivity raises it further to m≥8n/3 for n≥9. For the second bound, the paper shows it is best-possible by adding the arcs of a directed cycle through the extremal blocks of the first construction. The proofs are discharging arguments that track how many arcs must exist around vertices of low degree, an

Load-bearing premise

In the proof of Theorem 3, Claim 2 asserts without an explicit argument that when a degree-4 path component P=u0...uℓ has its two outer neighbors x and y equal, the common doubly adjacent vertex v has total degree at least 2ℓ+6; the discharging estimates for vertices of degrees 6 through 12 rely on this bound, so if that step needs extra hypotheses, the 8n/3 conclusion may not follow.

Editorial extensions

If this is right

Every strongly connected neighborhood-cyclic digraph with n≥5 has m≥7n/3, improving the trivial m≥2n bound.
Every strongly 2-connected neighborhood-cyclic digraph with n≥9 has m≥8n/3, so the density threshold rises with connectivity.
The m≥7n/3 bound is tight exactly on the block-cycle family D: k≥2 disjoint complete digraphs of order 3 joined by one arc around a directed cycle.
The m≥8n/3 bound is also tight: a digraph realizing equality is obtained by taking a member of D and adding a directed cycle through vertices of degree 4.
As a direct contrapositive, any strongly connected neighborhood-cyclic digraph with fewer than 7n/3 arcs cannot be strongly connected, and any with fewer than 8n/3 arcs cannot be strongly 2-connected.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural next question, left implicit by the paper, is whether strong 3-connectivity or general k-connectivity forces an even larger linear slope, and whether the coefficients 7/3 and 8/3 are the beginning of a sequence depending on k.
The target charge 16/3 in the second proof suggests that the extremal obstruction is a degree-4 vertex whose two out-neighbors and two in-neighbors each need compensation; a similar charging perspective may transfer to the undirected cyclic-neighborhood problem that motivated the paper.
One could test whether the equality cases for the 8n/3 bound admit a structural description as clean as the family D, since the paper proves best-possibility by example but does not characterize all extremal digraphs.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Two genuinely new extremal bounds here, and the main ideas are worth engaging with. But the proof of the second theorem is not complete as written.

The paper shows that a strongly connected neighborhood-cyclic digraph on n vertices has at least 7n/3 arcs, and a strongly 2-connected one at least 8n/3; both bounds are tight, with explicit extremal families. The discharging setup is adapted to digraphs with separate in/out neighborhoods, and that adaptation is the real contribution. Theorem 2's proof is detailed and mostly convincing, and the extremal digraph description in D is concrete.

The soft spots are in proportion. Theorem 2's equality characterization is a one-sentence jump from local configurations to the global D in D; that needs at least a paragraph. More importantly, Claim 2 in the proof of Theorem 3 asserts that when x=y, d_D(v) >= 2*ell + 6 for the path component P. The text says only that this follows from strong connectivity of D-x. It does not follow immediately: the direct count gives 2*ell + 4, and the extra +2 requires an argument that every vertex of P has no neighbors outside P union {v,x} and that strong connectivity of D-x forces arcs from v to the outside set and back. That argument is plausible — the stress-test reconstruction fills it in — but it is not in the manuscript. Since Claims 7-9 repeatedly use degree thresholds derived from this bound, the proof of m >= 8n/3 is incomplete as written.

I don't think this is a counterexample to the theorem. The missing step is local and likely repairable. But it is exactly the kind of step that can hide a false subcase, and the authors should be asked to spell it out. The best-possible verification for the 8n/3 construction is also brief; I'd want that expanded.

Who is this for: extremal digraph theorists working on sparse separators and neighborhood conditions. Outside that subfield, limited impact. It deserves a serious referee — the techniques are nontrivial and the results would be cited if they hold. My recommendation: send to peer review with a request for a revised proof of Claim 2 and the equality characterization, rather than desk reject.

Referee Report

2 major / 5 minor

Summary. The paper studies digraphs in which, for every vertex, both the out-neighborhood and the in-neighborhood induce a subdigraph containing a directed cycle ("neighborhood-cyclic"). It proves two extremal lower bounds. Theorem 2: every strongly connected neighborhood-cyclic digraph of order n≥5 and size m satisfies m≥7n/3, with equality if and only if the digraph belongs to a specified family D formed by cyclically arranged complete digraphs ↔K3 with exactly one arc between consecutive blocks. Theorem 3: every strongly 2-connected neighborhood-cyclic digraph of order n≥9 satisfies m≥8n/3. Both bounds are claimed best-possible. The proofs use discharging: in Theorem 2, initial charge d_D(u) is redistributed to degree-4 vertices to show final charge at least 14/3; in Theorem 3, a four-phase discharging argument shows final charge at least 16/3, contradicting m<8n/3.

Significance. If the proofs are correct, these are the first tight extremal results for neighborhood-cyclic digraphs and give a substantive directed analogue of recent undirected results on sparse cuts and cyclic neighborhoods. The discharging arguments are intricate and self-contained, with no fitted parameters; the extremal examples are explicit, and Theorem 2 includes a full equality characterization. The main value is the pair of tight bounds and the associated extremal family. However, two proof passages need expansion before the central claims are fully supported: the x=y case in Claim 2 of Theorem 3, and the global patching step in the equality case of Theorem 2.

major comments (2)

[Theorem 3, Claim 2 (Proof of Theorem 3)] The x=y case of Claim 2 is asserted without proof: "If x=y, then, since D−x is strongly connected, we obtain that d_D(v)≥2ℓ+6." The arc count gives only 2ℓ+4. A proof is needed and can be supplied: since P is a component of D[V4], no vertex of P has an arc to/from x beyond the endpoint arcs x→u0 and uℓ→x, otherwise its degree would exceed 4. Since x∈V≥5 and n≥9, there is a vertex z outside {v}∪V(P)∪{x}. In D−x, vertices of P have no neighbours outside {v}∪V(P), so strong connectivity forces at least one arc from v to the outside and at least one arc from the outside to v; these two arcs add the missing +2. Please insert this or an equivalent argument. Claims 7–9 use degree thresholds derived from this bound, so this is load-bearing.
[Theorem 2, equality case (end of proof)] The final step "Since D is strongly-connected and n≥5, this implies that D∈D" is too compressed. The preceding paragraph proves only local alternatives for each degree-4 vertex. To establish the equality characterization one must argue globally: the K3 blocks are vertex-disjoint, there are no extra arcs between V≥5 and V4 beyond one incoming and one outgoing arc per block, the blocks are arranged in a directed cycle, and no other arcs exist. This patching is part of the theorem statement and should be proved explicitly.

minor comments (5)

[Theorem 2, discharging definition] The instruction "For every arc e ... move ... from u to v" should clarify that a double arc triggers two transfers, so that a vertex joined to u by a double arc receives twice the amount. This is the source of the factor 2 in later formulas (e.g., Case 2).
[Definition of D] The phrase "adding ... an arc from some vertex" should read "exactly one arc" for clarity, since the extremal family D permits exactly one arc between consecutive blocks.
[Figure 1 caption] The caption contains corrupted text: "Double arcs are depicted as q q-."
[Theorem 3, Claim 2] The line "Since D is neighborhood-cyclic, there is a vertex v such that V(P)⊆N+(v)∩N-(v)" repeats an argument from Theorem 2; a short justification or a reference to the earlier case would improve readability.
[Abstract/Introduction] Minor wording: "arc between" in the abstract and intro should probably be "arc from ... to ..." to avoid ambiguity about orientation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proofs are self-contained discharging arguments with no fitted parameters, no prediction-by-construction steps, and no load-bearing self-citations.

full rationale

The paper derives two extremal bounds for strongly connected or strongly 2-connected neighborhood-cyclic digraphs using explicit discharging arguments. The hypotheses (neighborhood-cyclic, strong connectivity, n bounds) do not include the target inequalities m ≥ 7n/3 or m ≥ 8n/3, and the extremal claims are supported by explicit constructions (D and the directed cycle added to D), not by uniqueness theorems or prior work by the authors. Self-citations appear only as background references in the introduction (e.g. [10], [14]) and are not used to justify the central arguments. The discharging estimates in the proof of Theorem 3 are local counting arguments; the potentially terse step in Claim 2, 'If x=y, then, since D−x is strongly connected, we obtain that d_D(v)≥2ℓ+6', is an unexpanded argument about degree lower bounds, not a case where the desired bound is assumed or fitted. A missing intermediate justification would be a correctness or exposition issue, not circularity. There is no renaming of a known empirical pattern as organization, no imported uniqueness theorem, and no ansatz smuggled in via citation. The central derivations are therefore self-contained, and the honest finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

Central claim rests on standard graph-theoretic facts: neighborhood-cyclic forces minimum in/out-degree 2; strong 2-connectivity is used via deletion of any vertex; discharging conserves total charge. There are no fitted constants and no new entities. The proof's only nonstandard objects are bookkeeping 'demand pairs' in the discharging procedure, not explanatory postulates.

assumptions (4)

domain assumption Neighborhood-cyclic implies δ^+(D), δ^-(D) ≥ 2, so every vertex has total degree at least 4.
Used at the start of both proofs to justify the partition V=V4∪V≥5.
standard math Strongly 2-connected means D−v is strongly connected for every vertex v.
Invoked throughout Theorem 3 to rule out configurations after deleting a vertex; this is the standard definition.
standard math Discharging conserves total charge: the sum of final charges equals the sum of initial degrees, which equals 2m.
Bridges the per-vertex lower bounds c(u)≥14/3 or c(u)≥16/3 to the arc count bounds in both theorems.
domain assumption In a strongly connected digraph of order at least 5, a proper nonempty vertex subset with no arcs leaving or entering it is impossible.
Used in Theorem 2 to exclude K3 components in D[V4] and in several Claim 1 arguments.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Cyclic Neighborhoods in Digraphs." pith.science (2026). https://pith.science/paper/LOVV2LCX

@misc{pith2026260726606,
  author       = {Pith},
  title        = {Pith review of: Cyclic Neighborhoods in Digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LOVV2LCX}},
  note         = {Machine review of arXiv:2607.26606}
}

abstract

Let $D$ be a digraph of order $n$ and size $m$ with the property that no out-neighborhood or in-neighborhood of any vertex is acyclic. We show that, if $D$ is strongly connected, then $m\geq 7n/3$, and, if $D$ is strongly $2$-connected, then $m\geq 8n/3$. Both results are best-possible.

Figures

Figures reproduced from arXiv: 2607.26606 by the authors.

**Figure 1.** A digraph of order 18 in D. Double arcs are depicted as q q ✲✛. Theorem 2. If D is a strongly connected and neighborhood-cyclic digraph with n ≥ 5 vertices and m arcs, then m ≥ 7 3 n (1) with equality in (1) if and only if D ∈ D. If D is in D and D0, . . . , Dk−1 are as above, then, for every i in [k − 1]0, there is a vertex vi in V (Di) with dD(vi) = 4, and adding the arcs of the directed cycle v0v1 . . . vk−1v0 to… view at source ↗

**Figure 2.** u is isolated in D[V4]. First, suppose that N + D (u) = N − D (u) as shown in the left of [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Directed cycle components of D[V4] of lengths 2, 3, and 4. dD(v) ≥ 6. Furthermore, dD(v) = 6 implies that mD(v, V4) ≤ dD(v) − 2, and dD(v) = 7 implies that mD(v, V4) ≤ dD(v) − 1. It follows that v sends 2 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Directed path components of D[V4] of lengths 1 and 2. Since dD(v) ≥ 2ℓ + 2, the vertex v sends 2 3 charge to each vertex on C, and the vertex w sends a positive amount of charge to u1. This implies that c(u1) > 14 3 and c(ui) ≥ 14 3 for every i ∈ [ℓ] \ {1}. In all thre…

**Figure 5.** Figure 5: for an illustration, r rr r r ✁ ✁ ✁ ❆ ❆ ❆ v u w ✁ ✁ ❆ ✁ ❆ ❆ ❆❯ ✲ ✲ ✁ ✁✕ x y ✁ ✁✕ ☛ ❯ ❆ ❆❑ ✲✛ [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]

**Figure 6.** Figure 6: for an illustration, rr r r ✁ ✁ ✁ ❆ ❆ ❆ v u w ❆ ❆ ❆ ❆❯ x✲ ✁ ✁✕ ☛ ❯ ❆ ❆❑ ✲✛ [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 3 linked inside Pith

[1]

Aubian, M

G. Aubian, M. Bonamy, R. Bourneuf, O. Fontaine, and L. Picasarri-Arrieta, On cuts of small chromatic number in sparse graphs, arXiv:2510.01791v1

arXiv
[2]

Bang-Jensen and G

J. Bang-Jensen and G. Z. Gutin,Digraphs, second edition, Springer Monographs in Math- ematics, Springer, London, 2009

2009
[3]

Bessy, J

S. Bessy, J. Rauch, D. Rautenbach, and U.S. Souza, Sparse vertex cutsets and the maximum degree, Electron. J. Combin.32(2025), no. 2, Paper No. 2.32, 11 pp

2025
[4]

Bogdanov, E

I.I. Bogdanov, E. Neustroeva, G. Sokolov, A. Volostnov, N. Russkin, and V. Voronov, On forest and bipartite cuts in sparse graphs, arXiv:2505.16179

arXiv
[5]

Botler, Y.S

F. Botler, Y.S. Couto, C.G. Fernandes, E.F. de Figueiredo, R. G´ omez, V.F. dos Santos, and C.M. Sato, Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs, arXiv:2411.17885

arXiv
[6]

Chen and X

G. Chen and X. Yu, A note on fragile graphs, Discrete Math.249(2002), no. 1-3, 41–43

2002
[7]

Chen, R.J

G. Chen, R.J. Faudree, and M.S. Jacobson, Fragile graphs with small independent cuts, J. Graph Theory41(2002), no. 4, 327–341

2002
[8]

Cheng, Y

K. Cheng, Y. Tang, and X. Zhan, Sparse graphs with an independent or foresty minimum vertex cut, Discrete Math.349(2026), no. 1, Paper No. 114658, 6 pp

2026

Show all 15 references

[9]

Chernyshev, J

V. Chernyshev, J. Rauch, and D. Rautenbach, Forest cuts in sparse graphs, Discrete Math. 348(2025), no. 11, Paper No. 114594, 6 pp

2025
[10]

Hartel, J

T. Hartel, J. Rauch, and D. Rautenbach, Degenerate Vertex Cuts in Sparse Graphs, arxiv:2512.21298
[11]

Kriesell, personal communication at the4th Workshop on Graphs, Algorithms and Machine Learning(Spain, 22-27.03.2026)

M. Kriesell, personal communication at the4th Workshop on Graphs, Algorithms and Machine Learning(Spain, 22-27.03.2026)

2026
[12]

Le and F

V.B. Le and F. Pfender, Extremal graphs having no stable cutsets, Electron. J. Combin. 20(2013), no. 1, Paper 35, 7 pp

2013
[13]

C. Li, Y. Tang, and X. Zhan, The minimum size of a 3-connected locally nonforesty graph, arXiv:2410.23702

arXiv
[14]

Rauch and D

J. Rauch and D. Rautenbach, Revisiting Extremal Graphs Having No Stable Cutsets, Electron. J. Combin.32(2025), no. 4, P4.25

2025
[15]

Schneider and T

S. Schneider and T. Ueckerdt, Number of Edges in 3-Connected Graphs with Cyclic Neigh- borhoods, arXiv:2511.10717. 19

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

Aubian, M

G. Aubian, M. Bonamy, R. Bourneuf, O. Fontaine, and L. Picasarri-Arrieta, On cuts of small chromatic number in sparse graphs, arXiv:2510.01791v1

arXiv

[2] [2]

Bang-Jensen and G

J. Bang-Jensen and G. Z. Gutin,Digraphs, second edition, Springer Monographs in Math- ematics, Springer, London, 2009

2009

[3] [3]

Bessy, J

S. Bessy, J. Rauch, D. Rautenbach, and U.S. Souza, Sparse vertex cutsets and the maximum degree, Electron. J. Combin.32(2025), no. 2, Paper No. 2.32, 11 pp

2025

[4] [4]

Bogdanov, E

I.I. Bogdanov, E. Neustroeva, G. Sokolov, A. Volostnov, N. Russkin, and V. Voronov, On forest and bipartite cuts in sparse graphs, arXiv:2505.16179

arXiv

[5] [5]

Botler, Y.S

F. Botler, Y.S. Couto, C.G. Fernandes, E.F. de Figueiredo, R. G´ omez, V.F. dos Santos, and C.M. Sato, Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs, arXiv:2411.17885

arXiv

[6] [6]

Chen and X

G. Chen and X. Yu, A note on fragile graphs, Discrete Math.249(2002), no. 1-3, 41–43

2002

[7] [7]

Chen, R.J

G. Chen, R.J. Faudree, and M.S. Jacobson, Fragile graphs with small independent cuts, J. Graph Theory41(2002), no. 4, 327–341

2002

[8] [8]

Cheng, Y

K. Cheng, Y. Tang, and X. Zhan, Sparse graphs with an independent or foresty minimum vertex cut, Discrete Math.349(2026), no. 1, Paper No. 114658, 6 pp

2026