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

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

classification math.CO
keywords leastdegreesverticesalphagraphtherewhosewidetilde
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
Share X Bluesky LinkedIn Reddit HN
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 with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

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

    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)).