Geodesic
Trees with Unique Least Central Subtrees
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 811-828.

Voir la notice de l'article provenant de la source Library of Science

A subtree S of a tree T is a central subtree of T if S has the minimum eccentricity in the join-semilattice of all subtrees of T. Among all subtrees lying in the join-semilattice center, the subtree with minimal size is called the least central subtree. Hamina and Peltola asked what is the characterization of trees with unique least central subtree? In general, it is difficult to characterize completely the trees with unique least central subtree. Nieminen and Peltola [The subtree center of a tree, Networks 34 (1999) 272–278] characterized the trees with the least central subtree consisting just of a single vertex. This paper characterizes the trees having two adjacent vertices as a unique least central subtree.
Keywords: tree, central subtree, least central subtree 
@article{DMGT_2018_38_3_a11,
     author = {Kang, Liying and Shan, Erfang},
     title = {Trees with {Unique} {Least} {Central} {Subtrees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {811--828},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a11/}
}
TY  - JOUR
AU  - Kang, Liying
AU  - Shan, Erfang
TI  - Trees with Unique Least Central Subtrees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 811
EP  - 828
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a11/
LA  - en
ID  - DMGT_2018_38_3_a11
ER  - 
%0 Journal Article
%A Kang, Liying
%A Shan, Erfang
%T Trees with Unique Least Central Subtrees
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 811-828
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a11/
%G en
%F DMGT_2018_38_3_a11
Kang, Liying; Shan, Erfang. Trees with Unique Least Central Subtrees. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 811-828. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a11/

[1] S.P. Avann, Metric ternary distributive semi-latties, Proc. Amer. Math. Soc. 12 (1961) 407–414. doi:10.1090/S0002-9939-1961-0125807-5

[2] H. Bielak and M. Pańczyk, A self-stabilizing algorithm for finding weighted centroid in trees, Ann. Univ. Mariae Curie-Sk lodowska Sect. AI-Inform. 12(2) (2012) 27–37. doi:10.2478/v10065-012-0035-x

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[4] M.L. Brandeau and S.S. Chiu, An overview of representative problem in location research, Management Science 35 (1989) 645–674. doi:10.1287/mnsc.35.6.645

[5] S.L. Hakimi, Optimal locations of switching centers and the absolute centers and medians of a graph, Oper. Res. 12 (1964) 450–459. doi:10.1287/opre.12.3.450

[6] M. Hamina and M. Peltola, Least central subtrees, center, and centroid of a tree, Networks 57 (2011) 328–332. doi:10.1002/net.20402

[7] O. Kariv and S.L. Hakimi, An algorithm approach to network location problems . II: The p-medians, SIAM J. Appl. Math. 37 (1979) 539–560. doi:10.1137/0137041

[8] H.M. Mulder, The interval function of a graph, in: Mathematical Centre Tracts 132 (Mathematisch Centrum, Amsterdam, 1980).

[9] L. Nebeský, Median graphs, Comment. Math. Univ. Carolin. 12 (1971) 317–325.

[10] J. Nieminen and M. Peltola, The subtree center of a tree, Networks 34 (1999) 272–278. doi:10.1002/(SICI)1097-0037(199912)34:4h272::AID-NET6i3.0.CO;2-C

[11] K.B. Ried, Centroids to center in trees, Networks 21 (1991) 11–17. doi:10.1002/net.3230210103

[12] C. Smart and P.J. Slater, Center, median, and centroid subgraphs, Networks 34 (1999) 303–311. doi:10.1002/(SICI)1097-0037(199912)34:4h303::AID-NET10i3.0.CO;2-#

[13] J. Spoerhase and H.-C. Wirth, ( r, p )- Centroid problems on paths and trees, Theoret. Comput. Sci. 410 (2009) 5128–5137. doi:10.1016/j.tcs.2009.08.020

[14] A. Tamir, Improved complexity bounds for center location problems on networks by using dynamic data structures, SIAM J. Discrete Math. 1 (1988) 377–396. doi:10.1137/0401038

[15] B.C. Tansel, R.L. Francis and T.J. Lowe, Location on networks: a survey—Part I: the p-center and p-median problems, Management Science 29 (1983) 482–497. doi:10.1287/mnsc.29.4.482