On the extremal values of the ratios of number of paths

被引：9
作者：
Vukicevic, Damir [1 ]
Pisanski, Tomaz [2 ,3 ]
机构：
[1] Univ Split, Dept Math, Fac Math & Nat Sci, HR-21000 Split, Croatia
[2] Univ Ljubljana, Ljubljana 1000, Slovenia
[3] IMFM, Dept Theoret Comp Sci, Ljubljana 1000, Slovenia
来源：
ARS MATHEMATICA CONTEMPORANEA | 2010年 / 3卷 / 02期
关键词：
Extremal graph; path; push to leaves; M-2; INDEXES; ZAGREB M-1;
D O I：
10.26493/1855-3974.73.613
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we analyze the ratios of the numbers of paths p(i) (G) and p(j) (G) of different length in graph G. Namely, we are interested in the extremal values of these ratios for acyclic and cyclic graphs with given maximal degree. The values of infinum and supremum for graphs with given maximal degree are obtained. Also, the infinum of these ratios for trees with given maximal degree are obtained. Suprema for trees of given maximal degree are given when ratios of paths of length 1 and 2 are observed, and when ratios of paths of lengths 1 and 3 are observed. As the main result, a linear algorithm (in terms of maximal degree) for finding suprema of the ratios of the numbers of paths of length 2 and 3 for trees with given maximal degree is presented.
引用
收藏
页码：215 / 235
页数：21
相关论文
共 11 条
  • [1] AOUCHICHE M, 2005, GLOBAL OPTIMIZATION
  • [2] Bollobas B., 2004, Extremal Graph Theory
  • [3] Gutman I, 2004, MATCH-COMMUN MATH CO, P83
  • [4] Hansen P, 2007, CROAT CHEM ACTA, V80, P165
  • [5] EXPLICIT CONSTRUCTION OF REGULAR GRAPHS WITHOUT SMALL CYCLES
    IMRICH, W
    [J]. COMBINATORICA, 1984, 4 (01) : 53 - 59
  • [6] Nikolic S, 2003, CROAT CHEM ACTA, V76, P113
  • [7] Todeschini R., 2008, Handbook of Molecular Descriptors
  • [8] Trinajstic N., 1992, Chemical Graph theory, V2
  • [9] Vukicevic D, 2008, MATCH-COMMUN MATH CO, V60, P37
  • [10] Vukicevic D, 2007, MATCH-COMMUN MATH CO, V57, P633
12