Minimum status of trees with given parameters
RAIRO. Operations Research, Tome 55 (2021), pp. S765-S785

The status of a vertex v in a connected graph G is defined as the sum of the distances from v to all other vertices in G. The minimum status of G is the minimum of status of all vertices of G. We give the smallest and largest values for the minimum status of a tree with fixed parameters such as the diameter, the number of pendant vertices, the number of odd vertices, and the number of vertices of degree two, and characterize the unique extremal trees.

DOI : 10.1051/ro/2020015
Classification : 05C12, 05C35, 05C90
Keywords: Minimum status, closeness centrality, diameter, pendant vertices, odd vertices, series-reduced trees 
@article{RO_2021__55_S1_S765_0,
     author = {Peng, Zhene and Zhou, Bo},
     title = {Minimum status of trees with given parameters},
     journal = {RAIRO. Operations Research},
     pages = {S765--S785},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020015},
     mrnumber = {4223147},
     zbl = {1469.05032},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020015/}
}
TY  - JOUR
AU  - Peng, Zhene
AU  - Zhou, Bo
TI  - Minimum status of trees with given parameters
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S765
EP  - S785
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020015/
DO  - 10.1051/ro/2020015
LA  - en
ID  - RO_2021__55_S1_S765_0
ER  - 
%0 Journal Article
%A Peng, Zhene
%A Zhou, Bo
%T Minimum status of trees with given parameters
%J RAIRO. Operations Research
%D 2021
%P S765-S785
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020015/
%R 10.1051/ro/2020015
%G en
%F RO_2021__55_S1_S765_0
Peng, Zhene; Zhou, Bo. Minimum status of trees with given parameters. RAIRO. Operations Research, Tome 55 (2021), pp. S765-S785. doi: 10.1051/ro/2020015

M. Aouchiche and P. Hansen, Nordhaus-Gaddum relations for proximity and remoteness in graphs. Comput. Math. Appl. 59 (2010) 2827–2835. | MR | Zbl | DOI

M. Aouchiche and P. Hansen, Proximity and remoteness in graphs: results and conjectures. Networks 58 (2011) 95–102. | MR | Zbl | DOI

M. Aouchiche and P. Hansen, Proximity, remoteness and distance eigenvalues of a graph. Discrete Appl. Math. 213 (2016) 17–25. | MR | Zbl | DOI

M. Aouchiche and P. Hansen, Proximity, remoteness and girth in graphs. Discrete Appl. Math. 222 (2017) 31–39. | MR | Zbl | DOI

M. Aouchiche, G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. 20. Automated comparison of graph invariants. MATCH Commun. Math. Comput. Chem. 58 (2007) 365–384. | MR | Zbl

K. Balakrishnan, B. Brešar, M. Changat, S. Klavžar, A. Vesel and P. Žigert, Equal opportunity networks, distance-balanced graphs, and Wiener game. Discrete Optim. 12 (2014) 150–154. | MR | Zbl | DOI

F. Bergeron, P. Leroux and G. Labelle, Combinatorial Species and Tree-like Structures. Cambridge University Press, Cambridge (1998). | MR | Zbl

F. Buckley and M. Lewinter, A note on graphs with diameter-preserving spanning trees. J. Graph Theory 12 (1988) 525–528. | MR | Zbl | DOI

F. Buckley and F. Harary, Distance in Graphs. Addison-Wesley Publishing Company, Redwood City, CA (1990). | MR | Zbl

P. Dankelmann, Proximity, remoteness and minimum degree. Discrete Appl. Math. 184 (2015) 223–228. | MR | Zbl | DOI

A. A. Dobrynin, Infinite family of transmission irregular trees of even order. Discrete Math. 342 (2019) 74–77. | MR | Zbl | DOI

R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in graphs. Czechoslovak Math. J. 26 (1976) 283–296. | MR | Zbl | DOI

L. C. Freeman, Centrality in social networks. Conceptual clarification. Social Networks 1 (1979) 215–239. | DOI

J. Golbeck, Analyzing the Social Web. Morgan Kaufmann, Burlington, MA (2013) 25–44.

F. Harary, Status and contrastatus. Sociometry 22 (1959) 23–43. | MR | DOI

F. Harary and G. Prins, The number of homeomorphically irreducible trees, and other species. Acta Math. 101 (1959) 141–162. | MR | Zbl | DOI

J. Haslegrave, Extremal results on average subtree density of series-reduced trees. J. Combin. Theory Ser. B. 107 (2014) 26–41. | MR | Zbl | DOI

C. Jordan, Sur les assemblages de lignes. J. Reine Angew. Math. 70 (1869) 185–190. | MR | JFM

A. N. C. Kang and D. A. Ault, Some properties of a centroid of a free tree. Inf. Process. Lett. 4 (1975/76) 18–20. | MR | Zbl | DOI

O. Kariv and S. L. Hakimi, An algorithmic approach to network location problems. II: The p -medians. SIAM J. Appl. Math. 37 (1979) 539–560. | MR | Zbl | DOI

M. Krnc and R. Škrekovski, Centralization of transmission in networks. Discrete Math. 338 (2015) 2412–2420. | MR | Zbl | DOI

C. Liang, B. Zhou and H. Guo, Minimum status, matching and domination of graphs. To appear in: Comp. J. (2020) 10.1093/comjnl/bxaa057. | MR

H. Lin and B. Zhou, The distance spectral radius of graphs with given number of odd vertices. Electron. J. Linear Algebra 31 (2016) 286–305. | MR | Zbl | DOI

C. Lin, W. H. Tsai, J. L. Shang and Y. J. Zhang, Minimum statuses of connected graphs with fixed maximum degree and order. J. Comb. Optim. 24 (2012) 147–161. | MR | Zbl | DOI

S. Majstorović and G. Caporossi, Bounds and relations involving adjusted centrality of the vertices of a tree. Graphs Combin. 31 (2015) 2319–2334. | MR | Zbl | DOI

O. E. Polansky and D. Bonchev, The minimum distance number of trees. MATCH Commun. Math. Comput. Chem. 21 (1986) 341–344. | MR

R. Rissner and R. E. Burkard, Bounds on the radius and status of graphs. Networks 64 (2014) 76–83. | MR | Zbl | DOI

J. Sedlar, Remoteness, proximity and few other distance invariants in graphs. Filomat. 27 (2013) 1425–1435. | MR | Zbl | DOI

L. Šoltés, Transmission in graphs: a bound and vertex removing. Math. Slovaca 41 (1991) 11–16. | MR | Zbl

D. Vukičević and G. Caporossi, Network descriptors based on betweenness centrality and transmission and their extremal values. Discrete Appl. Math. 161 (2013) 2678–2686. | MR | Zbl | DOI

B. Zelinka, Medians and peripherians of trees. Arch. Math. (Brno) 4 (1968) 87–95. | MR | Zbl

Cité par Sources :