About relationship between parameters of certain graphs.pdf В данной работе наиболее важным является понятие реберного покрытия графакликами (РПК). РПК - это такой набор клик (полных подграфов) K 1, ...,Kr, что любоеребро графа G лежит хотя бы в одной из этих клик. В качестве клик, входящихв РПК, подразумеваются только максимальные по включению клики. Кроме того,будем отождествлять клику и множество ее вершин, то есть выражение «множествовершин R образует клику в графе G» означает, что множество вершин R порождаетмаксимальный полный подграф в графе G. Назовем ребро e графа G собственнымребром клики K, если оно лежит в этой клике и не лежит ни в какой другой максимальнойпо включению клике графа G. Соответственно клику K, имеющую хотя быодно собственное ребро, назовем зафиксированной.Утверждение 1. Клика K входит в любое РПК графа G тогда и только тогда,когда она является зафиксированной.Собственные ребра и соответственно зафиксированные клики допускают простуюхарактеризацию, позволяющую легко распознать их в графе.Утверждение 2. Ребро e E E (G) является собственным ребром некоторой кликиK тогда и только тогда, когда множество вершин графа G, смежных одновременнос обоими концами ребра e, порождает полный подграф в G. Кроме того, этот полныйподграф в объединении с концами ребра e образует клику K .Из данного утверждения следует возможность нахождения всех зафиксированныхклик графа за полиномиальное время (трудоемкость не более O(n4), где и = |V(G)|).Отсюда следует, что в определенном смысле графами, в которых сложно строить минимальноеРПК, являются графы, не содержащие зафиксированных клик, или, что эквивалентно,собственных ребер. Далее такие графы, то есть графы, в которых каждоеребро лежит не менее чем в двух кликах, назовем графами, свободными от собственныхребер. Введем на множестве вершин графа G отношение эквивалентности. Двевершины x и у называются эквивалентными, если они смежны и их окружения совпадают,то есть N (x) = N (у). Сжатым графом назовем граф, в котором все вершиныпопарно неэквивалентны.Основное содержание работы отражает следующая теорема.Теорема 1. Предположим, что G является связным сжатым графом, свободнымот собственных ребер. Тогда1) p(G) ^ A(G) - 1;2) если p(G) = A(G) - 1, то A(G) = 4, и граф G эквивалентен графу B;3) если p(G) = A(G) - 2, то в графе G существует не менее двух вершин степениA(G), либо граф G получается из графа B добавлением одной доминирующейвершины.С помощью введения специальных операций над сжатыми графами, свободнымиот собственных ребер, сохраняющих данные свойства, и с использованием данной теоремыдоказывается следующее утверждение.Утверждение 3. Существуют непустые сжатые графы, свободные от зафиксированныхклик, имеющие p(G) = р и A(G) = A, где A и р - произвольные натуральныечисла, удовлетворяющие ограничениям: р ^ 3, A ^ р + 1.

Скачать электронную версию публикации