Pith. sign in

REVIEW 3 cited by

The minimum size of a $3$-connected locally nonforesty graph

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2410.23702 v1 pith:5HGTKLER submitted 2024-10-31 math.CO

Chengli Li , Yurui Tang , Xingzhi Zhan This is my paper · ORCID
classification math.CO
keywords graphlocallynonforestyconnectedlocalordersizesubgraph
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

A local subgraph of a graph is the subgraph induced by the neighborhood of a vertex. Thus a graph of order $n$ has $n$ local subgraphs. A graph $G$ is called locally nonforesty if every local subgraph of $G$ contains a cycle. Recently, in studying forest cuts of a graph, Chernyshev, Rauch and Rautenbach posed the conjecture that if $n$ and $m$ are the order and size of a $3$-connected locally nonforesty graph respectively, then $m\ge 7(n-1)/3.$ We solve this problem by determining the minimum size of a $3$-connected locally nonforesty graph of order $n.$ It turns out that the conjecture does not hold.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Cyclic Neighborhoods in Digraphs

    math.CO 2026-07 conditional novelty 6.0 of 10

    Every strongly connected digraph with cyclic in/out-neighborhoods has at least 7n/3 arcs; every strongly 2-connected such digraph has at least 8n/3 arcs, and both bounds are tight.

  2. The minimum size of a $k$-connected locally nonforesty graph

    math.CO 2025-01 conditional novelty 6.0 of 10

    The minimum size of a k-connected locally nonforesty graph of order n is determined exactly for k=4, k=2 and k=1, and equals ceil(kn/2) for k at least 5.

  3. Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs

    math.CO 2024-11 conditional novelty 6.0 of 10

    Connected graphs with fewer than 9/4 n - 15/4 edges always have a vertex cut inducing a forest, improving on the previous 11/5 n - 18/5 bound toward the conjectured 3n - 6.

Pith tools