Pancyclicity, panconnectivity, and panpositionability for general graphs and bipartite graphs. (Q2839907)

The authors study several notions that strengthen that of hamilton graphs. A graph \(G\) is pancyclic if it contains cyclesNEWLINEof all lengths (3, \dots, \(| V(G)| \)). It is panconnected if it, for every pair of distinct vertices \(x\), \(y\),NEWLINEcontains an \(x-y\) path of every length (\(d(x,y), \dots, | V(G)| -1\)).NEWLINEFinally, \(G\) is panpositionable if it for every pair of distinct vertices \(x\), \(y\) and integer \(k\) contains a Hamilton cycle onNEWLINEwhich \(x\) and \(y\) are at distance \(k\) (for every \(k\) s. t. \(d(x,y) \leq k \leq | V(G)| /2\)).NEWLINENEWLINENEWLINENEWLINEIt is clear that panconnected implies pancyclic and also panpositionable implies pancyclic.NEWLINEThe paper shows that none of the reverse implications is true, and also that there is a graph that is panconnected but not panpositionable.NEWLINEIt remains open whether there is panpositionable graph that is not panconnected.NEWLINEThe proofs are by means of simple examples: small modification of a bipartite graph, circulant graphs, etc.NEWLINEAuthors also study related problems for bipartite graphs and find analogous results there.