2 votos

una condición necesaria para que un gráfico no vacío sea un gráfico de líneas

Todos los grafos que aparecen a continuación se refieren a un grafo simple finito.

Existe una condición necesaria y suficiente para que un gragh no vacío sea un gragh de línea:

Teorema de Krausz

Un gragh no vacío es un gragh de línea si y sólo si su conjunto de aristas puede dividirse en un conjunto de cliques con la propiedad de que cualquier vértice se encuentra como máximo en dos cliques.

Y podemos encontrar una condición necesaria obvia para que un gragh no vacío sea un gragh de línea:

Si un gragh no vacío GG es un gráfico lineal, entonces para cualquier vértice vv de GG los vecinos de vv puede dividirse en a lo sumo dos conjuntos de vértices tales que el subgrafo de GG inducido por cada conjunto de vértices es una camarilla.

Quiero preguntar si esta condición necesaria es suficiente para GG siendo una línea gragh. Si no es así, por favor da un contraejemplo.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X