Converse-invariant orientations of trees with maximum degree at least three
Converse-invariant orientations of trees with maximum degree at least three
Let be an orientation of a tree with maximum degree at least . Write for the converse orientation, and say that is converse invariant when it has the same number of copies in every tournament as . The bridge-mirroring operation is the operation defined in the paper that mirrors an oriented bridge; recursively applying it produces orientations from an orientation of a path.
Conjecture on converse-invariant tree orientations. is converse invariant if and only if
or can be obtained by applying the bridge-mirroring operation recursively to an orientation of a path.
The paper establishes this characterization for orientations of trees with diameter bounded by three. The conjecture proposes that the same description holds for all orientations of trees with maximum degree at least .
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Jiangdong Ai, Gregory Gutin, Hui Lei, Anders Yeo and Yacong Zhou, “Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials”, arXiv:2407.17051 (2024).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.