Pith. sign in

REVIEW 1 cited by

The $n/2$-bound for locating-dominating sets in subcubic graphs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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 2406.19278 v1 pith:TMQH4GPU submitted 2024-06-27 math.CO

Dipayan Chakraborty , Anni Hakanen , Tuomo Lehtilä This is my paper · ORCID
classification math.CO
keywords graphssubcubictwinsbounddegreeholdsopensame
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

The location-domination number is conjectured to be at most half of the order for twin-free graphs with no isolated vertices. We prove that this conjecture holds and is tight for subcubic graphs. We also show that the same upper bound holds for subcubic graphs with open twins of degree 3 and closed twins of any degree, but not for subcubic graphs with open twins of degree 1 or 2. These results then imply that the same upper bound holds for all cubic graphs (with or without twins) except $K_4$ and $K_{3,3}$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Structural Parameterization of Locating-Dominating Set and Test Cover

    cs.DS 2024-11 reject novelty 6.0 of 10

    New parameterized algorithms and a feedback-edge-set kernel for Locating-Dominating Set and Test Cover are claimed, together with quadratic-bit incompressibility results.

Pith tools