# Optimal Edge Decomposition of Graphs and Hamiltonicity of Tough Expanders

> **NSF 01002526DB NSF RESEARCH & RELATED ACTIVIT** · Auburn University (AL) · $250,136

## Abstract

This proposal centers on two core themes: the optimal decomposition of a graph's edges into matchings, and the Hamiltonicity problem in tough graphs with some “expansion” properties. The decomposition of the edges of a graph into non-conflicting groups, such as matchings, is deeply rooted in combinatorial theory and holds practical significance across various fields, including computer science, operations research, and telecommunications. Additionally, the Hamilton cycle problem, a fundamental NP-complete problem, has been extensively studied, with recent advancements highlighting the importance of concepts like expansion and quasi-randomness. The project includes several research problems well-suited for graduate student involvement. In addition, the PI has planned outreach activities centered around graph theory concepts to stimulate interest in STEM fields, particularly among middle school students.

The PI's proposal delves into these two pivotal problems and extends her ongoing investigation into four longstanding conjectures: the Overfull Conjecture (Chetwynd and Hilton, 1986), the Multigraph Overfull Conjecture (Stiebitz, Scheide, Toft, and Favrholdt,  2012), the Total Coloring Conjecture (Behzad and, independently, Vizing, 1960s), and the Toughness Conjecture (Chvatal, 1973). Along with collaborators, the PI has made substantial progress on each of these conjectures and aims to develop new techniques to further advance the field. This work builds on a combination 

## Key facts

- **NSF award ID:** 2451895
- **Awardee organization:** Auburn University (AL)
- **SAM.gov UEI:** DMQNDJDHTDG4
- **PI:** Songling Shan
- **Primary program:** 01002526DB NSF RESEARCH & RELATED ACTIVIT
- **All programs:** EXP PROG TO STIM COMP RES
- **Estimated total:** $250,136
- **Funds obligated:** $250,136
- **Transaction type:** Standard Grant
- **Period:** 08/15/2025 → 07/31/2028

## Primary source

NSF Award Search: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2451895

## Citation

> US National Science Foundation, Award 2451895, Optimal Edge Decomposition of Graphs and Hamiltonicity of Tough Expanders. Retrieved via AI Analytics 2026-06-08 from https://api.ai-analytics.org/grant/nsf/2451895. Licensed CC0.

---

*[NSF Awards dataset](/datasets/nsf-awards) · CC0 1.0*