Some results about the connectivity of trees

Pesquisa Operacional

Lilian Markenzon²  Nair Maria Maia De Abreu¹  Luciana Lee¹ 

[1] ,Universidade Federal do Rio de Janeiro NCE ,Brazil

关键词: trees;    internal degree sequence;    algebraic connectivity;   

DOI  :  10.1590/S0101-74382013000100008

来源: SciELO

【 摘 要 】

The second smallest Laplacian eigenvalue of a graph G is called algebraic connectivity, denoted a(G). The ordering of trees via this graph invariant is frequently studied in the literature. In this paper, we present a new invariant, the Internal Degree Sequence (IDS), that also supports an accurate evaluation of the connectivity of trees. We compare the IDS with a(G) for all elements in six classes of trees known to have the largest algebraic connectivity and we show that the IDS provides a strict total ordering of the elements of these classes. This result is also proved for a subclass of trees of diameter 4.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License