Geodesic
Tree-like structure graphs with full diversity of balls
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 1, pp. 25-41.

Voir la notice de l'article provenant de la source Math-Net.Ru

Under study is the diversity of metric balls in connected finite ordinary graphs considered as a metric space with the usual shortest-path metric. We investigate the structure of graphs in which all balls of fixed radius i are distinct for each i less than the diameter of the graph. Let us refer to such graphs as graphs with full diversity of balls. For these graphs, we establish some properties connected with the existence of bottlenecks and find out the configuration of blocks in the graph. Using the obtained properties, we describe the tree-like structure graphs with full diversity of balls. Illustr. 8, bibliogr. 22.
Mots-clés : graph, tree-like structure graphs, metric ball, radius of a ball, number of balls, diversity vector of balls, full diversity of balls. 
@article{DA_2018_25_1_a1,
     author = {A. A. Evdokimov and T. I. Fedoryaeva},
     title = {Tree-like structure graphs with full diversity of balls},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {25--41},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2018},
     language = {ru},
     url = {https://geodesic-test.mathdoc.fr/item/DA_2018_25_1_a1/}
}
TY  - JOUR
AU  - A. A. Evdokimov
AU  - T. I. Fedoryaeva
TI  - Tree-like structure graphs with full diversity of balls
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 25
EP  - 41
VL  - 25
IS  - 1
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DA_2018_25_1_a1/
LA  - ru
ID  - DA_2018_25_1_a1
ER  - 
%0 Journal Article
%A A. A. Evdokimov
%A T. I. Fedoryaeva
%T Tree-like structure graphs with full diversity of balls
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 25-41
%V 25
%N 1
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DA_2018_25_1_a1/
%G ru
%F DA_2018_25_1_a1
A. A. Evdokimov; T. I. Fedoryaeva. Tree-like structure graphs with full diversity of balls. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 1, pp. 25-41. https://geodesic-test.mathdoc.fr/item/DA_2018_25_1_a1/

[1] A. A. Evdokimov, “Locally isometric embeddings of graphs and the metric prolongation property”, Discrete Analysis and Operations Research, Math. Its Appl., 355, Kluwer Acad. Publ., Dordrecht, 1996, 7–14 | MR | Zbl

[2] A. A. Evdokimov, E. P. Kutsenogaya, T. I. Fedoryaeva, “On the full diversity of balls for graphs”, Prikl. Discretn. Mat., Prilozh., 2016, no. 9, 110–112 (Russian) | DOI

[3] A. A. Evdokimov, T. I. Fedoryaeva, “On the problem of characterizing the diversity vectors of balls”, J. Appl. Ind. Math., 8:2 (2014), 190–195 | DOI | MR

[4] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994 | MR | MR

[5] K. L. Rychkov, “Sufficient conditions for the existence of a graph with a given variety of balls”, J. Appl. Ind. Math., 1:3 (2007), 380–385 | DOI | MR | Zbl

[6] T. I. Fedoryaeva, “Operations and isometric embeddings of graphs related to the metric prolongation property”, Operations Research and Discrete Analysis, Math. Its Appl., 391, Kluwer Acad. Publ., Dordrecht, 1997, 31–49 | MR | Zbl | Zbl

[7] T. I. Fedoryaeva, “Variety of balls in the metric spaces of trees”, Diskretn. Anal. Issled. Oper. Ser. 1, 12:3 (2005), 74–84 (Russian) | MR | Zbl

[8] T. I. Fedoryaeva, “Diversity vectors of balls in graphs and estimates of the components of the vectors”, J. Appl. Ind. Math., 2:3 (2008), 341–356 | DOI | MR | Zbl

[9] T. I. Fedoryaeva, “Exact upper estimates of the number of different balls of given radius for graphs with fixed number of vertices and diameter”, Diskretn. Anal. Issled. Oper., 16:6 (2009), 74–92 (Russian) | MR | Zbl

[10] T. I. Fedoryaeva, “On the graphs with given diameter, number of vertices, and local diversity of balls”, J. Appl. Ind. Math., 5:1 (2011), 44–50 | DOI | MR | Zbl

[11] T. I. Fedoryaeva, “Majorants and minorants for the classes of graphs with fixed diameter and number of vertices”, J. Appl. Ind. Math., 7:2 (2013), 153–165 | DOI | MR

[12] T. I. Fedoryaeva, “Structure of the diversity vector of balls of a typical graph with given diameter”, Sib. Elektron. Mat. Izv., 13 (2016), 375–387 (Russian) | DOI | MR

[13] Guo J., Volkmann L., “A generalization of Menger's theorem for certain block-cactus graphs”, Graphs Comb., 11:1 (1995), 49–52 | DOI | MR

[14] Harary F., “A characterization of block-graphs”, Can. Math. Bull., 6:1 (1963), 1–6 | DOI | MR

[15] Harary F., Graph theory, Addison-Wesley, Reading, MA, 1969, 273 pp. | MR

[16] Harary F., Palmer E., Graphical enumeration, Acad. Press, New York, 1973, 263 pp. | MR

[17] Harary F., Uhlenbeck G. E., “On the number of Husimi trees”, Proc. Nat. Acad. Sci. USA, 39:4 (1953), 315–322 | DOI | MR

[18] Lan J. K., Chang G. J., “Algorithmic aspects of the $k$-domination problem in graphs”, Discrete Appl. Math., 161:10–11 (2013), 1513–1520 | DOI | MR

[19] Paten B., Diekhans M., Earl D., John J. St., Ma J., Suh B., Haussler D., “Cactus graphs for genome comparisons”, Proc. 14th Annu. Int. Conf. RECOMB2010 (Lisbon, Portugal, Apr. 25–28, 2010), Lect. Notes Bioinform., 6044, Springer, Heidelberg, 2010, 410–425

[20] Randerath B., Volkmann L., “A characterization of well covered block-cactus graphs”, Australas. J. Comb., 9 (1994), 307–314 | MR

[21] Topp J., Volkmann L., “Well covered and well dominated block graphs and unicyclic graphs”, Math. Pannonica, 1:2 (1990), 55–66 | MR

[22] Zmazek B., Zerovnik J., “Estimating the traffic on weighted cactus networks in linear time”, Proc. 9th Int. Conf. Information Visualization (London, England, July 6–8, 2005), IEEE Comput. Soc., Los Alamitos, 2005, 536–541 | DOI