пороговый граф

В теории графов пороговый граф — это граф, который может быть построен из одновершинного графа последовательным выполнением следующих двух операций: 1. * Добавление в граф одной изолированной вершины 2. * Добавление одной доминирующей вершины в граф, т.е. отдельной вершины, связанной со всеми остальными вершинами. Например, граф на рисунке является пороговым графом. Он может быть построен с одной вершины (вершина 1), и добавления чёрных вершин как изолированных вершин и красных вершин как доминирующих вершин в порядке нумерации. Пороговые графы были введены Хваталом и Хаммером. Глава, посвящённая графам, появилась в книге Голумбика, а книга Махадева и Пеледа полностью посвящена пороговым графам.