Skip to Main content Skip to Navigation
Journal articles

New Upper Bounds for the Heights of Some Light Subgraphs in 1-Planar Graphs with High Minimum Degree

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990621
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 4:37:03 PM
Last modification on : Thursday, September 7, 2017 - 1:03:39 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:46:56 PM

File

1527-6454-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00990621, version 1

Collections

Citation

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. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.9--16. ⟨hal-00990621⟩

Share

Metrics

Record views

307

Files downloads

994