On randomly 3-axial graphs
Yousef Alavi, Sabra S. Anderson, Gary Chartrand, S.F. Kapoor · Bulletin of the Australian Mathematical Society · 1982
A graph G, every vertex of which has degree at least three, is randomly 3-axial if for each vertex v of G, any ordered collection of three paths in G of length one with initial vertex v can be cyclically randomly extended to produce three internally disjoint paths which contain all the vertices of G. Randomly 3-axial graphs of order p > 4 are characterized for p ≢ 1 (mod 3), and are shown to be either complete graphs or certain regular complete bipartite graphs.