On Delta‐Wye Reducibility of Toroidal Graphs
Journal of Graph Theory · 2026-07 · 112 (3) · 183-197
DOI: 10.1002/jgt.70028 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 20.03.2026. Verfasst von Isidoro Gitler und 1 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben.
Abstract (Originalsprache)
In 2006, Yu proved that there are at least 68 billion forbidden minors for delta‐wye reducibility. It is an open problem to prove that this is the complete list of forbidden minors. We prove that only eight graphs from Yu's list admit an embedding in the torus. These graphs are the Petersen family of graphs together with the graph obtained from the complete bipartite graph by deleting a perfect matching. Moreover, we show that graphs that admit a toroidal embedding of representativity greater than three contain one of these eight toroidal graphs as a minor. Hence, they are not delta‐wye reducible. In contrast, we prove that any graph that admits a toroidal embedding with representativity less than two is delta‐wye reducible; in fact, 1‐terminal reducible. We also prove that if admits a toroidal embedding without disjoint essential cycles, then is delta‐wye reducible. Finally, we show that if a graph has a toroidal embedding that is a 3‐connected triangulation of the torus, then is not delta‐wye reducible.
Zitieren
APA
Gitler, I., & Sandoval–Angeles, G. (2026). On Delta‐Wye Reducibility of Toroidal Graphs. Journal of Graph Theory, 112(3), 183-197. https://doi.org/10.1002/jgt.70028
Vancouver
Gitler I, Sandoval–Angeles G. On Delta‐Wye Reducibility of Toroidal Graphs. Journal of Graph Theory. 2026;112(3):183-197. doi:10.1002/jgt.70028
BibTeX
@article{Gitler2026,
author = {Gitler, Isidoro and Sandoval–Angeles, Gustavo},
title = {On Delta‐Wye Reducibility of Toroidal Graphs},
journal = {Journal of Graph Theory},
year = {2026},
volume = {112},
number = {3},
pages = {183--197},
doi = {10.1002/jgt.70028}
}
EUVIMED