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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.9--16
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990621
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:37:03
Dernière modification le : jeudi 7 septembre 2017 - 01:03:39
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:46:56

Fichier

1527-6454-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

244

Téléchargements de fichiers

178