On \(3^*\)-connected graphs (Q2760442)

Let \(G\) be a 3-connected cubic graph. Then \(G\) is called \(3^*\)-connected, if there exist two vertices such that the three disjoint paths between them contain all the vertices of \(G\). The graph is called globally \(3^*\)-connected if this is true for all pairs of different vertices. Firstly, the authors present some necessary and sufficient conditions for graphs to be \(3^*\)-connected or globally \(3^*\)-connected. For example, a necessary condition for \(3^*\)-connectedness is that the circumference is at least \(2(n+1)/3\), where \(n\) is the order of the graph. Furthermore, it is shown that the ladders are \(3^*\)-connected, and that the generalized Petersen graphs \(P(n,2)\) are globally \(3^*\)-connected if and only if \(n\equiv 1,3\pmod 6\).