Rango mínimo de un gráfico

En matemáticas, el rango mínimo es un parámetro de gráfico para un grafo G. Fue motivado por el invariante de grafo de Colin de Verdière . ${\displaystyle \operatorname {mr} (G)}$

Definición

La matriz de adyacencia de un grafo no dirigido es una matriz simétrica cuyas filas y columnas corresponden a los vértices del grafo. Sus elementos son todos 0 o 1, y el elemento en la fila i y la columna j es distinto de cero siempre que el vértice i sea adyacente al vértice j en el grafo. De manera más general, una matriz de adyacencia generalizada es cualquier matriz simétrica de números reales con el mismo patrón de números distintos de cero fuera de la diagonal (los elementos de la diagonal pueden ser cualquier número real). El rango mínimo de se define como el rango más pequeño de cualquier matriz de adyacencia generalizada del grafo; se denota por . ${\displaystyle G}$ ${\displaystyle \operatorname {mr} (G)}$

Propiedades

Aquí hay algunas propiedades elementales.

• El rango mínimo de un gráfico es siempre como máximo igual a n  − 1, donde n es el número de vértices del gráfico. ^[1]
• Para cada subgrafo inducido H de un grafo dado G , el rango mínimo de H es como máximo igual al rango mínimo de G . ^[2]
• Si un gráfico está desconectado , entonces su rango mínimo es la suma de los rangos mínimos de sus componentes conexos . ^[3]
• El rango mínimo es invariante del grafo : los grafos isomorfos necesariamente tienen el mismo rango mínimo.

Caracterización de familias de grafos conocidas

Varias familias de gráficos pueden caracterizarse en términos de sus rangos mínimos.

• Para , el grafo completo K _n en n vértices tiene rango mínimo uno. Los únicos grafos que están conexos y tienen rango mínimo uno son los grafos completos. ^[4] ${\displaystyle n\geq 2}$
• Un grafo de trayectoria P _n en n vértices tiene un rango mínimo n  − 1. Los únicos grafos de n vértices con rango mínimo n  − 1 son los grafos de trayectoria. ^[5]
• Un gráfico cíclico C _n en n vértices tiene un rango mínimo n  − 2. ^[6]
• Sea un grafo 2-conexo . Entonces, si y solo si es un árbol lineal de 2 elementos. ^[7] ${\displaystyle G}$ ${\displaystyle \operatorname {mr} (G)=|G|-2}$ ${\displaystyle G}$
• Un gráfico tiene si y sólo si el complemento de es de la forma para números enteros no negativos apropiados con para todo . ^[8] ${\displaystyle G}$ ${\displaystyle \operatorname {mr} (G)\leq 2}$ ${\displaystyle G}$ ${\displaystyle (K_{s_{1}}\cup K_{s_{2}}\cup K_{p_{1},q_{1}}\cup \cdots \cup K_{p_{k},q_{k}})\vee K_{r}}$ ${\displaystyle k,s_{1},s_{2},p_{1},q_{1},\ldots ,p_{k},q_{k},r}$ ${\displaystyle p_{i}+q_{i}>0}$ ${\displaystyle i=1,\ldots ,k}$

Notas

1. Fallat–Hogben, Observación 1.2.
2. Fallat–Hogben, Observación 1.6.
3. Fallat–Hogben, Observación 1.6.
4. Fallat–Hogben, Observación 1.2.
5. Fallat-Hogben, Corolario 1.5.
6. Fallat–Hogben, Observación 1.6.
7. Fallat-Hogben, Teorema 2.10.
8. Fallat-Hogben, Teorema 2.9.

Referencias

• Fallat, Shaun; Hogben, Leslie , "El rango mínimo de matrices simétricas descritas por un gráfico: un estudio", Álgebra lineal y sus aplicaciones 426 (2007) (PDF) , págs. 558–582.