Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The complement of the Djoković-Winkler relation
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0002-1620-5508
Stockholm University, Faculty of Science, Department of Mathematics.
Number of Authors: 42025 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 348, no 3, article id 114328Article in journal (Refereed) Published
Abstract [en]

The Djoković-Winkler relation Θ 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” Θ‾ of Θ, where (e,f)∈Θ‾ if and only if e=f or (e,f)∉Θ for edges e and f. We establish the relationship between Θ‾ and the set Δef, comprising the distances between the vertices of e and f and shed some light on the intricacies of its transitive closure ⁎Θ‾⁎. Notably, we demonstrate that ⁎Θ‾⁎ exhibits multiple equivalence classes only within a restricted subclass of complete multipartite graphs. In addition, we characterize non-trivial relations R that coincide with Θ‾ 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 ⁎Θ‾⁎. Moreover, ⁎Θ‾⁎ has either exactly one or three equivalence classes.

Place, publisher, year, edition, pages
2025. Vol. 348, no 3, article id 114328
Keywords [en]
Block graph, Cartesian product, Complete multipartite graph, Diameter, Distances, Equivalence relation
National Category
Discrete Mathematics Computer Sciences
Identifiers
URN: urn:nbn:se:su:diva-241540DOI: 10.1016/j.disc.2024.114328ISI: 001361459700001Scopus ID: 2-s2.0-85209256182OAI: oai:DiVA.org:su-241540DiVA, id: diva2:1949006
Available from: 2025-04-01 Created: 2025-04-01 Last updated: 2025-04-01Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Hellmuth, MarcThekkumpadan Puthiyaveedu, Sandhya

Search in DiVA

By author/editor
Hellmuth, MarcThekkumpadan Puthiyaveedu, Sandhya
By organisation
Department of Mathematics
In the same journal
Discrete Mathematics
Discrete MathematicsComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 39 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf