ON THE MINIMUM WEIGHT OF A 3-CONNECTED 1-PLANAR GRAPH

被引：2
作者：
Lu, Zai Ping [1 ]
Song, Ning [1 ]
机构：
[1] Nankai Univ, Ctr Combinator, LPMC TJKLC, Tianjin 300071, Peoples R China
来源：
BULLETIN OF THE KOREAN MATHEMATICAL SOCIETY | 2017年 / 54卷 / 03期
关键词：
1-planar graph; weight; light edge; EDGE COLORINGS;
D O I：
10.4134/BKMS.b160296
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A graph is called 1-planar if it can be drawn in the Euclidean plane R-2 such that each edge is crossed by at most one other edge. The weight of an edge is the sum of degrees of two ends. It is known that every planar graph of minimum degree delta >= 3 has an edge with weight at most 13. In the present paper, we show the existence of edges with weight at most 25 in 3-connected 1-planar graphs.
引用
收藏
页码：763 / 787
页数：25
相关论文
共 25 条
  • [21] Light structures in 1-planar graphs with an application to linear 2-arboricity
    Liu, Juan
    Hu, Xiaoxue
    Wang, Weifan
    Wang, Yiqiao
    DISCRETE APPLIED MATHEMATICS, 2019, 267 : 120 - 130
  • [22] Minimum Connected Dominating Set Algorithm with Weight in Wireless Sensor Networks
    Zhang Jing
    Jia Chun-fu
    2008 4TH INTERNATIONAL CONFERENCE ON WIRELESS COMMUNICATIONS, NETWORKING AND MOBILE COMPUTING, VOLS 1-31, 2008, : 3973 - 3976
  • [23] Approximation algorithms for minimum (weight) connected k-path vertex cover
    Li, Xiaosong
    Zhang, Zhao
    Huang, Xiaohui
    DISCRETE APPLIED MATHEMATICS, 2016, 205 : 101 - 108
  • [24] 1-planar Graphs without 4-cycles or 5-cycles are 5-colorable
    Song, Li-li
    Sun, Lei
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2022, 38 (01): : 169 - 177
  • [25] Breaking the O(ln n) Barrier: An F hanced Approximation Algorithm for Fault-Tolerant Minimum Weight connected Dominating Set
    Zhou, Jiao
    Zhang, Zhao
    Tang, Shaojie
    Huang, Xiaohui
    Duc, Ding-Zhu
    INFORMS JOURNAL ON COMPUTING, 2018, 30 (02) : 225 - 235
123