En la teoría de grafos , un conjunto dominante conectado y un árbol de expansión de hoja máxima son dos estructuras estrechamente relacionadas definidas en un gráfico no dirigido .
Un conjunto dominante conexo mínimo de un grafo G es un conjunto dominante conexo con la cardinalidad más pequeña posible entre todos los conjuntos dominantes conexos de G . El número de dominación conexo de G es el número de vértices en el conjunto dominante mínimo conexo. [1]
Cualquier árbol de expansión T de un grafo G tiene al menos dos hojas, vértices que tienen solo una arista de T incidente con ellos. Un árbol de expansión de hojas máximas es un árbol de expansión que tiene el mayor número posible de hojas entre todos los árboles de expansión de G . El número máximo de hojas de G es el número de hojas en el árbol de expansión máximo de hojas. [2]
Si d es el número de dominación conectado de un gráfico G de n vértices , donde n > 2 , y l es su número máximo de hojas, entonces las tres cantidades d , l y n obedecen a la ecuación simple
Si D es un conjunto dominante conexo, entonces existe un árbol de expansión en G cuyas hojas incluyen todos los vértices que no están en D : forman un árbol de expansión del subgrafo inducido por D , junto con las aristas que conectan cada vértice restante v que no está en D a un vecino de v en D . Esto muestra que l ≥ norte - re .
En la otra dirección, si T es cualquier árbol de expansión en G , entonces los vértices de T que no son hojas forman un conjunto dominante conectado de G. Esto muestra que norte - l ≥ re . Poniendo estas dos desigualdades juntas prueba la igualdad n = d + l .