Pith. sign in

REVIEW 1 cited by

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 2311.18284 v1 pith:7CJUST5L submitted 2023-11-30 math.CO cs.DM

The Complement of the Djokovic-Winkler Relation

classification math.CO cs.DM
keywords thetaoverlinedistancesgraphrelationverticesclassescomplement
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original abstract

The Djokovi\'{c}-Winkler relation $\Theta$ is a binary relation defined on the edge set of a given graph that is based on the distances of certain vertices and which plays a prominent role in graph theory. In this paper, we explore the relatively uncharted ``reflexive complement'' $\overline\Theta$ of $\Theta$, where $(e,f)\in \overline\Theta$ if and only if $e=f$ or $(e,f)\notin \Theta$ for edges $e$ and $f$. We establish the relationship between $\overline\Theta$ and the set $\Delta_{ef}$, comprising the distances between the vertices of $e$ and $f$ and shed some light on the intricacies of its transitive closure $\overline\Theta^*$. Notably, we demonstrate that $\overline\Theta^*$ exhibits multiple equivalence classes only within a restricted subclass of complete multipartite graphs. In addition, we characterize non-trivial relations $R$ that coincide with $\overline\Theta$ as those where the graph representation is disconnected, with each connected component being the (join of) Cartesian product of complete graphs. The latter results imply, somewhat surprisingly, that knowledge about the distances between vertices is not required to determine $\overline\Theta^*$. Moreover, $\overline\Theta^*$ has either exactly one or three equivalence classes.

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. Minimal Isometric Embeddings of Graphs into Abelian Groups: Theory, Algorithms, and Applications to Signal Processing over Networks

    math.CO 2026-06 unverdicted novelty 7.0

    Every connected graph embeds isometrically into a Cayley graph of (Z_2)^k with k <= n-1 via new edge relations and a quotient labeling theorem, enabling group-based harmonic analysis on graphs.