Том 25, номер 1, 2018 г., Стр. 25–41

УДК 519.1+519.173
Евдокимов А. А., Федоряева Т. И.
Графы древовидной структуры с полным разнообразием шаров

Аннотация:
Изучается разнообразие метрических шаров в конечных связных обыкновенных графах, рассматриваемых как метрическое пространство с обычной метрикой пути. Исследовано строение графов, в которых различны все шары фиксированного радиуса $i$ для любого $i$, меньшего диаметра графа. Такие графы мы называем графами полного разнообразия шаров. Для них установлены свойства, связанные с наличием в них узких мест, и выяснена конфигурация блоков в графе. На основе полученных свойств описаны графы древовидной структуры с полным разнообразием шаров.
Ил. 8, библиогр. 22.

Ключевые слова: граф, граф древовидной структуры, метрический шар, радиус шара, число шаров, вектор разнообразия шаров, полное разнообразие шаров.

DOI: 10.17377/daio.2018.25.583

Евдокимов Александр Андреевич ^1,2
Федоряева Татьяна Ивановна ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: evdok@math.nsc.ru, fti@math.nsc.ru

Статья поступила 27 июня 2017 г.
Исправленный вариант — 8 августа 2017 г.

Литература

[1] Евдокимов А. А. Локально изометрические вложения графов и свойство продолжения метрики // Сиб. журн. исслед. операций. 1994. Т. 1, № 1. С. 5–12.

[2] Евдокимов А. А., Куценогая Е. П., Федоряева Т. И. О графах полного разнообразия шаров // Прикл. дискрет. математика. Прил. 2016. № 9. С. 110–112.

[3] Евдокимов А. А., Федоряева Т. И. О проблеме характеризации векторов разнообразия шаров // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 1. C. 44–52.

[4] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М: Наука, 1990. 384 с.

[5] Рычков К. Л. О достаточных условиях существования графа с заданным разнообразием шаров // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13, № 1. C. 99–108.

[6] Федоряева Т. И. Операции и изометрические вложения графов, связанные со свойством продолжения метрики // Дискрет. анализ и исслед. операций. 1995. Т. 2, № 3. C. 49–67.

[7] Федоряева Т. И. Разнообразие шаров в метрических пространствах деревьев // Дискрет. анализ и исслед. операций. Сер. 1. 2005. Т. 12, № 3. С. 74–84.

[8] Федоряева Т. И. Векторы разнообразия шаров для графов и оценки их компонент // Дискрет. анализ и исслед. операций. Сер. 1. 2007. Т. 14, № 2. C. 47–67.

[9] Федоряева Т. И. Точные верхние оценки числа различных шаров заданного радиуса в графах с фиксированными числом вершин и диаметром // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 6. C. 74–92.

[10] Федоряева Т. И. О графах с заданными диаметром, числом вершин и локальным разнообразием шаров // Дискрет. анализ и исслед. операций. 2010. Т. 17, № 1. C. 65–74.

[11] Федоряева Т. И. Мажоранты и миноранты класса графов с фиксированными диаметром и числом вершин // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 1. C. 58–76.

[12] Федоряева Т. И. Строение вектора разнообразия шаров типичного графа заданного диаметра // Сиб. электрон. мат. изв. 2016. Т. 13. C. 375–387.

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

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

[15] Harary F. Graph theory. Reading, MA: Addison-Wesley, 1969. 273 p.

[16] Harary F., Palmer E. Graphical enumeration. New York: Acad. Press, 1973. 263 p.

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

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

[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). Heidelberg: Springer, 2010. P. 410–425. (Lect. Notes Bioinform.; Vol. 6044).

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

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

[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). Los Alamitos: IEEE Comput. Soc., 2005. P. 536–541.