Pith. sign in

REVIEW 1 cited by

Cycles and paths through vertices whose degrees are at least the bipartite-hole-number

Not yet reviewed by Pith; the record is open.

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 2506.09750 v1 pith:3GJRODEA submitted 2025-06-11 math.CO

classification math.CO
keywords leastdegreesverticesalphagraphtherewhosewidetilde
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

The bipartite-hole-number of a graph $G$, denoted by $\widetilde{\alpha}(G)$, is the minimum integer $k$ such that there exist positive integers $s$ and $t$ with $s + t = k + 1$, satisfying the property that for any two disjoint sets $A, B \subseteq V(G)$ with $|A| = s$ and $|B| = t$, there is at least one edge between $A$ and $B$. In 1992, Bollob\'as and Brightwell, and independently Shi, proved that every $2$-connected graph of order $n$ contains a cycle passing through all vertices whose degrees are at least $\frac{n}{2}$. Motivated by their result, we show that in any $2$-connected graph of order $n$, there exists a cycle containing all vertices whose degrees are at least $\widetilde{\alpha}(G)$. Moreover, we prove that for any pair of vertices in a connected graph $G$, if their degrees are at least $\widetilde{\alpha}(G) + 1$, then there exists a path joining them that contains all vertices whose degrees are at least $\widetilde{\alpha}(G) + 1$. The results extend two existing ones.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Edge-disjoint Hamilton cycles under a bipartite-hole condition

    math.CO 2026-07 accept novelty 6.0 of 10

    f(a,k), the min-degree threshold for k edge-disjoint Hamilton cycles under bipartite-hole number ≤ a, equals Θ(a + k + ak/log(k+2)).

Pith tools