Pith Number

pith:NYSKETAX

pith:2026:NYSKETAXSSUZUYYHVAS7MNGUNX

not attested not anchored not stored refs resolved

Optimization problem for star covers of graphs without four cycles

Damjana Kokol Bukov\v{s}ek, Helena \v{S}migoc, Polona Oblak

For graphs without four-cycles the SNT-rank is given by the minimum number of bipartite components in a star cover.

arxiv:2605.17383 v1 · 2026-05-17 · math.CO · math.RA

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

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{NYSKETAXSSUZUYYHVAS7MNGUNX}

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 consider a family of graphs that do not contain four cycles, and develop an algorithm to determine the SNT-rank of such graphs.

C2weakest assumption

The restriction to C4-free graphs is sufficient to make the optimization problem of counting bipartite components in a star cover both well-defined and algorithmically solvable.

C3one line summary

Develops an algorithm to compute the SNT-rank of C4-free graphs by optimizing the number of bipartite components in star covers.

References

14 extracted · 14 resolved · 0 Pith anchors

[1] LeRoy B. Beasley. Preservers of term ranks and star cover numbers of symmetric matrices.Electron. J. Linear Algebra, 31:549–564, 2016 2016

[2] Beasley and Thomas J 2009

[3] D. de Caen, D. A. Gregory, and N. J. Pullman. The Boolean rank of zero-one matrices. InProceedings of the Third Caribbean Conference on Combinatorics and Computing (Bridgetown, 1981), pages 169–173. U 1981

[4] Springer, Heidelberg, fourth edition, 2010 2010

[5] Covering graphs with few complete bipartite subgraphs.Theoret 2045

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-05-20T00:03:55.826247Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

6e24a24c1794a99a6307a825f634d46de59602cfa7b4ad14e677731e9df0eccb

Aliases

arxiv: 2605.17383 · arxiv_version: 2605.17383v1 · doi: 10.48550/arxiv.2605.17383 · pith_short_12: NYSKETAXSSUZ · pith_short_16: NYSKETAXSSUZUYYH · pith_short_8: NYSKETAX

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/NYSKETAXSSUZUYYHVAS7MNGUNX \
  | 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: 6e24a24c1794a99a6307a825f634d46de59602cfa7b4ad14e677731e9df0eccb

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "3a01e8db8d89238d744f2eff34881d51aedc3523a1f441261fc1f728ed232ead",
    "cross_cats_sorted": [
      "math.RA"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "math.CO",
    "submitted_at": "2026-05-17T10:56:03Z",
    "title_canon_sha256": "be4f4a975f1b6fd416dbcee97acd3145da2d7b14742c780be489bb9d32694fd1"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.17383",
    "kind": "arxiv",
    "version": 1
  }
}