2024/07/24 by Ai, Jiangdong, Gutin, Gregory, Lei, Hui +2
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.17051
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.