Abstract
In this paper, for the purpose of measuring the non-self-centrality extent of non-selfcentered graphs, a novel eccentricity-based invariant, named as non-self-centrality number (NSC number for short), of a graph G is defined as follows: \(N\left( G \right) = \sum\nolimits_{{v_i}{v_j} \in V\left( G \right)} {|{e_i} - {e_j}|} \) where the summation goes over all the unordered pairs of vertices in G and e i is the eccentricity of vertex v i in G, whereas the invariant will be called third Zagreb eccentricity index if the summation only goes over the adjacent vertex pairs of graph G. In this paper, we determine the lower and upper bounds on N(G) and characterize the corresponding graphs at which the lower and upper bounds are attained. Finally we propose some attractive research topics for this new invariant of graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abdo, H., Brandt, S., Dimitrov, D.: The total irregularity of a graph. Discrete Math. Theor. Comput. Sci., 16, 201–206 (2014)
Buckley, F.: Facility location problems. College Math. J., 78, 24–32 (1987)
Balakrishnan, K., Brešar, B., Changat, M., et al.: Almost self-centered median and chordal graphs. Taiwanese J. Math., 16, 1911–1922 (2012)
Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications, Macmillan Press, New York, 1976
Chartrand, G., Gu, W., Schultz, M., et al.: Eccentric graphs. Networks, 34 115–121 (1999)
Das, K. C., Lee, D.-W., Graovac, A.: Some properties of the Zagreb eccentricity indices. ARS Mathematica Contemporanea, 6, 117–125 (2013)
Das, K. C., Nadjafi-Arani, M. J.: Comparison between the Szeged index and the eccentric connectivity index. Discrete Appl. Math., 186, 74–86 (2015)
Das, K. C., Xu, K., Gutman, I.: On Zagreb and Harary indices. MATCH Commun. Math. Comput. Chem., 70, 301–314 (2013)
Furtula, B., Gutman, I., Ediz, S.: On difference of Zagreb indices. Discrete Appl. Math., 178, 83–88 (2014)
Hage, P., Harary, F.: Eccentricity and centrality in networks. Social Networks, 17, 57–63 (1995)
Harary, F., Schwenk, A. J.: The number of caterpillars. Discrete Math., 6, 359–365 (1973)
Horoldagva, B., Das, K. C.: On comparing Zagreb indices for graphs. Hacettepe J. Math. Stat., 41, 223–230 (2012)
Horoldagva, B., Lee, S.-G.: Comparing Zagreb indices for connected graphs. Discrete Appl. Math., 158, 1073–1078 (2010)
Hua, H., Zhang, S., Xu, K.: Further results on the eccentric distance sum. Discrete Appl. Math., 160, 170–180 (2012)
Klavžar, S., Nadjafi-Arani, M. J.: Wiener index in weighted graphs via unification of Θ*-classes. European J. Combin., 36, 71–76 (2014)
Klavžar, S., Narayankar, K. P., Walikar, H. B.: Almost self-centered graphs. Acta Math. Sin., Engl. Ser., 27, 2343–2350 (2011)
Klavžar, S., Narayankar, K. P., Walikar, H. B., et al.: Almost-peripheral graphs. Taiwanese J. Math., 18, 463–471 (2014)
Klavžar, S., Yoomi Rho: On the Wiener index of generalized Fibonacci cubes and Lucas cubes. Discrete Appl. Math., 187, 155–160 (2015)
Krnc, M., Škrekovski, R.: Group centralization of network indices. Discrete Appl. Math., 186, 147–157 (2015)
Liu, M., Liu, B.: The second Zagreb indices of unicyclic graphs with given degree sequences. Discrete Appl. Math., 167, 217–221 (2014)
Todeschini, R., Consonni, V.: Handbook of molecular descriptors, Wiley-VCH, Weinheim, 2000
Todeschini, R., Consonni, V.: Molecular descriptors for chemoinformatics, vol I, vol II, Wiley-VCH, Weinheim, 2009, 934–938
Tomescu, I.: Some extremal properties of the degree distance of a graph. Discrete Appl. Math., 98, 159–163 (1999)
Tomescu, I.: Properties of connected graphs having minimum degree distance. Discrete Math., 309, 2745–2748 (2009)
Tomescu, I.: Ordering connected graphs having small degree distances. Discrete Appl. Math., 158, 1714–1717 (2010)
Vukičević, D., Graovac, A.: Note on the comparison of the first and second normalized Zagreb eccentricity indices. Acta Chim. Slov., 57, 524–528 (2010)
Wiener, H.: Structural determination of paraffin boiling points. J. Am. Chem. Soc., 69, 17–20 (1947)
Xu, K.: Trees with the seven smallest and eight greatest Harary indices. Discrete Appl. Math., 160, 321–331 (2012)
Xu, K., Das, K. C.: On Harary index of graphs. Discrete Appl. Math., 159, 1631–1640 (2011)
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)
Xu, K., Das, K. C., Trinajstić, N.: The Harary Index of a Graph, Springer, Heidelberg, 2015
Xu, K., Liu, M., Das, K. C., et al.: A survey on graphs extremal with respect to distance-based topological indices. MATCH Commun. Math. Comput. Chem., 71, 461–508 (2014)
Yu, G., Feng, L.: On the connective eccentricity index of graphs. MATCH Commun. Math. Comput. Chem., 69, 611–628 (2013)
Yu, G., Feng, L., Ilić, A.: On the eccentric distance sum of trees and unicyclic graphs. J. Math. Anal. Appl., 375, 99–107 (2011)
Yu, G., Qu, H., Tang, L., et al.: On the connective eccentricity index of trees and unicyclic graphs with given diameter. J. Math. Anal. Appl., 420, 1776–1786 (2014)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by NSFC (Grant No. 11201227), China Postdoctoral Science Foundation (Grant Nos. 2013M530253, 2014T70512), Natural Science Foundation of Jiangsu Province (Grant No. BK20131357), National Research Foundation funded by the Korean government (Grant Nos. 2013R1A1A2009341), TUBITAK and Scientific Research Project Office (BAP) of Selçuk University
Rights and permissions
About this article
Cite this article
Xu, K.X., Das, K.C. & Maden, A.D. On a novel eccentricity-based invariant of a graph. Acta. Math. Sin.-English Ser. 32, 1477–1493 (2016). https://doi.org/10.1007/s10114-016-5518-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10114-016-5518-z
Keywords
- Eccentricity
- non-self-centered graph
- non-self-centrality number
- third Zagreb eccentricity index
- diameter