Tree with maximum non-self-centrality number among all trees of fixed order and maximum degree (Q2078836): Difference between revisions

In an undirected graph \(G=(V,E)\), the eccentricity of \(x\in V\) is \(e(x)=\max\{d(x,y)\mid y\in V\}\); the radius \(r=r(G)\) and the diameter \(d=d(G)\) are respectively the minimum and maximum eccentricity over all vertices of \(G\); the non-self-centrality (NSC) number \(N(G)\) is defined as \(\sum|e(x)-e(y)|\) summed over all unordered pairs \(x,y\in V\) [\textit{K. X. Xu} et al., Acta Math. Sin., Engl. Ser. 32, No. 12, 1477--1493 (2016; Zbl 1362.05044)]. \(\mathcal{T}(n,\Delta)\), with \(\Delta\ge4\), is the class of \(n\)-vertex trees with maximum degree \(\Delta\); a broom \(B_{n,\Delta}\in\mathcal{T}(n,\Delta)\) is a tree obtained by attaching \(\Delta-1\) pendent vertices to an end-vertex of a path with \(n-(\Delta-1)\) vertices. The authors' main result, in Theorem 6, is to resolve a question raised in \S5(iv) of the paper cited above: Let \(r\) be the radius of \(B_{n,\Delta}\). Then for any \(T\in\mathcal{T}(n,\Delta)\), \(n\ge 4\), we have \(N(T)\le r^2\Delta+r(r-1)\cdot\frac{2r-1}3\) if \(d(B_{n,\Delta})\) is even; and \(N(T)\le r(r-1)\cdot\frac{3\Delta+2(r-2)}3\) if \(d(B_{n,\Delta})\) is odd; with equality holding if and only if \(T\) is isomorphic to \(B_{n,\Delta}\).