Long cycles and spanning subgraphs of locally maximal 1‐planar graphs

I Fabrici, J Harant, T Madaras, S Mohr… - Journal of Graph …, 2020 - Wiley Online Library
I Fabrici, J Harant, T Madaras, S Mohr, R Soták, CT Zamfirescu
Journal of Graph Theory, 2020Wiley Online Library
A graph is 1‐planar if it has a drawing in the plane such that each edge is crossed at most
once by another edge. Moreover, if this drawing has the additional property that for each
crossing of two edges the end vertices of these edges induce a complete subgraph, then the
graph is locally maximal 1‐planar. For a 3‐connected locally maximal 1‐planar graph G, we
show the existence of a spanning 3‐connected planar subgraph and prove that G is
Hamiltonian if G has at most three 3‐vertex‐cuts, and that G is traceable if G has at most four …
Abstract
A graph is 1‐planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1‐planar. For a 3‐connected locally maximal 1‐planar graph G, we show the existence of a spanning 3‐connected planar subgraph and prove that G is Hamiltonian if G has at most three 3‐vertex‐cuts, and that G is traceable if G has at most four 3‐vertex‐cuts. Moreover, infinitely many nontraceable 5‐connected 1‐planar graphs are presented.
Wiley Online Library
以上显示的是最相近的搜索结果。 查看全部搜索结果