EUVIMEDEUVIMED entdecken
Crossref

Inversion diameter and treewidth

Yichen Wang, Haozhe Wang, Yuxuan Yang, Mei Lu

Discrete Mathematics & Theoretical Computer Science · 21.05.2026 · vol. 28:2 (Graph Theory)

DOI: 10.46298/dmtcs.16074 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 21.05.2026. Verfasst von Yichen Wang und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In an oriented graph $\overrightarrow{G}$, the inversion of a subset $X$ of vertices is the operation that reverses the orientation of all arcs with both end-vertices in $X$. The inversion graph of a graph $G$, denoted by $\mathcal{I}(G)$, is the graph whose vertices are orientations of $G$ in which two orientations $\overrightarrow{G_1}$ and $\overrightarrow{G_2}$ are adjacent if and only if there is an inversion transforming $\overrightarrow{G_1}$ into $\overrightarrow{G_2}$.The inversion diameter of a graph $G$ is the diameter of its inversion graph $\mathcal{I}(G)$, denoted by $\mathrm{diam}(\mathcal{I}(G))$.Havet, Hörsch, and Rambaud~(2024) first proved that for $G$ of treewidth $k$, $\mathrm{diam}(\mathcal{I}(G)) \le 2k$, and that there are graphs of treewidth $k$ with inversion diameter $k+2$.In this paper, we construct graphs of treewidth $k$ with inversion diameter $2k$, which implies that the previous upper bound $\mathrm{diam}(\mathcal{I}(G)) \le 2k$ is tight.Moreover, for graphs with maximum degree $Δ$, Havet, Hörsch, and Rambaud~(2024) proved $\mathrm{diam}(\mathcal{I}(G)) \le 2Δ-1$ and conjectured that $\mathrm{diam}(\mathcal{I}(G)) \le Δ$. We prove the conjecture when $Δ=3$ with the help of computer calculations.

Zitieren

APA

Wang, Y., Wang, H., Yang, Y., & Lu, M. (2026). Inversion diameter and treewidth. Discrete Mathematics & Theoretical Computer Science, vol. 28:2(Graph Theory). https://doi.org/10.46298/dmtcs.16074

Vancouver

Wang Y, Wang H, Yang Y, Lu M. Inversion diameter and treewidth. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:2(Graph Theory). doi:10.46298/dmtcs.16074

BibTeX
@article{Wang2026,
  author = {Wang, Yichen and Wang, Haozhe and Yang, Yuxuan and Lu, Mei},
  title = {Inversion diameter and treewidth},
  journal = {Discrete Mathematics & Theoretical Computer Science},
  year = {2026},
  volume = {vol. 28:2},
  number = {Graph Theory},
  doi = {10.46298/dmtcs.16074}
}
Kostenlos starten →