Extremal problems about the order and size of nonhamiltonian locally linear graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914472827813888 |
|---|---|
| author | Liu, Feng Zhang, Leilei |
| author_facet | Liu, Feng Zhang, Leilei |
| contents | The interaction between local traits and global frameworks of mathematical objects has long endured as a central theme in various mathematical domains. A graph \(G\) is referred to as locally linear provided that the subgraph induced by the neighborhood of each vertex is a path. Likewise, $G$ is said to be locally hamiltonian (or locally traceable) when every vertex neighborhood induces a hamiltonian (or traceable) subgraph. Research on such local features of graphs has garnered significant interest. For example, Pareek and Skupień~ investigated the minimal possible order of a locally hamiltonian graph that is not hamiltonian, while Davies and Thomassen determined the minimum number of edges in locally hamiltonian graphs. Similar investigations on locally traceable graphs were conducted by Asratian and Oksimets, and also by de Wet and van Aardt. In this work, we focus on locally linear graphs. In particular, we identify the smallest order of a nonhamiltonian locally linear graph, as well as the least number of edges such graphs can have for a given order. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_16066 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extremal problems about the order and size of nonhamiltonian locally linear graphs Liu, Feng Zhang, Leilei Combinatorics 05C35, 05C45, 05C69 The interaction between local traits and global frameworks of mathematical objects has long endured as a central theme in various mathematical domains. A graph \(G\) is referred to as locally linear provided that the subgraph induced by the neighborhood of each vertex is a path. Likewise, $G$ is said to be locally hamiltonian (or locally traceable) when every vertex neighborhood induces a hamiltonian (or traceable) subgraph. Research on such local features of graphs has garnered significant interest. For example, Pareek and Skupień~ investigated the minimal possible order of a locally hamiltonian graph that is not hamiltonian, while Davies and Thomassen determined the minimum number of edges in locally hamiltonian graphs. Similar investigations on locally traceable graphs were conducted by Asratian and Oksimets, and also by de Wet and van Aardt. In this work, we focus on locally linear graphs. In particular, we identify the smallest order of a nonhamiltonian locally linear graph, as well as the least number of edges such graphs can have for a given order. |
| title | Extremal problems about the order and size of nonhamiltonian locally linear graphs |
| topic | Combinatorics 05C35, 05C45, 05C69 |
| url | https://arxiv.org/abs/2402.16066 |