Критический граф

Cтраница 1

Критический граф, не являющийся реберно-критическим. [1]

Критический граф G может обладать еще одним свойством: X ( G - X) x ( G) - 1 для любого ребра х графа G. В этом случае граф G называется реберно-критическим; если % ( G) n, то G называется п-реберно-критическим. Хотя каждый реберно-критический граф обязательно является критическим, обратное не верно. [2]

Каждый критический граф имеет соответствующие простые цепи L0 максимальной длины и простые циклы С0 максимальной длины. [3]

Каждый критический граф имеет соответствующие простые цепи LQ максимальной длины и простые циклы CQ максимальной длины. Следующий результат принадлежит Дж. [4]

Теорема 14.3.3. Критический граф не может быть разделен вершинами содержащегося в нем полного графа. [5]

Докажите, что всякий критический граф, являющийся fe-xpo - матическим, обладает следующими свойствами: ( i) он связен; ( ii) степень каждой его вершины не меньше k - 1; ( Hi) не существует вершины удаление которой приводит к несвязному графу. [6]

Ясно, что каждый критический граф G связен. Далее, поскольку X ( G) max x ( B), где максимум берется по всем блокам В графа G, то G должен быть блоком. Это одно из свойств, которыми обладают критические графы. [7]

Критический граф, не являющийся реберно-критическим. [8]

Каждый разрез по вершинам критического графа содержит две несмежные вершины. [9]

Если рассматриваются также и другие типы критических графов, то граф, критический в указанном смысле, будем называть критическим по раскраске. [10]

Критический граф, не являющийся реберно-критическим. [11]

В одном из направлений исследований свойства критических графов связывают с длинами циклов, в частности, окружения и обхвата. [12]

Следовательно, каждый fe - хромати-ческий граф содержит конечный критический граф с тем же хроматическим числом. [13]

Гомоморфные образы простой цепи Р4. [14]

Таким образом, реберно-критические графы обладают всеми свойствами критических графов, но в некоторых случаях о первых графах можно сказать больше, чем о вторых. [15]

Страницы: 1 2 3