Минимальный ранг графа

В математике минимальный ранг — это графа . параметр $\operatorname {mr} (G)$ для графа G. ​Это было мотивировано графическим инвариантом Колена де Вердьера .

Определение

Матрица смежности неориентированного графа — это симметричная матрица , строки и столбцы которой соответствуют вершинам графа. Все его элементы равны 0 или 1, а элемент в строке i и столбце j не равен нулю, если вершина i смежна с вершиной j в графе. В более общем смысле, обобщенная матрица смежности — это любая симметричная матрица действительных чисел с одинаковым набором ненулевых значений на диагонали (диагональными элементами могут быть любые действительные числа). Минимальный ранг $G$ определяется как наименьший ранг любой обобщенной матрицы смежности графа; это обозначается $\operatorname {mr} (G)$.

Характеристики

Вот некоторые элементарные свойства.

• Минимальный ранг графа всегда не более чем n − 1, где n — количество вершин в графе.
• Для каждого индуцированного подграфа H данного графа G минимальный ранг H не более чем равен минимальному G. рангу
• Если граф несвязен , то его минимальный ранг равен сумме минимальных рангов его связных компонентов .
• Минимальный ранг является инвариантом графа : изоморфные графы обязательно имеют одинаковый минимальный ранг.

Характеристика известных семейств графов

Некоторые семейства графов можно охарактеризовать с точки зрения их минимальных рангов.

• Для $n\geq 2$, полный граф K _n на n вершинах имеет минимальный ранг один. Единственными связными графами, имеющими минимальный ранг один, являются полные графы.
• Граф путей P _n на n вершинах имеет минимальный ранг n - 1. Единственные графы с n -вершинами с минимальным рангом n - 1 являются графами путей.
• Граф циклов C _n на n вершинах имеет минимальный ранг n − 2.
• Позволять $G$ быть 2-связным графом. Затем $\operatorname {mr} (G)=|G|-2$ тогда и только тогда, когда $G$ является линейным 2-деревом.
• График $G$ имеет $\operatorname {mr} (G)\leq 2$ тогда и только тогда, когда дополнение $G$ имеет форму $(K_{s_{1}}\cup K_{s_{2}}\cup K_{p_{1},q_{1}}\cup \cdots \cup K_{p_{k},q_{k}})\vee K_{r}$ для соответствующих неотрицательных целых чисел $k,s_{1},s_{2},p_{1},q_{1},\ldots ,p_{k},q_{k},r$ с $p_{i}+q_{i}>0$ для всех $i=1,\ldots ,k$.

Ссылки

• Фаллат, Шон; Хогбен, Лесли , «Минимальный ранг симметричных матриц, описываемых графом: обзор», Линейная алгебра и ее приложения 426 (2007) (PDF) , стр. 558–582 .