ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Relation between Randić index and average distance of trees
    Cygan, Marek ; Pilipczuk, Michał ; Škrekovski, Riste
    The Randić index ▫$R(G)$▫ of a graph ▫$G$▫ is the sum of weights ▫$(\deg(u) \deg(v))^{-0.5}$▫ over all edges ▫$uv$▫ of ▫$G$▫, where ▫$\deg(v)$▫ denotes the degree of a vertex ▫$v$▫. We prove that for ... any tree ▫$T$▫ with ▫$n_1$▫ leaves ▫$R(T) \ge {\rm ad}(T) + \max(0, \sqrt{n_1}-2)$▫, where ▫${\rm ad}(T)$▫ is the average distance between vertices of ▫$T$▫. As a consequence we resolve the conjecture ▫$R(G) \ge {\rm ad}(G)$▫ given by Fajtlowicz in 1988 for the case when ▫$G$▫ is a tree.
    Source: Match : communications in mathematical and in computer chemistry. - ISSN 0340-6253 (Vol. 66, no. 2, 2011, str. 605-612)
    Type of material - article, component part
    Publish date - 2011
    Language - english
    COBISS.SI-ID - 16589401

    Link(s):

    http://match.pmf.kg.ac.rs/electronic_versions/match66/n2/match66%282%29_605-612.pdf

Shelf entry