Geodesic
On the extremal values of ratios of number of paths
Ars Mathematica Contemporanea, Tome 3 (2010) no. 2, pp. 215-235.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

In this paper, we analyze the ratios of the numbers of paths pi(G) and pj(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.
DOI : 10.26493/1855-3974.73.613
Keywords: Extremal graph, path, push to leaves 
@article{10_26493_1855_3974_73_613,
     author = {Damir Vuki\v{c}evi\'c and Toma\v{z} Pisanski},
     title = {On the extremal values of ratios of number of paths},
     journal = {Ars Mathematica Contemporanea},
     pages = {215--235},
     publisher = {mathdoc},
     volume = {3},
     number = {2},
     year = {2010},
     doi = {10.26493/1855-3974.73.613},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.73.613/}
}
TY  - JOUR
AU  - Damir Vukičević
AU  - Tomaž Pisanski
TI  - On the extremal values of ratios of number of paths
JO  - Ars Mathematica Contemporanea
PY  - 2010
SP  - 215
EP  - 235
VL  - 3
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.73.613/
DO  - 10.26493/1855-3974.73.613
LA  - en
ID  - 10_26493_1855_3974_73_613
ER  - 
%0 Journal Article
%A Damir Vukičević
%A Tomaž Pisanski
%T On the extremal values of ratios of number of paths
%J Ars Mathematica Contemporanea
%D 2010
%P 215-235
%V 3
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.73.613/
%R 10.26493/1855-3974.73.613
%G en
%F 10_26493_1855_3974_73_613
Damir Vukičević; Tomaž Pisanski. On the extremal values of ratios of number of paths. Ars Mathematica Contemporanea, Tome 3 (2010) no. 2, pp. 215-235. doi : 10.26493/1855-3974.73.613. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.73.613/

Cité par Sources :