|
Zapiski Nauchnykh Seminarov POMI, 2012, Volume 406, Pages 12–30
(Mi znsl5288)
|
|
|
|
This article is cited in 9 scientific papers (total in 9 papers)
Upper bound on the number of edges of an almost planar bipartite graph
D. V. Karpov St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia
Abstract:
Let $G$ be a bipartite graph without loops and multiple edges on $v\ge4$ vertices, which can be drawn on the plane such that any edge intersects at most one other edge. We prove that such graph has at most $3v-8$ edges for even $v\ne6$ and at most $3v-9$ edges for odd $v$ and $v=6$. For all $v\ge4$ examples showing that these bounds are tight are constructed.
In the end of the paper, we discuss a question about drawings of complete bipartite graphs on the plane such that any edge intersects at most one other edge.
Key words and phrases:
topological graphs, planar graphs, bipartite graphs.
Received: 03.09.2012
Citation:
D. V. Karpov, “Upper bound on the number of edges of an almost planar bipartite graph”, Combinatorics and graph theory. Part V, Zap. Nauchn. Sem. POMI, 406, POMI, St. Petersburg, 2012, 12–30; J. Math. Sci. (N. Y.), 196:6 (2014), 737–746
Linking options:
https://www.mathnet.ru/eng/znsl5288 https://www.mathnet.ru/eng/znsl/v406/p12
|
Statistics & downloads: |
Abstract page: | 287 | Full-text PDF : | 87 | References: | 38 |
|