Cтраница 4
Петерсен показал также, что этот результат нельзя усилить, приведя кубический граф без мостов, который не является суммой трех 1-факторов. [46]
Равенство k 5 выполняется, поскольку ребро содержит 2 вершины и содержится в трех 1-факторах, так как 1-факторизация содержит пять 1-факторов. [47]
При k 4 2-связный граф G, имеющий 1-фактор, представляет собой цикл длины 4 и все его вершины тотально покрыты его 1-факторами. [48]
Обозначим через / ( п) наибольшее из чисел &, для которых справедливо следующее утверждение: если n - связный граф G имеет 1-фактор, то он имеет по крайней мере k ( различных) 1-факторов. [49]
Для каждого нечетного п, п З, и для п 4 существует только один п-связный граф Gn, имеющий f ( n) 1-факторов. [50]
Объединяя эти два множества 1-факторов, получаем для графа G по крайней мере f ( n - 1) / ( д - 2) 1-факторов. [51]
Каждый r - регулярный граф ( где г 0) с четным числом вершин, у которого K ( G) г - 1, имеет 1-фактор. [52]
Если F содержит ребро ( У, V), то граф G - G2, полученный в результате удаления компоненты G2 из G, будет 2-связным и будет иметь 1-фактор. [53]
В работах [10] и [15] указана такая 1 / - функция V ( О), что для кубических графов с 2п вершинами ( - 1) V ( О) есть число 1-факторов. [54]
Граф G G - Vi, V2 ( n - 2) - связен и имеет 1-фактор F - Е, так что он имеет по крайней мере f ( n - 2) 1-факторов. Добавляя ребро Е к 1-фактору графа G, получаем 1-фактор графа G. [55]