Uniquely Pancyclic Graphs

How to contact me.


Unsolved Problems 1-25. Unsolved Problems 26-52.
10. Determine which simple graphs G on n vertices have exactly one cycle of each possible length k, 3 <= k <= n (R. Entringer, 1973).

Yair Caro:
  1. There are only seven known UPC-graphs (unipancyclic graphs) having respectively 3, 5, 8, 8, 14, 14, 14 vertices (Entringer).

    • n=3, Hamilton cycle v1v2v3v1.

    • n=5, Hamilton cycle v1v2v3v4v5v1 and chord v1v3.

    • n=8, Hamilton cycle v1v2v3...v8v1 and
      • chords v1v3 and v3v6; or
      • chords v1v3 and v4v7.


    • n=14, Hamilton cycle v1v2v3...v14v1 and
      • chords v1v3, v1v12 and v2v10; or
      • chords v1v3, v2v8 and v4v7; or
      • chords v1v3, v2v8 and v5v8.


  2. It is proved that there are only four outerplanar UPC-graphs having 3, 5, 8, 8 vertices respectively.

  3. It is conjectured that the above 7 graphs are the only UPC-graphs.

  4. Essentially there was no progress since 1986 !!

The only available papers on the subject so far are :
URL: http://www.math.fau.edu/locke/UPCGraph.htm
Last modified December 29, 1999, by S.C. Locke.