×

Eccentricity of networks with structural constraints. (English) Zbl 1447.91117

This paper studies eccentricity centrality for bipartite graphs and tree graphs with structural restrictions. Eccentricity centrality \(E(v)=1/e(v)\) is defined as the reciprocal of the eccentricity of a node \(v\), and \(e(v)\) is the maximum distance between \(v\) and all nodes \(u\) in a connected graph \(G\). Define \(E_1(v)=\sum_{u\in V(G)}(E(v)-E(u))\). For a connected graph with bipartite sets \(K\) and \(L\) of sizes \(|K|=k\ge2\) and \(|L|=l\ge2\), it is shown \(E_1(v)\le l/6\) for \(k=2\) and \(v\in K\). Moreover, if \(k\ge3\), then \(E_1(v)\le (l/6)+(k-1)/4\). On estimating the eccentricity centrality of trees with prescribed order and maximum degree, a scheme dubbed as \(S\)-enumerations has been developed to label the vertices of a tree in the characterization of trees with maximum eccentricity.

MSC:

91D30 Social networks; opinion dynamics
05C35 Extremal problems in graph theory
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Bonacich, Simultaneous group and individual centralities, Soc. Netw. 13 (1991) 155-168. doi:10.1016/0378-8733(91)90018-O
[2] S.P. Borgatti and M.G. Everett, Network analysis of 2-mode data, Soc. Netw. 19 (1997) 243-269. doi:10.1016/S0378-8733(96)00301-2
[3] A. Davis, B.B. Gardner and M.R. Gardner, Deep South: A Social Anthropological Study of Caste and Class (University of Chicago Press, Chicago, 1941).
[4] R. Dunbar, The social brain hypothesis, Evolutionary Anthropology 6 (1998) 178-190. doi:10.1016/S0378-8733(96)00301-2
[5] M.G. Everett, P. Sinclair and P. Dankelmann, Some centrality results new and old, J. Math. Sociol. 28 (2004) 215-227. doi:10.1080/00222500490516671 · Zbl 1134.91576
[6] K. Faust, Centrality in affiliation networks, Soc. Netw. 19 (1997) 157-191. doi:10.1016/S0378-8733(96)00300-0
[7] L.C. Freeman, A set of measures of centrality based on betweenness, Sociometry 40 (1977) 35-41. doi:10.2307/3033543
[8] L.C. Freeman, Centrality in social networks conceptual clarification, Soc. Netw. 1 (979) 215-239.
[9] P. Hage and F. Harary, Eccentricity and centrality in networks, Soc. Netw. 17 (1995) 57-63. doi:10.1016/0378-8733(94)00248-9
[10] C. Heuberger and S. Wagner, Maximizing the number of independent subsets over trees with bounded degree, J. Graph Theory 58 (2008) 49-68. doi:10.1002/jgt.20294 · Zbl 1156.05042
[11] C. Heuberger and S. Wagner, Chemical trees minimizing energy and Hosoya index, J. Math. Chem. 46 (2009) 214-230. doi:10.1007/s10910-008-9456-6 · Zbl 1182.92071
[12] A. Ilić, Eccentric connectivity index, in: Novel Molecular Structure Descriptors — Theory and Applications II, Mathematical Chemistry Monographs 9, I. Gutman and B. Furtula (Ed(s)), (University of Kragujevac and Faculty of Science Kragujevac, 2010) 139-168.
[13] C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math. 70 (1869) 185-190. doi:10.1515/crll.1869.70.185 · JFM 02.0344.01
[14] M. Krnc, J.-S. Sereni, R.Škrekovski and Z.B. Yilma, Closeness centralization measure for two-mode data of prescribed sizes, Netw. Sci. 4 (2016) 474-490. doi:0.1017/nws.2016.14
[15] J.A. McHugh, Algorithmic Graph Theory (Prentice-Hall, Inc., Upper Saddle River, NJ, 1990). · Zbl 0755.68056
[16] M.E.J. Newman, Networks: An Introduction (Oxford University Press, Oxford, 2010). doi:10.1093/acprof:oso/9780199206650.001.0001 · Zbl 1195.94003
[17] P. Sinclair, Betweenness centralization for bipartite graphs, J. Math. Sociol. 29 (2004) 25-31. doi:10.1080/00222500590889730 · Zbl 1063.05126
[18] P. Sinclair, Erratum: Betweenness centralization for bipartite graphs, J. Math. Sociol. 29 (2005) 263-264. doi:10.1080/00222500590961630 · Zbl 1079.05517
[19] P. Sinclair, Network centralization with the Gil Schmidt power centrality index, Soc. Netw. 31 (2009) 214-219. doi:10.1016/j.socnet.2009.04.004
[20] S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications (Cambridge University Press, Cambridge, 1994). doi:10.1017/CBO9780511815478 · Zbl 0926.91066
[21] D.B. West, Introduction to Graph Theory (Prentice Hall, Inc., Upper Saddle River, NJ, 1996). · Zbl 0845.05001
[22] G. Yu, L. Feng and A. Ilić, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99-107. · Zbl 1282.05077
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.