4-connected maximal planar graphs are 4-ordered

DOI10.1016/S0012-365X(02)00438-7MaRDI QIDQ1850021zbMATH OpenOpenAlexFDO

Authors Wayne Goddard

Publication date 2 December 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(02)00438-7

zbMATH Keywords

\(k\)-orderedmaximal planar

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Review text

A graph \(G\) is said to be \(k\)-ordered if given any cyclic \(k\)-tuple of distinct vertices of \(G\), there is a circuit in \(G\) that encounters these vertices in the given cyclic order. It is shown that every 4-connected maximal planar graph is 4-ordered. If a 4-connected planar graph is not maximal planar, then it need not be 2-linked [\textit{H. A. Jung}, Math. Ann. 187, 95-103 (1970; Zbl 0184.27601)], in which case it would not be 4-ordered.

Recommendations

• 4-connected triangulations and 4-orderedness
• 7-connected graphs are 4-ordered
• Every 5-connected planar triangulation is 4-ordered Hamiltonian
• On 3-regular 4-ordered graphs
• On 4-ordered 3-regular graphs

Cited in

(6)

• 7-connected graphs are 4-ordered
• (3,3)-linked planar graphs
• Linkage for the diamond and the path with four vertices
• Every 5-connected planar triangulation is 4-ordered Hamiltonian
• Connectivity for kite-linked graphs
• 4-connected triangulations and 4-orderedness

This page was built for publication: 4-connected maximal planar graphs are 4-ordered

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850021)