The minimum size of maximal bipartite IC-plane graphs with given connectivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913869870399488 |
|---|---|
| author | Wang, Guiping Huang, Yuanqiu Ouyang, Zhangdong Zhang, Licheng |
| author_facet | Wang, Guiping Huang, Yuanqiu Ouyang, Zhangdong Zhang, Licheng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_00878 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The minimum size of maximal bipartite IC-plane graphs with given connectivity Wang, Guiping Huang, Yuanqiu Ouyang, Zhangdong Zhang, Licheng Combinatorics 05C10, 05C62 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. |
| title | The minimum size of maximal bipartite IC-plane graphs with given connectivity |
| topic | Combinatorics 05C10, 05C62 |
| url | https://arxiv.org/abs/2506.00878 |