The minimum size of maximal bipartite IC-plane graphs with given connectivity

Read full text Summarise with VIRAT
Authors: Guiping Wang, Yuanqiu Huang, Zhangdong Ouyang, Licheng Zhang
Cited by: 0
References: 19

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Recently, the problem of establishing bounds on the edge density of 1-planar graphs, including their subclass IC-planar graphs, has received considerable attention. In 2018, Angelini et al. showed that any n-vertex bipartite IC-planar graph has at most 2.25n-4 edges, which implies that bipartite IC-planar graphs have vertex-connectivity at most 4. In this paper, we prove that any n-vertex maximal bipartite IC-plane graph with connectivity 2 has at least 3/2n-2 edges, and those with connectivity 3 has at least 2n-3 edges. All the above lower bounds are tight. For 4-connected maximal bipartite IC-planar graphs, the question of determining a non-trivial lower bound on the size remains open.

Fields of Study & Subjects

Advanced Graph Theory Research Limits and Structures in Graph Theory Complexity and Algorithms in Graphs

Publication details

Journal / source
Discussiones Mathematicae Graph Theory
Volume
46
Issue
3
Pages
765–765
Publication date
1 January 2026
Language
EN