Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.05953 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912589373505536 |
|---|---|
| author | Chen, Hangdi Ma, Yuhan Ye, Qingjie |
| author_facet | Chen, Hangdi Ma, Yuhan Ye, Qingjie |
| contents | Given two non-adjacent vertices \( u \) and \( v \), we say a $uv$-walk \( W \) dominates a $uv$-walk \( W' \) if every internal vertex of \( W' \) is adjacent to some internal vertex of \( W \) or belongs to \( W \). A class of walks \(\mathbf{A}\) dominates a class of walks \(\mathbf{B}\) if for every pair of non-adjacent vertices $u,v$ in the graph, every $uv$-walk in \(\mathbf{A}\) dominates every $uv$-walk in \(\mathbf{B}\). This paper investigates the domination relationships among various types of walks connecting two non-adjacent vertices in a graph. In particular, we focus on the problem which is proposed in [S. B. Tondato, Graphs Combin. 40 (2024)]. We study the domination between different walk types (shortest paths, toll walks, weakly toll walks, $l_k$-paths for $k\in \left\{2,3\right\}$) and $m_3$-paths. And we show how these relationships give rise to characterizations of graph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05953 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On walk domination: Between different types of walks and $m_3$-path Chen, Hangdi Ma, Yuhan Ye, Qingjie Combinatorics 05C38, 05C69 Given two non-adjacent vertices \( u \) and \( v \), we say a $uv$-walk \( W \) dominates a $uv$-walk \( W' \) if every internal vertex of \( W' \) is adjacent to some internal vertex of \( W \) or belongs to \( W \). A class of walks \(\mathbf{A}\) dominates a class of walks \(\mathbf{B}\) if for every pair of non-adjacent vertices $u,v$ in the graph, every $uv$-walk in \(\mathbf{A}\) dominates every $uv$-walk in \(\mathbf{B}\). This paper investigates the domination relationships among various types of walks connecting two non-adjacent vertices in a graph. In particular, we focus on the problem which is proposed in [S. B. Tondato, Graphs Combin. 40 (2024)]. We study the domination between different walk types (shortest paths, toll walks, weakly toll walks, $l_k$-paths for $k\in \left\{2,3\right\}$) and $m_3$-paths. And we show how these relationships give rise to characterizations of graph classes. |
| title | On walk domination: Between different types of walks and $m_3$-path |
| topic | Combinatorics 05C38, 05C69 |
| url | https://arxiv.org/abs/2504.05953 |