Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials
<|reference_start|>Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials: An oriented graph $D$ is converse invariant if, for any tournament $T$, the number of copies of $D$ in $T$ is equal to that of its converse $-D$. El Sahili and Ghazo Hanna [J. Graph Theory 102 (2023), 684-701] showed that any oriented graph $D$ with maximum degree at most 2 is converse invariant. They proposed a question: Can we characterize all converse invariant oriented graphs?   In this paper, we introduce a digraph polynomial and employ it to give a necessary condition for an oriented graph to be converse invariant. This polynomial serves as a cornerstone in proving all the results presented in this paper. In particular, we characterize all orientations of trees with diameter at most 3 that are converse invariant. We also show that all orientations of regular graphs are not converse invariant if $D$ and $-D$ have different degree sequences. In addition, in contrast to the findings of El Sahili and Ghazo Hanna, we prove that every connected graph $G$ with maximum degree at least $3$, admits an orientation $D$ of $G$ such that $D$ is not converse invariant. We pose one conjecture.<|reference_end|>
@article{ai2024number,
    title={Number of Subgraphs and Their Converses in Tournaments and New Digraph
  Polynomials},
    author={Jiangdong Ai, Gregory Gutin, Hui Lei, Anders Yeo, Yacong Zhou},
    journal={arXiv preprint arXiv:2407.17051},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.17051},
    primaryClass={math.CO cs.DM}
}