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:
- 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.
- It is proved that there are only four outerplanar UPC-graphs having
3, 5, 8, 8
vertices respectively.
- It is conjectured that the above 7 graphs are the only UPC-graphs.
- Essentially there was no progress since 1986 !!
The only available papers on the subject so far are :
- Shi, Y.B., Yap, H.P,. and Teo, S.K., On uniquely r-pancyclic graphs,
Graph Theory and Its Applications: East and West, (Jinan, 1986),
487-499,
Ann. New York Acad. Sci., 576, New York Acad. Sci. New York, 1989.
MR 93d:05088
- Shi, Y.B., Some theorems of uniquely pancyclic graphs,
Discrete Math. 59(1986), 167-180. MR 87j:05103
URL: http://www.math.fau.edu/locke/UPCGraph.htm
Last modified December 29, 1999, by S.C. Locke.