The wild number of an edge-colored graph
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915437034340352 |
|---|---|
| author | Anders, Katie Foster-Greenwood, Briana Garcia, Rebecca Krawzik, Naomi |
| author_facet | Anders, Katie Foster-Greenwood, Briana Garcia, Rebecca Krawzik, Naomi |
| contents | We introduce the wild number of an edge-colored graph as a measure of how close an edge-colored graph is to having a spanning tree in every color. This combinatorial concept originates in the algebraic theory of generalized graph splines. After showing that determining the wild number of a graph is an NP-complete problem, we provide bounds on the wild number and find the exact wild number for trees, cycles, and families of graphs with restrictions on the edge-colorings. This article serves as an invitation to the topic of wild numbers and includes several open problems, many of which are suitable for undergraduate research projects. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06711 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The wild number of an edge-colored graph Anders, Katie Foster-Greenwood, Briana Garcia, Rebecca Krawzik, Naomi Combinatorics 05C70 (Primary) 05C15, 05C40, 05C25 (Secondary) We introduce the wild number of an edge-colored graph as a measure of how close an edge-colored graph is to having a spanning tree in every color. This combinatorial concept originates in the algebraic theory of generalized graph splines. After showing that determining the wild number of a graph is an NP-complete problem, we provide bounds on the wild number and find the exact wild number for trees, cycles, and families of graphs with restrictions on the edge-colorings. This article serves as an invitation to the topic of wild numbers and includes several open problems, many of which are suitable for undergraduate research projects. |
| title | The wild number of an edge-colored graph |
| topic | Combinatorics 05C70 (Primary) 05C15, 05C40, 05C25 (Secondary) |
| url | https://arxiv.org/abs/2508.06711 |