Cтраница 1
Минимальный факторно-критический граф не может содержать цикл с 4 вершинами. [1]
Построить 2-связный минимальный факторно-критический граф G, содержащий два ребра е и е, которые не лежат на эластичном цикле. [2]
Каждый эластичный факторно-критический подграф минимального факторно-критического графа тоже является минимальным факторно-критическим графом. [3]
В каждой колосковой декомпозиции минимального факторно-критического графа все ости собственные. [4]
Показать, что в минимальном факторно-критическом графе никакой эластичный цикл не имеет хорд. Привести пример минимального факторно-критического графа, в котором ( неэластичный) цикл имеет хорду. [5]
Каждый эластичный факторно-критический подграф минимального факторно-критического графа тоже является минимальным факторно-критическим графом. [6]
Далее, очевидно, что любой граф, у которого каждый блок есть Кз, является минимальным факторно-критическим графом. Напомним, что факторно-критический граф не может содержать разрезающих ребер. Все эти графы имеют ( Зр - 3) / 2 ребер, где р - число вершин, а следующий результат гласит, что это самые плотные минимальные факторно-критические графы. [7]
Показать, что в минимальном факторно-критическом графе никакой эластичный цикл не имеет хорд. Привести пример минимального факторно-критического графа, в котором ( неэластичный) цикл имеет хорду. [8]
Мы уже видели, что для факторно-критических графов существует теория колосковой декомпозиции, абсолютно аналогичная соответствующей теории для элементарных двудольных графов. Эту технику можно весьма успешно применить для изучения минимальных факторно-критических графов, и полученные результаты совершенно аналогичны результатам, относящимся к минимальным элементарным двудольным графам. [9]
Напомним, что в отличие от бикритических графов, факторно-критические графы могут иметь точки сочленения. То же самое верно и для минимальных факторно-критических графов. [10]