← All problems

Petingi–Rodríguez conjecture on ν-min graphs

Let ν(G)\nu(G) denote the number of induced paths on four vertices (induced 33-paths) in a simple graph GG. For integers d≥1d\ge 1 and n≥1n\ge 1, call a dd-regular graph on nn vertices ν\nu-minimal if it minimizes ν\nu among all dd-regular graphs on nn vertices. The Petingi–Rodríguez conjecture states that, for every dd and nn, a dd-regular graph GG on nn vertices is ν\nu-minimal if and only if the disjoint union G⊔Kd+1G\sqcup K_{d+1} is ν\nu-minimal among all dd-regular graphs on n+d+1n+d+1 vertices. Equivalently, the class of dd-regular ν\nu-minimal graphs is invariant under the addition or deletion of components isomorphic to Kd+1K_{d+1}.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 tt-optimal graphs.
  • Petingi and Rodríguez: proved asymptotically that non-almost-regular graphs are suboptimal in the relevant large-nn regime.
  • Their
−min⁡refinementgivesthesameasymptoticconclusionwhensuitable-\min refinement gives the same asymptotic conclusion when suitable

-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 tt-optimal graphs. The latest reported result proves invariance under adding or deleting copies of Kd+1K_{d+1} for d≥3d\ge 3 and n≥d3n\ge d^3, 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.

Sources

Solutions 0

No solutions have been posted yet.