Xin Zhang ; Jian-Liang Wu ; Guizhen Liu - New Upper Bounds for the Heights of Some Light Subgraphs in 1-Planar Graphs with High Minimum Degree

dmtcs:560 - Discrete Mathematics & Theoretical Computer Science, September 10, 2011, Vol. 13 no. 3 - https://doi.org/10.46298/dmtcs.560
New Upper Bounds for the Heights of Some Light Subgraphs in 1-Planar Graphs with High Minimum DegreeArticle

Authors: Xin Zhang ORCID1; Jian-Liang Wu 1; Guizhen Liu 1

  • 1 School of Mathematics [Shandong]

Combinatorics

[en]
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph of minimum degree 6 contains a copy of 4-cycle with all vertices of degree at most 19. In addition, we also show that the complete graph K 4 is light in the family of 1-planar graphs of minimum degree 7, with its height at most 11.

https://doi.org/10.46298/dmtcs.560
Source: HAL:hal-00990621v1
Volume: Vol. 13 no. 3
Section: Combinatorics
Published on: September 10, 2011
Imported on: May 5, 2010
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

Share and export

Consultation statistics

This page has been seen 536 times.
This article's PDF has been downloaded 521 times.