Аннотация:
Данная статья исследует экстремальные свойства и оценки двух значимых топологических индексов в теории графов: индексов Альбертсона и Сигма, с акцентом на деревья и двудольные графы. Мы идентифицируем уникальные деревья, которые максимизируют и минимизируют индекс Альбертсона, включая звёзды и пути, и расширяем эту характеристику на двудольные графы. В этой работе мы изучаем точные верхние и нижние оценки топологических индексов для заданной последовательности степеней $\mathscr{D}=(d_1,d_2,\ldots,d_n)$. Мы выводим точные нижние и верхние оценки для индексов Альбертсона и Сигма на основе неубывающей последовательности степеней $\mathscr{D}=(d_1,d_2,\ldots,d_n)$. Установление таких оценок является фундаментальной задачей в изучении топологических индексов, поскольку эти результаты выявляют внутренние взаимосвязи различных индексов. Для генерации двудольных графов и турниров с заданными последовательностями степеней проводится анализ времени смешивания и свойств сходимости. Точные верхние и нижние оценки индекса Сигма на основе последовательностей степеней обеспечивают более глубокое понимание его поведения в деревьях. Наши результаты предлагают новые взгляды на меры структурной нерегулярности графов, подкреплённые строгими доказательствами и вычислительными алгоритмами для оценки этих индексов в случайных деревьях и лесах. Эти результаты способствуют пониманию экстремальных свойств и комбинаторных структур в теории графов с приложениями в химической теории графов и анализе сетей.
Полный текст:
PDF файл (1457 kB)