Wild number for spanning trees in complete and complete bipartite graphs
Abstract
Given an edge-colored graph, the wild number measures how close the graph is to having a spanning tree in every color. We investigate this parameter for complete graphs and complete bipartite graphs, with particular emphasis on minimum proper colorings and equitable $2$-colorings. For complete graphs, we determine the full range of wild numbers attainable by equitable $2$-colorings and show that, although every value in this range occurs, the expected wild number of a uniformly random equitable $2$-coloring tends to $0$ as the order of the graph grows. For minimum proper colorings of Kn, we establish a general lower bound, determine the exact wild number for 3 ≤ n ≤ 12, and conjecture that the lower bound is sharp for all n. We also develop structural conditions on ideal wild sets and use them to obtain upper bounds and analyze the performance of a natural greedy algorithm. For complete bipartite graphs, we prove a sharp upper bound for equitable $2$-colorings and determine the wild number exactly for minimum proper colorings. Finally, we apply these results to Cartesian products of complete graphs and complete bipartite graphs, obtaining lower bounds for the wild number under minimum proper and product colorings.
Related
- Maximum number of spanning trees in bipartite graphs with a given diameter
- A Turán-type extremal problem for the number of spanning trees in C4-free graphs
- Trace-minimal graphs maximizing the number of spanning trees
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
- On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
BibTeX
@misc{dawkins2026wild,
title = {{Wild number for spanning trees in complete and complete bipartite graphs}},
author = {Aleyah Dawkins and Alexander Nappo and Jessie Tong and Christopher Zimbizi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22142},
eprint = {2610.22142},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22142},
}
RIS
TY - UNPB
TI - Wild number for spanning trees in complete and complete bipartite graphs
AU - Aleyah Dawkins
AU - Alexander Nappo
AU - Jessie Tong
AU - Christopher Zimbizi
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.22142
UR - https://arxiv.org/abs/2610.22142
AB - Given an edge-colored graph, the wild number measures how close the graph is to having a spanning tree in every color. We investigate this parameter for complete graphs and complete bipartite graphs, with particular emphasis on minimum proper colorings and equitable $2$-colorings. For complete graphs, we determine the full range of wild numbers attainable by equitable $2$-colorings and show that, although every value in this range occurs, the expected wild number of a uniformly random equitable $2$-coloring tends to $0$ as the order of the graph grows. For minimum proper colorings of K_n, we establish a general lower bound, determine the exact wild number for 3 ≤ n ≤ 12, and conjecture that the lower bound is sharp for all n. We also develop structural conditions on ideal wild sets and use them to obtain upper bounds and analyze the performance of a natural greedy algorithm. For complete bipartite graphs, we prove a sharp upper bound for equitable $2$-colorings and determine the wild number exactly for minimum proper colorings. Finally, we apply these results to Cartesian products of complete graphs and complete bipartite graphs, obtaining lower bounds for the wild number under minimum proper and product colorings.
ER -