Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909266853494784 |
|---|---|
| author | Ai, Jiangdong Gutin, Gregory Lei, Hui Yeo, Anders Zhou, Yacong |
| author_facet | Ai, Jiangdong Gutin, Gregory Lei, Hui Yeo, Anders Zhou, Yacong |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_17051 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials Ai, Jiangdong Gutin, Gregory Lei, Hui Yeo, Anders Zhou, Yacong Combinatorics Discrete Mathematics 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. |
| title | Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2407.17051 |