×

Tree with maximum non-self-centrality number among all trees of fixed order and maximum degree. (English) Zbl 1484.05109

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\) [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 §5(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}\).

MSC:

05C35 Extremal problems in graph theory
05C05 Trees
05C12 Distance in graphs
05C40 Connectivity

Citations:

Zbl 1362.05044
Full Text: DOI

References:

[1] Buckley, F., Facility location problems, College Math. J, 78, 24-32 (1987) · Zbl 0995.90500
[2] Das, K. C.; Lee, D. W.; Graovac, A., Some properties of the Zagreb eccentricity indices, ARS Math Contemp., 6, 117-125 (2013) · Zbl 1301.05098
[3] Das, K. C.; Nadjafi-Arani, M. J., Comparison between the Szeged index and the eccentric connectivity index, Discrete Appl. Math., 186, 74-86 (2015) · Zbl 1311.05095
[4] Das, K. C.; Xu, K.; Gutman, I., On Zagreb and Harary indices, MATCH Commun. Math. Comput. Chem., 70, 301-314 (2013) · Zbl 1299.05035
[5] Hage, P.; Harary, F., Eccentricity and centrality in networks, Social Networks, 17, 57-63 (1995)
[6] Hua, H.; Zhang, S.; Xu, K., Further results on the eccentric distance sum, Discrete Appl. Math., 160, 170-180 (2012) · Zbl 1237.05058
[7] Klavzar, S.; Nadjafi-Arani, M. J., Wiener index in weighted graphs via unification of \(\Theta^\ast \)-classes, European J. Combin., 36, 71-76 (2014) · Zbl 1284.05118
[8] Klavzar, S.; Rho, Y., On the Wiener index of generalized Fibonacci cubes and Lucas cubes, Discrete Appl. Math., 187, 155-160 (2015) · Zbl 1315.05044
[9] Tohti, A.; Vumar, E., A note on non-self-centrality number of a graph, J. Xinjiang University, 35, 42-46 (2018) · Zbl 1399.05116
[10] Vukicevic, D.; Graovac, A., Note on the comparison of the first and second normalized Zagreb eccentricity indices, Acta Chim. Slov., 57, 524-528 (2010)
[11] Wiener, H., Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69, 17-20 (1947)
[12] Xu, K., Trees with the seven smallest and eight greatest Harary indices, Discrete Appl. Math., 160, 321-331 (2012) · Zbl 1237.05061
[13] Xu, K.; Alizadeh, Y.; Das, K. C., On two eccentricity-based topological indices of graphs, Discrete Appl. Math., 233, 240-250 (2017) · Zbl 1372.05119
[14] Xu, K.; Das, K. C., On Harary index of graphs, Discrete Appl. Math., 159, 1631-1640 (2011) · Zbl 1228.05143
[15] Xu, K.; Das, K. C.; Liu, H., Some extremal results on the connective eccentricity index of graphs, J. Math. Anal. Appl., 433, 803-817 (2016) · Zbl 1321.05142
[16] Xu, K.; Das, K. C.; Maden, A. D., On a novel eccentricity-based invariant of a graph, Acta Math. Sin. (Engl. Ser.), 32, 1477-1493 (2016) · Zbl 1362.05044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.