Volume 25, No 1, 2018, P. 25-41

UDC 519.1+519.173
A. A. Evdokimov and T. I. Fedoryaeva
Tree-like structure graphs with full diversity of balls

Abstract:
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

Keywords: graph, tree-like structure graphs, metric ball, radius of a ball, number of balls, diversity vector of balls, full diversity of balls.

DOI: 10.17377/daio.2018.25.583

Alexander A. Evdokimov ^1,2
Tatiana I. Fedoryaeva ^1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: evdok@math.nsc.ru, fti@math.nsc.ru

Received 27 June 2017
Revised 8 August 2017

References

[1] A. A. Evdokimov, Locally isometric embeddings of graphs and the metric prolongation property, Sib. Zh. Issled. Oper., 1, No. 1, 5–12, 1994 [Russian]. Translated in Discrete Analysis and Operations Research, pp. 7–14, Kluwer Acad. Publ., Dordrecht, 1996 (Math. Its Appl., Vol. 355).

[2] A. A. Evdokimov, E. P. Kutsenogaya, and T. I. Fedoryaeva, On the full diversity of balls for graphs, Prikl. Discretn. Mat., Prilozh., No. 9, 110–112, 2016 [Russian].

[3] A. A. Evdokimov and T. I. Fedoryaeva, On the problem of characterizing the diversity vectors of balls, Diskretn. Anal. Issled. Oper., 21, No. 1, 44–52, 2014 [Russian]. Translated in J. Appl. Ind. Math., 8, No. 2, 190–195, 2014.

[4] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lektsii po teorii grafov, Nauka, Moscow, 1990 [Russian]. Translated un?der the title Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994.

[5] K. L. Rychkov, Sufficient conditions for the existence of a graph with a given variety of balls, Diskretn. Anal. Issled. Oper., Ser. 1, 13, No. 1, 99–108, 2006 [Russian]. Translated in J. Appl. Ind. Math., 1, No. 3, 380–385, 2007.

[6] T. I. Fedoryaeva, Operations and isometric embeddings of graphs related to the metric prolongation property, Diskretn. Anal. Issled. Oper., 2, No. 3, 49–67, 1995 [Russian]. Translated in Operations Research and Discrete Analysis, pp. 31–49, Kluwer Acad. Publ., Dordrecht, 1997 (Math. Its Appl., Vol. 391).

[7] T. I. Fedoryaeva, Variety of balls in the metric spaces of trees, Diskretn. Anal. Issled. Oper., Ser. 1, 12, No. 3, 74–84, 2005 [Russian].

[8] T. I. Fedoryaeva, Diversity vectors of balls in graphs and estimates of the components of the vectors, Diskretn. Anal. Issled. Oper., 14, No. 2, 47–67, 2007 [Russian]. Translated in J. Appl. Ind. Math., 2, No. 3, 341–356, 2008.

[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, No. 6, 74–92, 2009 [Russian].

[10] T. I. Fedoryaeva, On the graphs with given diameter, number of vertices, and local diversity of balls, Diskretn. Anal. Issled. Oper., 17, No. 1, 65–74, 2010 [Russian]. Translated in J. Appl. Ind. Math., 5, No. 1, 44–50, 2011.

[11] T. I. Fedoryaeva, Majorants and minorants for the classes of graphs with fixed diameter and number of vertices, Diskretn. Anal. Issled. Oper., 20, No. 1, 58–76, 2013 [Russian]. Translated in J. Appl. Ind. Math., 7, No. 2, 153–165, 2013.

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

[13] J. Guo and L. Volkmann, A generalization of Menger’s theorem for certain block-cactus graphs, Graphs Comb., 11, No. 1, 49–52, 1995.

[14] F. Harary, A characterization of block-graphs, Can. Math. Bull., 6, No. 1, 1–6, 1963.

[15] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.

[16] F. Harary and E. M. Palmer, Graphical Enumeration, Acad. Press, New York, 1973.

[17] F. Harary and G. E. Uhlenbeck, On the number of Husimi trees, Proc. Nat. Acad. Sci. USA, 39, No. 4, 315–322, 1953.

[18] J. K. Lan and G. J. Chang, Algorithmic aspects of the $k$-domination problem in graphs, Discrete Appl. Math., 161, No. 10–11, 1513–1520, 2013.

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

[20] B. Randerath and L. Volkmann, A characterization of well covered block-cactus graphs, Australas. J. Comb., 9, 307–314, 1994.

[21] J. Topp and L. Volkmann, Well covered and well dominated block graphs and unicyclic graphs, Math. Pannonica, 1, No. 2, 55–66, 1990.

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