Pith. sign in

REVIEW

Graphs with many independent vertex cuts

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 2210.15151 v1 pith:KUOBAQG3 submitted 2022-10-27 math.CO

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

The cycles are the only $2$-connected graphs in which any two nonadjacent vertices form a vertex cut. We generalize this fact by proving that for every integer $k\ge 3$ there exists a unique graph $G$ satisfying the following conditions: (1) $G$ is $k$-connected; (2) the independence number of $G$ is greater than $k;$ (3) any independent set of cardinality $k$ is a vertex cut of $G.$ The edge version of this result does not hold. We also consider the problem when replacing independent sets by the periphery.

Discussion (0). Continue with ORCID to comment.

Pith tools