Light graphs in families of outerplanar graphs

被引:6
作者
Fabrici, Igor [1 ]
机构
[1] Safarik Univ, Inst Math, Kosice 04154, Slovakia
关键词
outerplanar graph; light graph; path; triangle; 3-star;
D O I
10.1016/j.disc.2005.11.058
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We prove that every 2-connected outerplanar graph of order at least k (k >= 3) contains a path on k vertices with all vertices of degree at most k + 3 and a path on k vertices with degree sum at most 4k - 2. Further, every 2-connected outerplanar graph without adjacent vertices with degree sum <= 5 contains a triangle C(3) with vertices of degrees 2, 4 and b, 4 <= b <= 6, and a 3-star K(1,3) with central vertex of degree 4 and remaining vertices of degrees 2, 2 and b, 4 <= b <= 6, Moreover, all bounds are best possible. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码:866 / 872
页数:7
相关论文
共 14 条
  • [1] BORODIN O., 1989, MAT ZAMETKI, V46, P9
  • [2] CHARTRAND G, 1967, ANN I H POINCARE B, V3, P433
  • [3] Subgraphs with restricted degrees of their vertices in planar 3-connected graphs
    Fabrici, I
    Jendrol, S
    [J]. GRAPHS AND COMBINATORICS, 1997, 13 (03) : 245 - 250
  • [4] On vertex-degree restricted paths in polyhedral graphs
    Fabrici, I
    Hexel, E
    Jendrol, S
    Walther, H
    [J]. DISCRETE MATHEMATICS, 2000, 212 (1-2) : 61 - 73
  • [5] FABRICI I, UNPUB GRAPHS COMBIN
  • [6] Hackmann A, 2001, ARS COMBINATORIA, V60, P181
  • [7] Harary F., 1972, Graph Theory
  • [8] Jendrol S, 1999, DISCRETE MATH, V197, P453
  • [9] JENDROL S, UNPUB DISCRETE MATH
  • [10] Jendrol S., 1996, DISCUSS MATH GRAPH T, V16, P207, DOI DOI 10.7151/DMGT.1035