Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs

100%

Czap J., Przybyło J., Škrabuľáková E.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 1

141-151

A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true for unbalanced ones. We prove that the maximal possible size of bipartite 1-planar graphs whose one partite set is much smaller than the other one tends towards 2n rather than 3n. In particular, we prove that if the size of the smaller partite set is sublinear in n, then |E| = (2 + o(1))n, while the same is not true otherwise.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Czap J.

1 Przybyło J.

1 Škrabuľáková E.

1 2016

Wyniki wyszukiwania

On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs