Preview

Доклады Национальной академии наук Беларуси

Расширенный поиск

ХАРАКТЕРИЗАЦИЯ 1-ТРЕУГОЛЬНЫХ ГРАФОВ

Аннотация

Граф называется 1-треугольным, если для любого максимального независимого множества I этого графа каждое ребро графа, не инцидентное ни одной вершине из I, образует единственный треугольник с вершиной из множества I. В работе получена структурная характеризация класса 1-треугольных графов, которая влечёт полиномиальный алгоритм их распознавания.

Просмотров: 831


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-8323 (Print)
ISSN 2524-2431 (Online)