Skip to main content
MathOverflow

Return to Question

added 1 character in body
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

A graph is 1-planar if it can be drawn on the plane such that each edge is crossed at most once.

Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed that $m \ge 3n − 8$ holds for even $n \ge 8$ and $m \ge 3n − 9$ holds for odd $n \ge 7$.

[1]. D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite graph. J. Math. Sci., 196:737–746, 2014.

So the minimum degree of any 1-planar bipartite graph is at most $5$. Here is my question.

  • Construct a 5-regular bipartite 1-planar graph.

I've noticed that $5n\le2(3n-8)$ implies that $n\ge 16$. Maybe we will find such graph with $16$ vertices.

As jpreen reminds us, the following are 41 5-regular bipartite graphs with 16 vertices (with graph6 format). It may not be easy to determine whether they are 1-planrplanar or not.

O????Bw}FKWwlOUoDw?}?
O????Bw}FKWwfOUoEw@]?
O????Bw|Fo[WpoJoBw?}?
O????Bw|FcPw{ORoDw?}?
O????Bw|FSWwdoVOFW@]?
O????Bw|FSWwdoRoFg@u?
O????Bw|FEZ_woJoBw?}?
O????Bw|FE\OxOFoBw?}?
O????Bw|FEZOtOFoDw@]?
O????Bw|FEXojOUoBw@m?
O????Bw|FEXofOMoDwAm?
O????Bw|FEXokoVODw?}?
O????Bw|FEXokoNOHw?}?
O????Bw|FEXoeoToFg@]?
O????Bw|FE[Wz?FoBw?}?
O????Bw|FE[Wf_VODw?}?
O????Bw|FEXWl_VOBw@]?
O????Bwxei^?woJoBw?}?
O????BwxeiRotOYoFW@]?
O????BwxeiXW}?LoDw?}?
O????BwxeiXWn?XoFW?}?
O????BwxeiXWf_ZOFW@m?
O????BwpvoWwl_ZOFW?}?
O????BwpvgToxOUoFW?}?
O????BwpvgXWm_ZOEw?}?
O????BwpvgXWj_VOFW@m?
O????BwpvgXWj_[oFg?}?
O????Bwptw[W}?ToDw?}?
O????Bwptw[W{_VODw?}?
O????Bwptw[W{_NOHw?}?
O????BwptwUW}?XoBwA]?
O????BwptwUWm_XoJgA]?
O????BwptwUWioXoJoAy?
O????BwptwWw|?YoBw@u?
O????Bwptk\G|?MoHw?}?
O????BwptkTg|?YoJW?}?
O????BwptkTg|?RoJW@u?
O????BwptkTgl_]OJWA]?
O????BwptkTgl_VOJWBU?
O????BwptkTgj_VOJWBe?
O????BwptkTgeoZ_JgBe?

The problem comes from planar bipartite graphs. Any planar bipartite graph has minimum degree at most 3. The smallest order of 3-regular planar bipartite graph is 8; see the below graph. enter image description here

A graph is 1-planar if it can be drawn on the plane such that each edge is crossed at most once.

Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed that $m \ge 3n − 8$ holds for even $n \ge 8$ and $m \ge 3n − 9$ holds for odd $n \ge 7$.

[1]. D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite graph. J. Math. Sci., 196:737–746, 2014.

So the minimum degree of any 1-planar bipartite graph is at most $5$. Here is my question.

  • Construct a 5-regular bipartite 1-planar graph.

I've noticed that $5n\le2(3n-8)$ implies that $n\ge 16$. Maybe we will find such graph with $16$ vertices.

As jpreen reminds us, the following are 41 5-regular bipartite graphs with 16 vertices (with graph6 format). It may not be easy to determine whether they are 1-planr or not.

O????Bw}FKWwlOUoDw?}?
O????Bw}FKWwfOUoEw@]?
O????Bw|Fo[WpoJoBw?}?
O????Bw|FcPw{ORoDw?}?
O????Bw|FSWwdoVOFW@]?
O????Bw|FSWwdoRoFg@u?
O????Bw|FEZ_woJoBw?}?
O????Bw|FE\OxOFoBw?}?
O????Bw|FEZOtOFoDw@]?
O????Bw|FEXojOUoBw@m?
O????Bw|FEXofOMoDwAm?
O????Bw|FEXokoVODw?}?
O????Bw|FEXokoNOHw?}?
O????Bw|FEXoeoToFg@]?
O????Bw|FE[Wz?FoBw?}?
O????Bw|FE[Wf_VODw?}?
O????Bw|FEXWl_VOBw@]?
O????Bwxei^?woJoBw?}?
O????BwxeiRotOYoFW@]?
O????BwxeiXW}?LoDw?}?
O????BwxeiXWn?XoFW?}?
O????BwxeiXWf_ZOFW@m?
O????BwpvoWwl_ZOFW?}?
O????BwpvgToxOUoFW?}?
O????BwpvgXWm_ZOEw?}?
O????BwpvgXWj_VOFW@m?
O????BwpvgXWj_[oFg?}?
O????Bwptw[W}?ToDw?}?
O????Bwptw[W{_VODw?}?
O????Bwptw[W{_NOHw?}?
O????BwptwUW}?XoBwA]?
O????BwptwUWm_XoJgA]?
O????BwptwUWioXoJoAy?
O????BwptwWw|?YoBw@u?
O????Bwptk\G|?MoHw?}?
O????BwptkTg|?YoJW?}?
O????BwptkTg|?RoJW@u?
O????BwptkTgl_]OJWA]?
O????BwptkTgl_VOJWBU?
O????BwptkTgj_VOJWBe?
O????BwptkTgeoZ_JgBe?

The problem comes from planar bipartite graphs. Any planar bipartite graph has minimum degree at most 3. The smallest order of 3-regular planar bipartite graph is 8; see the below graph. enter image description here

A graph is 1-planar if it can be drawn on the plane such that each edge is crossed at most once.

Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed that $m \ge 3n − 8$ holds for even $n \ge 8$ and $m \ge 3n − 9$ holds for odd $n \ge 7$.

[1]. D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite graph. J. Math. Sci., 196:737–746, 2014.

So the minimum degree of any 1-planar bipartite graph is at most $5$. Here is my question.

  • Construct a 5-regular bipartite 1-planar graph.

I've noticed that $5n\le2(3n-8)$ implies that $n\ge 16$. Maybe we will find such graph with $16$ vertices.

As jpreen reminds us, the following are 41 5-regular bipartite graphs with 16 vertices (with graph6 format). It may not be easy to determine whether they are 1-planar or not.

O????Bw}FKWwlOUoDw?}?
O????Bw}FKWwfOUoEw@]?
O????Bw|Fo[WpoJoBw?}?
O????Bw|FcPw{ORoDw?}?
O????Bw|FSWwdoVOFW@]?
O????Bw|FSWwdoRoFg@u?
O????Bw|FEZ_woJoBw?}?
O????Bw|FE\OxOFoBw?}?
O????Bw|FEZOtOFoDw@]?
O????Bw|FEXojOUoBw@m?
O????Bw|FEXofOMoDwAm?
O????Bw|FEXokoVODw?}?
O????Bw|FEXokoNOHw?}?
O????Bw|FEXoeoToFg@]?
O????Bw|FE[Wz?FoBw?}?
O????Bw|FE[Wf_VODw?}?
O????Bw|FEXWl_VOBw@]?
O????Bwxei^?woJoBw?}?
O????BwxeiRotOYoFW@]?
O????BwxeiXW}?LoDw?}?
O????BwxeiXWn?XoFW?}?
O????BwxeiXWf_ZOFW@m?
O????BwpvoWwl_ZOFW?}?
O????BwpvgToxOUoFW?}?
O????BwpvgXWm_ZOEw?}?
O????BwpvgXWj_VOFW@m?
O????BwpvgXWj_[oFg?}?
O????Bwptw[W}?ToDw?}?
O????Bwptw[W{_VODw?}?
O????Bwptw[W{_NOHw?}?
O????BwptwUW}?XoBwA]?
O????BwptwUWm_XoJgA]?
O????BwptwUWioXoJoAy?
O????BwptwWw|?YoBw@u?
O????Bwptk\G|?MoHw?}?
O????BwptkTg|?YoJW?}?
O????BwptkTg|?RoJW@u?
O????BwptkTgl_]OJWA]?
O????BwptkTgl_VOJWBU?
O????BwptkTgj_VOJWBe?
O????BwptkTgeoZ_JgBe?

The problem comes from planar bipartite graphs. Any planar bipartite graph has minimum degree at most 3. The smallest order of 3-regular planar bipartite graph is 8; see the below graph. enter image description here

added 1156 characters in body
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

A graph is 1-planar if it can be drawn on the plane such that each edge is crossed at most once.

Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed that $m \ge 3n − 8$ holds for even $n \ge 8$ and $m \ge 3n − 9$ holds for odd $n \ge 7$.

[1]. D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite graph. J. Math. Sci., 196:737–746, 2014.

So the minimum degree of any 1-planar bipartite graph is at most $5$. Here is my question.

  • Construct a 5-regular bipartite 1-planar graph.

I've noticed that $5n\le2(3n-8)$ implies that $n\ge 16$. Maybe we will find such graph with $16$ vertices.

As jpreen reminds us, the following are 41 5-regular bipartite graphs with 16 vertices (with graph6 format). It may not be easy to determine whether they are 1-planr or not.

O????Bw}FKWwlOUoDw?}?
O????Bw}FKWwfOUoEw@]?
O????Bw|Fo[WpoJoBw?}?
O????Bw|FcPw{ORoDw?}?
O????Bw|FSWwdoVOFW@]?
O????Bw|FSWwdoRoFg@u?
O????Bw|FEZ_woJoBw?}?
O????Bw|FE\OxOFoBw?}?
O????Bw|FEZOtOFoDw@]?
O????Bw|FEXojOUoBw@m?
O????Bw|FEXofOMoDwAm?
O????Bw|FEXokoVODw?}?
O????Bw|FEXokoNOHw?}?
O????Bw|FEXoeoToFg@]?
O????Bw|FE[Wz?FoBw?}?
O????Bw|FE[Wf_VODw?}?
O????Bw|FEXWl_VOBw@]?
O????Bwxei^?woJoBw?}?
O????BwxeiRotOYoFW@]?
O????BwxeiXW}?LoDw?}?
O????BwxeiXWn?XoFW?}?
O????BwxeiXWf_ZOFW@m?
O????BwpvoWwl_ZOFW?}?
O????BwpvgToxOUoFW?}?
O????BwpvgXWm_ZOEw?}?
O????BwpvgXWj_VOFW@m?
O????BwpvgXWj_[oFg?}?
O????Bwptw[W}?ToDw?}?
O????Bwptw[W{_VODw?}?
O????Bwptw[W{_NOHw?}?
O????BwptwUW}?XoBwA]?
O????BwptwUWm_XoJgA]?
O????BwptwUWioXoJoAy?
O????BwptwWw|?YoBw@u?
O????Bwptk\G|?MoHw?}?
O????BwptkTg|?YoJW?}?
O????BwptkTg|?RoJW@u?
O????BwptkTgl_]OJWA]?
O????BwptkTgl_VOJWBU?
O????BwptkTgj_VOJWBe?
O????BwptkTgeoZ_JgBe?

The problem comes from planar bipartite graphs. Any planar bipartite graph has minimum degree at most 3. The smallest order of 3-regular planar bipartite graph is 8; see the below graph. enter image description here

A graph is 1-planar if it can be drawn on the plane such that each edge is crossed at most once.

Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed that $m \ge 3n − 8$ holds for even $n \ge 8$ and $m \ge 3n − 9$ holds for odd $n \ge 7$.

[1]. D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite graph. J. Math. Sci., 196:737–746, 2014.

So the minimum degree of any 1-planar bipartite graph is at most $5$. Here is my question.

  • Construct a 5-regular bipartite 1-planar graph.

I've noticed that $5n\le2(3n-8)$ implies that $n\ge 16$. Maybe we will find such graph with $16$ vertices.

The problem comes from planar bipartite graphs. Any planar bipartite graph has minimum degree at most 3. The smallest order of 3-regular planar bipartite graph is 8; see the below graph. enter image description here

A graph is 1-planar if it can be drawn on the plane such that each edge is crossed at most once.

Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed that $m \ge 3n − 8$ holds for even $n \ge 8$ and $m \ge 3n − 9$ holds for odd $n \ge 7$.

[1]. D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite graph. J. Math. Sci., 196:737–746, 2014.

So the minimum degree of any 1-planar bipartite graph is at most $5$. Here is my question.

  • Construct a 5-regular bipartite 1-planar graph.

I've noticed that $5n\le2(3n-8)$ implies that $n\ge 16$. Maybe we will find such graph with $16$ vertices.

As jpreen reminds us, the following are 41 5-regular bipartite graphs with 16 vertices (with graph6 format). It may not be easy to determine whether they are 1-planr or not.

O????Bw}FKWwlOUoDw?}?
O????Bw}FKWwfOUoEw@]?
O????Bw|Fo[WpoJoBw?}?
O????Bw|FcPw{ORoDw?}?
O????Bw|FSWwdoVOFW@]?
O????Bw|FSWwdoRoFg@u?
O????Bw|FEZ_woJoBw?}?
O????Bw|FE\OxOFoBw?}?
O????Bw|FEZOtOFoDw@]?
O????Bw|FEXojOUoBw@m?
O????Bw|FEXofOMoDwAm?
O????Bw|FEXokoVODw?}?
O????Bw|FEXokoNOHw?}?
O????Bw|FEXoeoToFg@]?
O????Bw|FE[Wz?FoBw?}?
O????Bw|FE[Wf_VODw?}?
O????Bw|FEXWl_VOBw@]?
O????Bwxei^?woJoBw?}?
O????BwxeiRotOYoFW@]?
O????BwxeiXW}?LoDw?}?
O????BwxeiXWn?XoFW?}?
O????BwxeiXWf_ZOFW@m?
O????BwpvoWwl_ZOFW?}?
O????BwpvgToxOUoFW?}?
O????BwpvgXWm_ZOEw?}?
O????BwpvgXWj_VOFW@m?
O????BwpvgXWj_[oFg?}?
O????Bwptw[W}?ToDw?}?
O????Bwptw[W{_VODw?}?
O????Bwptw[W{_NOHw?}?
O????BwptwUW}?XoBwA]?
O????BwptwUWm_XoJgA]?
O????BwptwUWioXoJoAy?
O????BwptwWw|?YoBw@u?
O????Bwptk\G|?MoHw?}?
O????BwptkTg|?YoJW?}?
O????BwptkTg|?RoJW@u?
O????BwptkTgl_]OJWA]?
O????BwptkTgl_VOJWBU?
O????BwptkTgj_VOJWBe?
O????BwptkTgeoZ_JgBe?

The problem comes from planar bipartite graphs. Any planar bipartite graph has minimum degree at most 3. The smallest order of 3-regular planar bipartite graph is 8; see the below graph. enter image description here

Became Hot Network Question
added 5 characters in body
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

A graph is 1-planar if it can be drawn on the plane such that each edge is crossed at most once.

Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed that $m \ge 3n − 8$ holds for even $n \ge 8$ and $m \ge 3n − 9$ holds for odd $n \ge 7$.

[1]. D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite graph. J. Math. Sci., 196:737–746, 2014.

So the minimum degree of any 11-planar bipartite graph is at most $5$. Here is my question.

  • Construct a 5-regular bipartite 1-planar graph.

I noteI've noticed that $5n\le2(3n-8)$ implingimplies that $n\ge 16$. Maybe we will find such graph with $16$ vertices.

The problem comes from planar bipartite graphs. Any planar bipartite graph has minimum degree at most 3. The smallest order of 3-regular planar bipartite graph is 8; see the below graph. enter image description here

A graph is 1-planar if it can be drawn on the plane such that each edge is crossed at most once.

Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed that $m \ge 3n − 8$ holds for even $n \ge 8$ and $m \ge 3n − 9$ holds for odd $n \ge 7$.

[1]. D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite graph. J. Math. Sci., 196:737–746, 2014.

So the minimum degree of any 1-planar bipartite graph is at most $5$. Here is my question.

  • Construct a 5-regular bipartite 1-planar graph.

I note that $5n\le2(3n-8)$ impling that $n\ge 16$. Maybe we will find such graph with $16$ vertices.

The problem comes from planar bipartite graphs. Any planar bipartite graph has minimum degree at most 3. The smallest order of 3-regular planar bipartite graph is 8; see the below graph. enter image description here

A graph is 1-planar if it can be drawn on the plane such that each edge is crossed at most once.

Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed that $m \ge 3n − 8$ holds for even $n \ge 8$ and $m \ge 3n − 9$ holds for odd $n \ge 7$.

[1]. D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite graph. J. Math. Sci., 196:737–746, 2014.

So the minimum degree of any 1-planar bipartite graph is at most $5$. Here is my question.

  • Construct a 5-regular bipartite 1-planar graph.

I've noticed that $5n\le2(3n-8)$ implies that $n\ge 16$. Maybe we will find such graph with $16$ vertices.

The problem comes from planar bipartite graphs. Any planar bipartite graph has minimum degree at most 3. The smallest order of 3-regular planar bipartite graph is 8; see the below graph. enter image description here

added 8 characters in body
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17
escaped the square brackets in the reference (it is pointing to the image after the last edit)
Source Link
edit approved Sep 10, 2022 at 10:35
The Amplitwist
edit approved Sep 10, 2022 at 10:35
The Amplitwist
  • 1.4k
  • 3
  • 11
  • 22
added 261 characters in body
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17