Petingi–Rodríguez conjecture on ν-min graphs
Let denote the number of induced paths on four vertices (induced -paths) in a simple graph . For integers and , call a -regular graph on vertices -minimal if it minimizes among all -regular graphs on vertices. The Petingi–Rodríguez conjecture states that, for every and , a -regular graph on vertices is -minimal if and only if the disjoint union is -minimal among all -regular graphs on vertices. Equivalently, the class of -regular -minimal graphs is invariant under the addition or deletion of components isomorphic to .
References
- Trace-minimal graphs maximizing the number of spanning trees — arXiv — Pablo Romero, Louis Petingi
Source: arXiv
Progress summary
A recent manuscript extends the known large-size results and constructs new extremal graph families, but the full conjecture remains open.
The conjecture concerns graphs maximizing spanning-tree counts with prescribed numbers of vertices and edges, refining work of Petingi and Rodríguez. Their earlier papers developed the relevant extremal framework but did not settle the full conjecture.
Known results
- Petingi and Rodríguez, 1999: studied almost-regular maximizers of spanning-tree counts.
- Petingi, Rodríguez, 2002: developed a characterization technique and constructed infinitely many -optimal graphs.
- Petingi and Rodríguez: proved asymptotically that non-almost-regular graphs are suboptimal in the relevant large- regime.
- Their
-min graphs exist.
2025–2026 asymptotic and construction results
A 2025 manuscript introduces trace-minimal graphs, strengthens the asymptotic comparison using Laplacian-trace order, and constructs infinitely many regular -optimal graphs. The latest reported result proves invariance under adding or deleting copies of for and , and gives further infinite extremal families. These are claimed advances, not a proof of the full conjecture.
Current status (as of October 2026): The asymptotic results and new extremal families are claimed, while the full Petingi–Rodríguez conjecture for all parameters remains open.
Solutions 0
No solutions have been posted yet.