Light subgraphs in graphs with average degree at most four

被引:0
作者
Wang, Tao [1 ,2 ]
机构
[1] Henan Univ, Inst Appl Math, Kaifeng 475004, Peoples R China
[2] Henan Univ, Sch Math & Stat, Kaifeng 475004, Peoples R China
基金
中国国家自然科学基金;
关键词
Light subgraphs; Average degree; Normal plane maps; Planar graph; 3-PATHS;
D O I
10.1016/j.disc.2016.04.020
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A graph H is said to be light in a family G of graphs if at least one member of G contains a copy of H and there exists an integer lambda(H, G) such that each member G of G with a copy of H also has a copy K of H such that deg(G)(v) <= lambda(H, G) for all v is an element of V(K). In this paper, we study the light graphs in the class of graphs with small average degree, including the plane graphs with some restrictions on girth. We proved that: 1. If G is a graph with delta(G) = 2, average degree less than 14/5 and without (2, 2, infinity)-triangles, then G has one of the following configurations: a (2, 2, 13(-), 2)-path, a (2, 3(-), 3(-))-path and a (4; 2, 2, 2, 3(-))-star. 2. If G is a plane graph with delta(G) >= 2 and face size at least 7, then G has a (2, 2, 5(-))-path, or a (2, 5(-), 2)-path or a (3, 3, 2, 3)-path. 3. If G is a graph with delta(G) = 2, average degree less than 3 and without (2, 2, infinity)-triangles, then G has one of the following configurations: a (2, 3(-), 3(-))-path, a (2, 2, infinity, 2)-path, a (2, 2, 4, 3)-path, a (4; 2, 2, 2, 6(-))-star, a (4; 2, 2, 3, 5(-))-star, a (4; 2, 3, 3, 3)-star, a (5; 2, 2, 2, 2, 2)-star and a (5; 2, 2, 2, 2, 3)-star. 4. If G is a graph with delta(G) = 2, average degree less than 3 and without (2, 2, infinity)-triangles, then G has one of the following configurations: a (2, 3(-), 3(-))-path, a (2, 2, infinity, 2)-path, a (2, 2, 4, 3)-path, a (4; 2, 2, 2, 6(-))-star, a (2, 4, 3, 2)-path, a (2, 4, 3)-triangle, a (5; 2, 2, 2, 2, 2)-star and a (5; 2, 2, 2, 2, 3)-star. 5. If G is a graph with delta(G) >= 2 and average degree less than 10/3, then G has one of the following configurations: a (2, 2, infinity)-path, a (2, 3, 6(-))-path, a (3, 3, 3)-path, a (2, 4, 3(-))-path and a (2, 9(-), 2)-path. 6. If G is a graph with delta(G) = 3 and average degree less than 4, then G contains a (4(-), 3, 7(-))-path, or a (5, 3, 5)-path or a (5, 3, 6)-path. 7. If G is a triangle-free normal plane map, then it contains one of the following configurations: a (3, 3, 3)-path, a (3, 3, 4)-path, a (3, 3, 5, 3)-path, a (4, 3, 4)-path, a (4, 3, 5)-path, a (5, 3, 5)-path, a (5, 3, 6)-path and a (3, 4, 3)-path. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码:2581 / 2591
页数:11
相关论文
共 15 条
  • [1] Aksenov VA, 2015, ELECTRON J COMB, V22
  • [2] Ando K., 1993, ANN M MATH SOC JAP
  • [3] Describing tight descriptions of 3-paths in triangle-free normal plane maps
    Borodin, O. V.
    Ivanova, A. O.
    [J]. DISCRETE MATHEMATICS, 2015, 338 (11) : 1947 - 1952
  • [4] Describing 3-paths in normal plane maps
    Borodin, O. V.
    Ivanova, A. O.
    Jensen, T. R.
    Kostochka, A. V.
    Yancey, M. P.
    [J]. DISCRETE MATHEMATICS, 2013, 313 (23) : 2702 - 2711
  • [5] BORODIN OV, 1989, J REINE ANGEW MATH, V394, P180
  • [6] BORODIN OV, J GRAPH THE IN PRESS
  • [7] A structural property of convex 3-polytopes
    Jendrol, S
    [J]. GEOMETRIAE DEDICATA, 1997, 68 (01) : 91 - 99
  • [8] Optimal unavoidable sets of types of 3-paths for planar graphs of given girth
    Jendrol', S.
    Macekova, M.
    Montassier, M.
    Sotak, R.
    [J]. DISCRETE MATHEMATICS, 2016, 339 (02) : 780 - 789
  • [9] Describing short paths in plane graphs of girth at least 5
    Jendrol', S.
    Macekova, M.
    [J]. DISCRETE MATHEMATICS, 2015, 338 (02) : 149 - 158
  • [10] Light subgraphs of graphs embedded in the plane-A survey
    Jendrol', S.
    Voss, H. -J.
    [J]. DISCRETE MATHEMATICS, 2013, 313 (04) : 406 - 421