Construction, Extension and Paths of Near-Homogeneous Tournaments
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915265957068800 |
|---|---|
| author | Tang, Rongxia Chen, Zhaojun Zhang, Zan-Bo |
| author_facet | Tang, Rongxia Chen, Zhaojun Zhang, Zan-Bo |
| contents | A homogeneous tournament is a tournament with $4t+3$ vertices such that every arc is contained in exactly $t+1$ cycles of length $3$. Homogeneous tournaments are the first class of tournaments that are proved to be path extendable, which means that every nonhamiltonian path $P$ in such a tournament $T$ can be extended to a path $P'$ with the same initial and terminal vertex and $V(P')=V(P)\cup \{u\}$ for a certain vertex $u\in V(T)\backslash V(P)$. In order to find more path extendable tournaments we study the generalization of homogeneous tournaments called near-homogeneous tournaments, in which every arc is contained in $t$ or $t+1$ cycles of length $3$. Near-homogeneity has been defined in tournaments with $4t+1$ vertices. In this paper, we raise a new method to construct near-homogeneous tournaments with $4t+1$ vertices. We then show that the definition of near-homogeneous tournament can be extended to tournaments with an even number of vertices. Finally we verify path extendability of near-homogeneous tournaments, thus expand the class of path extendable tournaments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_06445 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Construction, Extension and Paths of Near-Homogeneous Tournaments Tang, Rongxia Chen, Zhaojun Zhang, Zan-Bo Combinatorics 05C20, 05B20 G.2.2 A homogeneous tournament is a tournament with $4t+3$ vertices such that every arc is contained in exactly $t+1$ cycles of length $3$. Homogeneous tournaments are the first class of tournaments that are proved to be path extendable, which means that every nonhamiltonian path $P$ in such a tournament $T$ can be extended to a path $P'$ with the same initial and terminal vertex and $V(P')=V(P)\cup \{u\}$ for a certain vertex $u\in V(T)\backslash V(P)$. In order to find more path extendable tournaments we study the generalization of homogeneous tournaments called near-homogeneous tournaments, in which every arc is contained in $t$ or $t+1$ cycles of length $3$. Near-homogeneity has been defined in tournaments with $4t+1$ vertices. In this paper, we raise a new method to construct near-homogeneous tournaments with $4t+1$ vertices. We then show that the definition of near-homogeneous tournament can be extended to tournaments with an even number of vertices. Finally we verify path extendability of near-homogeneous tournaments, thus expand the class of path extendable tournaments. |
| title | Construction, Extension and Paths of Near-Homogeneous Tournaments |
| topic | Combinatorics 05C20, 05B20 G.2.2 |
| url | https://arxiv.org/abs/2209.06445 |