Comparative results between the number of subtrees and Wiener index of graphs

Autor:	Kexiang Xu, Jie Li, Zuwen Luo
Rok vydání:	2022
Předmět:	Management Science and Operations Research Computer Science Applications Theoretical Computer Science
Zdroj:	RAIRO - Operations Research. 56:2495-2511
ISSN:	2804-7303 0399-0559
DOI:	10.1051/ro/2022118
Popis:	For a graph G, we denote by N(G) the number of non-empty subtrees of G. If G is connected, its Wiener index W(G) is the sum of distances between all unordered pairs of vertices of G. In this paper we establish some comparative results between N and W. It is shown that N(G) > W(G) if G is a graph of order n ≥ 7 and diameter 2 or 3. Also some graphs are constructed with large diameters and N > W. Moreover, for a tree T ≇ Sn of order n, we prove that W(T) > N(T) if T is a starlike tree with maximum degree 3 or a tree with exactly two vertices of maximum degrees 3 one of which has two leaf neighbors, or a broom with klog2 n leaves. And a method is provided for constructing the graphs with N W. Finally several related open problems are proposed to the comparison between N and W.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b4df3624f7f8738f2b00c4d2171380bf https://doi.org/10.1051/ro/2022118 Zobrazit plný text záznamu