×
Xu, Ke Xiang; Das, Kinkar Ch.; Maden, Ayse Dilek

On a novel eccentricity-based invariant of a graph. (English) Zbl 1362.05044

Acta Math. Sin., Engl. Ser. 32, No. 12, 1477-1493 (2016).
Summary: 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(G) = \sum\nolimits_{{v_i}{v_j} \in V(G)} |{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.

Cited in 1 Review
Cited in 21 Documents

MSC:

05C12 Distance in graphs
05C35 Extremal problems in graph theory

Keywords:

eccentricity; non-self-centered graph; non-self-centrality number; third Zagreb eccentricity index; diameter
Cite Review PDF
Full Text: DOI

References:

[1] Abdo, H., Brandt, S., Dimitrov, D.: The total irregularity of a graph. Discrete Math. Theor. Comput. Sci.,16, 201-206 (2014) · Zbl 1288.05130
[2] Buckley, F.: Facility location problems. College Math. J.,78, 24-32 (1987) · Zbl 0995.90500 · doi:10.2307/2686313
[3] Balakrishnan, K., Brešar, B., Changat, M., et al.: Almost self-centered median and chordal graphs. Taiwanese J. Math.,16, 1911-1922 (2012) · Zbl 1252.05048
[4] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications, Macmillan Press, New York, 1976 · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[5] Chartrand, G., Gu, W., Schultz, M., et al.: Eccentric graphs. Networks,34 115-121 (1999) · Zbl 0959.90062 · doi:10.1002/(SICI)1097-0037(199909)34:2<115::AID-NET4>3.0.CO;2-K
[6] Das, K. C., Lee, D.-W., Graovac, A.: Some properties of the Zagreb eccentricity indices. ARS Mathematica Contemporanea,6, 117-125 (2013) · Zbl 1301.05098
[7] 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 · doi:10.1016/j.dam.2015.01.011
[8] Das, K. C., Xu, K., Gutman, I.: On Zagreb and Harary indices. MATCH Commun. Math. Comput. Chem.,70, 301-314 (2013) · Zbl 1299.05035
[9] Furtula, B., Gutman, I., Ediz, S.: On difference of Zagreb indices. Discrete Appl. Math.,178, 83-88 (2014) · Zbl 1300.05066 · doi:10.1016/j.dam.2014.06.011
[10] Hage, P., Harary, F.: Eccentricity and centrality in networks. Social Networks,17, 57-63 (1995) · doi:10.1016/0378-8733(94)00248-9
[11] Harary, F., Schwenk, A. J.: The number of caterpillars. Discrete Math.,6, 359-365 (1973) · Zbl 0266.05102 · doi:10.1016/0012-365X(73)90067-8
[12] Horoldagva, B., Das, K. C.: On comparing Zagreb indices for graphs. Hacettepe J. Math. Stat.,41, 223-230 (2012) · Zbl 1278.05129
[13] Horoldagva, B., Lee, S.-G.: Comparing Zagreb indices for connected graphs. Discrete Appl. Math.,158, 1073-1078 (2010) · Zbl 1230.05188 · doi:10.1016/j.dam.2010.02.013
[14] Hua, H., Zhang, S., Xu, K.: Further results on the eccentric distance sum. Discrete Appl. Math.,160, 170-180 (2012) · Zbl 1237.05058 · doi:10.1016/j.dam.2011.10.002
[15] Klavžar, S., Nadjafi-Arani, M. J.: Wiener index in weighted graphs via unification of Θ*-classes. European J. Combin.,36, 71-76 (2014) · Zbl 1284.05118 · doi:10.1016/j.ejc.2013.04.008
[16] Klavžar, S., Narayankar, K. P., Walikar, H. B.: Almost self-centered graphs. Acta Math. Sin., Engl. Ser.,27, 2343-2350 (2011) · Zbl 1260.05052 · doi:10.1007/s10114-011-9628-3
[17] Klavžar, S., Narayankar, K. P., Walikar, H. B., et al.: Almost-peripheral graphs. Taiwanese J. Math.,18, 463-471 (2014) · Zbl 1357.05032
[18] Klavžar, S., Yoomi Rho: On the Wiener index of generalized Fibonacci cubes and Lucas cubes. Discrete Appl. Math.,187, 155-160 (2015) · Zbl 1315.05044 · doi:10.1016/j.dam.2015.02.002
[19] Krnc, M., Škrekovski, R.: Group centralization of network indices. Discrete Appl. Math.,186, 147-157 (2015) · Zbl 1312.91078 · doi:10.1016/j.dam.2015.01.007
[20] Liu, M., Liu, B.: The second Zagreb indices of unicyclic graphs with given degree sequences. Discrete Appl. Math.,167, 217-221 (2014) · Zbl 1284.05066 · doi:10.1016/j.dam.2013.10.033
[21] Todeschini, R., Consonni, V.: Handbook of molecular descriptors, Wiley-VCH, Weinheim, 2000 · doi:10.1002/9783527613106
[22] Todeschini, R., Consonni, V.: Molecular descriptors for chemoinformatics, vol I, vol II, Wiley-VCH, Weinheim, 2009, 934-938 · doi:10.1002/9783527628766
[23] Tomescu, I.: Some extremal properties of the degree distance of a graph. Discrete Appl. Math.,98, 159-163 (1999) · Zbl 0936.05038 · doi:10.1016/S0166-218X(99)00117-1
[24] Tomescu, I.: Properties of connected graphs having minimum degree distance. Discrete Math.,309, 2745-2748 (2009) · Zbl 1182.05076 · doi:10.1016/j.disc.2008.06.031
[25] Tomescu, I.: Ordering connected graphs having small degree distances. Discrete Appl. Math.,158, 1714-1717 (2010) · Zbl 1208.05021 · doi:10.1016/j.dam.2010.05.023
[26] 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)
[27] Wiener, H.: Structural determination of paraffin boiling points. J. Am. Chem. Soc.,69, 17-20 (1947) · doi:10.1021/ja01193a005
[28] Xu, K.: Trees with the seven smallest and eight greatest Harary indices. Discrete Appl. Math.,160, 321-331 (2012) · Zbl 1237.05061 · doi:10.1016/j.dam.2011.08.014
[29] Xu, K., Das, K. C.: On Harary index of graphs. Discrete Appl. Math.,159, 1631-1640 (2011) · Zbl 1228.05143 · doi:10.1016/j.dam.2011.06.003
[30] 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 · doi:10.1016/j.jmaa.2015.08.027
[31] Xu, K., Das, K. C., Trinajstić, N.: The Harary Index of a Graph, Springer, Heidelberg, 2015 · Zbl 1365.05005 · doi:10.1007/978-3-662-45843-3
[32] 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) · Zbl 1464.05140
[33] Yu, G., Feng, L.: On the connective eccentricity index of graphs. MATCH Commun. Math. Comput. Chem.,69, 611-628 (2013) · Zbl 1299.05112
[34] Yu, G., Feng, L., Ilić, A.: On the eccentric distance sum of trees and unicyclic graphs. J. Math. Anal. Appl.,375, 99-107 (2011) · Zbl 1282.05077 · doi:10.1016/j.jmaa.2010.08.054
[35] 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) · Zbl 1298.05096 · doi:10.1016/j.jmaa.2014.06.050
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.