Pith Number

pith:Q4VWJWKO

pith:2026:Q4VWJWKOYTKZM6NLJ7VXI3VOID

not attested not anchored not stored refs resolved

The 2-Quasi-Regularizability Conjecture and Independence Polynomials of Wp Graphs

Kevin Pereyra

A connected W_2 graph is 2-quasi-regularizable exactly when n(G) is at least 3α(G).

arxiv:2605.14076 v1 · 2026-05-13 · math.CO

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{Q4VWJWKOYTKZM6NLJ7VXI3VOID}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We prove the conjecture. The key point is a local expansion theorem: if G is connected and belongs to W_2, then every non-maximum independent set A satisfies |N_G(A)| ≥ 2|A|. Thus the only possible obstruction to 2-quasi-regularizability in a connected W_2 graph comes from maximum independent sets, where the condition is exactly n(G)−α(G)≥2α(G).

C2weakest assumption

The assumption that G is connected and lies in the class W_2; the local expansion theorem is stated only under these hypotheses, so the reduction to the numerical condition on maximum independent sets holds only inside this restricted family.

C3one line summary

Proves the 2-quasi-regularizability conjecture for connected W_2 graphs via a local expansion theorem and derives explicit log-concavity and unimodality regions for their independence polynomials.

References

37 extracted · 37 resolved · 2 Pith anchors

[1] Y. Alavi, P. J. Malde, A. J. Schwenk, and P. Erdos,The vertex independence sequence of a graph is not constrained, Congressus Numerantium58(1987), 15–23 1987

[2] Berge,Some common properties for regularizable graphs, edge-critical graphs and B-graphs, Annals of Discrete Mathematics12(1982), 31–44 1982

[3] J. I. Brown, C. A. Hickman, and R. J. Nowakowski,On the location of roots of independence polynomials, Journal of Algebraic Combinatorics19(2004), 273–282 2004

[4] S.-Y. Chen and H.-J. Wang,Unimodality of very well-covered graphs, Ars Combina- toria97A(2010), 509–529 2010

[5] M. Chudnovsky and P. Seymour,The roots of the independence polynomial of a claw-free graph, Journal of Combinatorial Theory, Series B97(2007), 350–357 2007

Formal links

1 machine-checked theorem link

Receipt and verification

First computed	2026-05-17T23:39:12.362638Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

872b64d94ec4d59679ab4feb746eae40c0dc283ab7cde9ea08de03cdf7ba1f22

Aliases

arxiv: 2605.14076 · arxiv_version: 2605.14076v1 · doi: 10.48550/arxiv.2605.14076 · pith_short_12: Q4VWJWKOYTKZ · pith_short_16: Q4VWJWKOYTKZM6NL · pith_short_8: Q4VWJWKO

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/Q4VWJWKOYTKZM6NLJ7VXI3VOID \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 872b64d94ec4d59679ab4feb746eae40c0dc283ab7cde9ea08de03cdf7ba1f22

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "e5e5fda998c68d7c7b1af1b503f218b5100ac8a92839827fad28fc04c3f4362c",
    "cross_cats_sorted": [],
    "license": "http://creativecommons.org/publicdomain/zero/1.0/",
    "primary_cat": "math.CO",
    "submitted_at": "2026-05-13T19:55:00Z",
    "title_canon_sha256": "0fcd5d1f0397675ea15b63c2889b612f4ddbeb9f39dd53ca231aaab28455f5b3"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.14076",
    "kind": "arxiv",
    "version": 1
  }
}