EUVIMEDEUVIMED entdecken
Crossref

On Delta‐Wye Reducibility of Toroidal Graphs

Isidoro Gitler, Gustavo Sandoval–Angeles

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →