Tree with maximum non-self-centrality number among all trees of fixed order and maximum degree (Q2078836): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:47, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Tree with maximum non-self-centrality number among all trees of fixed order and maximum degree |
scientific article |
Statements
Tree with maximum non-self-centrality number among all trees of fixed order and maximum degree (English)
0 references
4 March 2022
0 references
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}\).
0 references
non-self-centrality
0 references
radius
0 references
eccentricity
0 references
fixed maximum degree
0 references