Skip to content
DraconiticResearch
Search Sources API
190,851 studies31 sourcesUpdated 56 min ago
PreprintarXiv licencearXiv

A complete classification of metrizable and strictly metrizable theta graphs

  • Guangfu Wang
Open at sourcePDFDOICite

Abstract

Cizma and Linial asked for a classification of the metrizable theta graphs. We solve both their problem and its strict analogue. For a≤ b≤ c, the theta graph Θa,b,c is metrizable if and only if a≤ 2 or (a,b,c)=(3,3,3), and it is strictly metrizable if and only if a≤2. Thus Θ3,3,3 is precisely the exceptional theta graph that is metrizable but not strictly metrizable. The negative directions follow from the known obstructions Θ3,3,4 and Θ3,3,3 together with topological-minor closure. The positive direction is constructive. Consistency turns the possible detours through a length-two arm into compatible Ferrers relations, which are represented by one-dimensional potentials; all resulting shortest-path comparisons have positive slack. The exceptional ordinary-metrizable graph Θ3,3,3 is handled by a two-threshold weak Ferrers representation. The proof is structural, yields rational edge lengths algorithmically, and uses no enumeration of path systems.

Related

  1. Classification of strictly resistance nonnegative graphs
    Hailey Jay Garcia
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. An e-positive classification for complete multipartite graphs
    Ariel Y. Sun, David G. L. Wang, Watson Z. Y. Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A complete classification of perfect state transfer in Grover walks on abelian Cayley graphs
    Koushik Bhakta, Bikash Bhattacharjya
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsQuantum physics & quantum informationarXiv
  4. Strictly positive optimal Hardy weights on manifolds and graphs via Green potential
    Ujjal Das, Matthias Keller, Yehuda Pinchover
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  5. Counting graphs admitting a strictly matched involution
    Stephan Dominique Andres, Igor Režan
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{wang2026complete,
  title = {{A complete classification of metrizable and strictly metrizable theta graphs}},
  author = {Guangfu Wang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2606.16357},
  eprint = {2606.16357},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.16357},
}
RIS
TY  - UNPB
TI  - A complete classification of metrizable and strictly metrizable theta graphs
AU  - Guangfu Wang
PY  - 2026
DA  - 2026/09/09
PB  - arXiv
DO  - 10.48550/arxiv.2606.16357
UR  - https://arxiv.org/abs/2606.16357
AB  - Cizma and Linial asked for a classification of the metrizable theta graphs. We solve both their problem and its strict analogue. For a≤ b≤ c, the theta graph Θ_a,b,c is metrizable if and only if a≤ 2 or (a,b,c)=(3,3,3), and it is strictly metrizable if and only if a≤2. Thus Θ_3,3,3 is precisely the exceptional theta graph that is metrizable but not strictly metrizable. The negative directions follow from the known obstructions Θ_3,3,4 and Θ_3,3,3 together with topological-minor closure. The positive direction is constructive. Consistency turns the possible detours through a length-two arm into compatible Ferrers relations, which are represented by one-dimensional potentials; all resulting shortest-path comparisons have positive slack. The exceptional ordinary-metrizable graph Θ_3,3,3 is handled by a two-threshold weak Ferrers representation. The proof is structural, yields rational edge lengths algorithmically, and uses no enumeration of path systems.
ER  -