no. 1
On extremal leaf status and internal status
RAIRO. Operations Research, Tome 56 (2022) no. 1, pp. 415-430

For a vertex u of a tree T, the leaf (internal, respectively) status of u is the sum of the distances from u to all leaves (internal vertices, respectively) of T. The minimum (maximum, respectively) leaf status of a tree T is the minimum (maximum, respectively) leaf statuses of all vertices of T. The minimum (maximum, respectively) internal status of a tree T is the minimum (maximum, respectively) internal statuses of all vertices of T. We characterize those trees with the smallest (largest, respectively) extremal (minimum and maximum) leaf status and extremal (minimum and maximum) internal status, respectively. We also study the corresponding extremal problems for trees with given parameters, including diameter or maximum degree.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2022010
Classification : 05C12, 05C35
Keywords: Minimum leaf status, maximum leaf status, minimum internal status, maximum internal status, extremal problem 
@article{RO_2022__56_1_415_0,
     author = {Guo, Haiyan and Zhou, Bo},
     title = {On extremal leaf status and internal status},
     journal = {RAIRO. Operations Research},
     pages = {415--430},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {1},
     doi = {10.1051/ro/2022010},
     mrnumber = {4379611},
     zbl = {1486.05073},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022010/}
}
TY  - JOUR
AU  - Guo, Haiyan
AU  - Zhou, Bo
TI  - On extremal leaf status and internal status
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 415
EP  - 430
VL  - 56
IS  - 1
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022010/
DO  - 10.1051/ro/2022010
LA  - en
ID  - RO_2022__56_1_415_0
ER  - 
%0 Journal Article
%A Guo, Haiyan
%A Zhou, Bo
%T On extremal leaf status and internal status
%J RAIRO. Operations Research
%D 2022
%P 415-430
%V 56
%N 1
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022010/
%R 10.1051/ro/2022010
%G en
%F RO_2022__56_1_415_0
Guo, Haiyan; Zhou, Bo. On extremal leaf status and internal status. RAIRO. Operations Research, Tome 56 (2022) no. 1, pp. 415-430. doi: 10.1051/ro/2022010

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

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

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

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

[5] M. Cheng, H. Lin and B. Zhou, Minimum status of series-reduced trees with given parameters. Bull. Braz. Math. Soc. (N.S.) (2021) DOI: . | DOI | MR | Zbl

[6] A. A. Dobrynin and R. Sharafdini, Stepwise transmission irregular graphs. Appl. Math. Comput. 371 (2020) 124949. | MR | Zbl | DOI

[7] K. Durant and S. Wagner, On the centroid of increasing trees. Discrete Math. Theor. Comput. Sci. 21 (2019) Paper 8. | MR | Zbl

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

[9] C. Liang, B. Zhou and H. Guo, Minimum status, matching and domination of graphs. Comput. J. 64 (2021) 1384–1392. | MR | DOI

[10] H. Lin and B. Zhou, Which numbers are status differences?. Appl. Math. Comput. 399 (2021). | MR | Zbl

[11] 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

[12] Z. Peng and B. Zhou, Minimun status of trees with given parameters. RAIRO. Oper. Res. 55 (2021) S765–S785. | MR | Zbl | Numdam | DOI

[13] K. Pravas and A. Vijayakumar, The median problem on k-partite graphs. Discuss. Math. Graph Theory 35 (2015) 439–446. | MR | Zbl | DOI

[14] P. Qiao and X. Zhan, The relation between the number of leaves of a tree and its diameter. Czechoslovak Math. J. (2021). DOI: . | DOI | MR | Zbl

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

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

[17] P. J. Slater, Centers to centroids in graphs. J. Graph Theory 2 (1978) 209–222. | MR | Zbl | DOI

[18] H. Smith, L. Székely, H. Wang and S. Yuan, On different “middle parts” of a tree. Electron. J. Combin. 25 (2018) Paper 3.17. | MR | Zbl | DOI

[19] 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

[20] H. Wang, Centroid, leaf-centroid, and internal-centroid. Graphs Combin. 31 (2015) 783–793. | MR | Zbl | DOI

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

Cité par Sources :