Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials

An oriented graph (Formula presented.) is converse invariant if, for any tournament (Formula presented.), the number of copies of (Formula presented.) in (Formula presented.) is equal to that of its converse (Formula presented.). El Sahili and Ghazo Hanna [J. Graph Theory 102 (2023), 684-701] showed that any oriented graph (Formula presented.) 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 (Formula presented.) and (Formula presented.) have different degree sequences. In addition, in contrast to the findings of El Sahili and Ghazo Hanna, we prove that every connected graph (Formula presented.) with maximum degree at least 3, admits an orientation (Formula presented.) of (Formula presented.) such that (Formula presented.) is not converse invariant. We pose a new conjecture.