EN|RU

7 декабря 2017 г., 17 стр.

УДК 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.

 © Институт математики им. С. Л. Соболева, 2015