Introducci´ on

Nuevas caracterizaciones

Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones Pablo De Caria, Marisa Gutierrez

Mar del Plata, septiembre de 2009

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Definiciones r´ apidas Un uv -separador de G es un conjunto S ⊆ V (G ) tal que G − S es no conexo y u y v quedan en componentes conexas distintas. Es minimal si ning´ un conjunto menor tiene la misma propiedad. Un clique es un conjunto maximal de v´ertices adyacentes de a pares. C (G ) simboliza la familia de cliques de G . Una familia de conjuntos es Helly si la intersecci´ on de todos los elementos de toda subfamilia de conjuntos no disjuntos de a pares es no vac´ıa. G es un grafo Helly cuando C (G ) es Helly. T ´arbol y u, v ∈ V (T ), T [u, v ] indicar´a el camino en T de u a v . T (u, v ) indicar´a a los v´ertices interiores.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Definiciones r´ apidas Un uv -separador de G es un conjunto S ⊆ V (G ) tal que G − S es no conexo y u y v quedan en componentes conexas distintas. Es minimal si ning´ un conjunto menor tiene la misma propiedad. Un clique es un conjunto maximal de v´ertices adyacentes de a pares. C (G ) simboliza la familia de cliques de G . Una familia de conjuntos es Helly si la intersecci´ on de todos los elementos de toda subfamilia de conjuntos no disjuntos de a pares es no vac´ıa. G es un grafo Helly cuando C (G ) es Helly. T ´arbol y u, v ∈ V (T ), T [u, v ] indicar´a el camino en T de u a v . T (u, v ) indicar´a a los v´ertices interiores.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Definiciones r´ apidas Un uv -separador de G es un conjunto S ⊆ V (G ) tal que G − S es no conexo y u y v quedan en componentes conexas distintas. Es minimal si ning´ un conjunto menor tiene la misma propiedad. Un clique es un conjunto maximal de v´ertices adyacentes de a pares. C (G ) simboliza la familia de cliques de G . Una familia de conjuntos es Helly si la intersecci´ on de todos los elementos de toda subfamilia de conjuntos no disjuntos de a pares es no vac´ıa. G es un grafo Helly cuando C (G ) es Helly. T ´arbol y u, v ∈ V (T ), T [u, v ] indicar´a el camino en T de u a v . T (u, v ) indicar´a a los v´ertices interiores.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Definiciones r´ apidas Un uv -separador de G es un conjunto S ⊆ V (G ) tal que G − S es no conexo y u y v quedan en componentes conexas distintas. Es minimal si ning´ un conjunto menor tiene la misma propiedad. Un clique es un conjunto maximal de v´ertices adyacentes de a pares. C (G ) simboliza la familia de cliques de G . Una familia de conjuntos es Helly si la intersecci´ on de todos los elementos de toda subfamilia de conjuntos no disjuntos de a pares es no vac´ıa. G es un grafo Helly cuando C (G ) es Helly. T ´arbol y u, v ∈ V (T ), T [u, v ] indicar´a el camino en T de u a v . T (u, v ) indicar´a a los v´ertices interiores.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Definiciones r´ apidas Un uv -separador de G es un conjunto S ⊆ V (G ) tal que G − S es no conexo y u y v quedan en componentes conexas distintas. Es minimal si ning´ un conjunto menor tiene la misma propiedad. Un clique es un conjunto maximal de v´ertices adyacentes de a pares. C (G ) simboliza la familia de cliques de G . Una familia de conjuntos es Helly si la intersecci´ on de todos los elementos de toda subfamilia de conjuntos no disjuntos de a pares es no vac´ıa. G es un grafo Helly cuando C (G ) es Helly. T ´arbol y u, v ∈ V (T ), T [u, v ] indicar´a el camino en T de u a v . T (u, v ) indicar´a a los v´ertices interiores.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Una cuerda de un ciclo es una arista entre v´ertices no consecutivos del ciclo. Un grafo es cordal si no posee ciclos de al menos cuatro v´ertices sin cuerdas. El grafo de intersecci´ on de una familia F de conjuntos, L(F ), tiene a los conjuntos como v´ertices y como aristas a todo par de conjuntos no disjuntos.

L(C (G )) recibe el nombre de grafo clique de G o K (G ). Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Una cuerda de un ciclo es una arista entre v´ertices no consecutivos del ciclo. Un grafo es cordal si no posee ciclos de al menos cuatro v´ertices sin cuerdas. El grafo de intersecci´ on de una familia F de conjuntos, L(F ), tiene a los conjuntos como v´ertices y como aristas a todo par de conjuntos no disjuntos.

L(C (G )) recibe el nombre de grafo clique de G o K (G ). Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Una cuerda de un ciclo es una arista entre v´ertices no consecutivos del ciclo. Un grafo es cordal si no posee ciclos de al menos cuatro v´ertices sin cuerdas. El grafo de intersecci´ on de una familia F de conjuntos, L(F ), tiene a los conjuntos como v´ertices y como aristas a todo par de conjuntos no disjuntos.

L(C (G )) recibe el nombre de grafo clique de G o K (G ). Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Una cuerda de un ciclo es una arista entre v´ertices no consecutivos del ciclo. Un grafo es cordal si no posee ciclos de al menos cuatro v´ertices sin cuerdas. El grafo de intersecci´ on de una familia F de conjuntos, L(F ), tiene a los conjuntos como v´ertices y como aristas a todo par de conjuntos no disjuntos.

L(C (G )) recibe el nombre de grafo clique de G o K (G ). Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Una cuerda de un ciclo es una arista entre v´ertices no consecutivos del ciclo. Un grafo es cordal si no posee ciclos de al menos cuatro v´ertices sin cuerdas. El grafo de intersecci´ on de una familia F de conjuntos, L(F ), tiene a los conjuntos como v´ertices y como aristas a todo par de conjuntos no disjuntos.

L(C (G )) recibe el nombre de grafo clique de G o K (G ). Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Grafos dualmente cordales Definiciones Dado G grafo, w es m´ aximo vecino de v si N 2 [v ] ⊆ N[w ].

v1 v2 ...vn es un orden de m´ aximas vecindades de G si vi tiene un m´aximo vecino en G [{vi , ..., vn }].

Se llama dualmente cordal a todo grafo que posee un orden de m´aximas vecindades.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Grafos dualmente cordales Definiciones Dado G grafo, w es m´ aximo vecino de v si N 2 [v ] ⊆ N[w ].

v1 v2 ...vn es un orden de m´ aximas vecindades de G si vi tiene un m´aximo vecino en G [{vi , ..., vn }].

Se llama dualmente cordal a todo grafo que posee un orden de m´aximas vecindades.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Grafos dualmente cordales Definiciones Dado G grafo, w es m´ aximo vecino de v si N 2 [v ] ⊆ N[w ].

v1 v2 ...vn es un orden de m´ aximas vecindades de G si vi tiene un m´aximo vecino en G [{vi , ..., vn }].

Se llama dualmente cordal a todo grafo que posee un orden de m´aximas vecindades.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Ejemplo

v1 v7 v2 v3 v6 v5 v4 es un orden de m´aximas vecindades.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Ejemplo

v1 v7 v2 v3 v6 v5 v4 es un orden de m´aximas vecindades.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Otras caracterizaciones Existe T ´arbol generador tal que todo clique induce un sub´arbol. I Existe T ´arbol generador tal que, ∀v ∈ V (G ), N[v ] induce un sub´arbol. I

Cualquier T con estas caracter´ısticas se llama ´ arbol compatible.

Propiedad: T es compatible con G sii ∀x, y , z, xy ∈ E (G ) y z ∈ T (x, y ) implica que xz, yz ∈ E (G ). Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Otras caracterizaciones Existe T ´arbol generador tal que todo clique induce un sub´arbol. I Existe T ´arbol generador tal que, ∀v ∈ V (G ), N[v ] induce un sub´arbol. I

Cualquier T con estas caracter´ısticas se llama ´ arbol compatible.

Propiedad: T es compatible con G sii ∀x, y , z, xy ∈ E (G ) y z ∈ T (x, y ) implica que xz, yz ∈ E (G ). Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Otras caracterizaciones Existe T ´arbol generador tal que todo clique induce un sub´arbol. I Existe T ´arbol generador tal que, ∀v ∈ V (G ), N[v ] induce un sub´arbol. I

Cualquier T con estas caracter´ısticas se llama ´ arbol compatible.

Propiedad: T es compatible con G sii ∀x, y , z, xy ∈ E (G ) y z ∈ T (x, y ) implica que xz, yz ∈ E (G ). Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Otras caracterizaciones Existe T ´arbol generador tal que todo clique induce un sub´arbol. I Existe T ´arbol generador tal que, ∀v ∈ V (G ), N[v ] induce un sub´arbol. I

Cualquier T con estas caracter´ısticas se llama ´ arbol compatible.

Propiedad: T es compatible con G sii ∀x, y , z, xy ∈ E (G ) y z ∈ T (x, y ) implica que xz, yz ∈ E (G ). Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Otras caracterizaciones Existe T ´arbol generador tal que todo clique induce un sub´arbol. I Existe T ´arbol generador tal que, ∀v ∈ V (G ), N[v ] induce un sub´arbol. I

Cualquier T con estas caracter´ısticas se llama ´ arbol compatible.

Propiedad: T es compatible con G sii ∀x, y , z, xy ∈ E (G ) y z ∈ T (x, y ) implica que xz, yz ∈ E (G ). Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Otras caracterizaciones I

G es Helly y K (G ) es cordal.

I

G es el grafo clique de un grafo cordal.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Otras caracterizaciones I

G es Helly y K (G ) es cordal.

I

G es el grafo clique de un grafo cordal.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Otras caracterizaciones I

G es Helly y K (G ) es cordal.

I

G es el grafo clique de un grafo cordal.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Nuevas caracterizaciones Teorema G es dualmente cordal ⇐⇒ ∃ T generador tal que todo separador minimal induce un sub´arbol. Demostraci´ on =⇒) Se prueba que si T es un ´arbol compatible con G todo uv -separador minimal S induce un sub´arbol. Basta ver que ∀x, y , x, y ∈ S y T (x, y ) 6= ∅ implica T (x, y ) ∩ S 6= ∅.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Nuevas caracterizaciones Teorema G es dualmente cordal ⇐⇒ ∃ T generador tal que todo separador minimal induce un sub´arbol. Demostraci´ on =⇒) Se prueba que si T es un ´arbol compatible con G todo uv -separador minimal S induce un sub´arbol. Basta ver que ∀x, y , x, y ∈ S y T (x, y ) 6= ∅ implica T (x, y ) ∩ S 6= ∅.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Nuevas caracterizaciones Teorema G es dualmente cordal ⇐⇒ ∃ T generador tal que todo separador minimal induce un sub´arbol. Demostraci´ on =⇒) Se prueba que si T es un ´arbol compatible con G todo uv -separador minimal S induce un sub´arbol. Basta ver que ∀x, y , x, y ∈ S y T (x, y ) 6= ∅ implica T (x, y ) ∩ S 6= ∅.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Nuevas caracterizaciones Teorema G es dualmente cordal ⇐⇒ ∃ T generador tal que todo separador minimal induce un sub´arbol. Demostraci´ on =⇒) Se prueba que si T es un ´arbol compatible con G todo uv -separador minimal S induce un sub´arbol. Basta ver que ∀x, y , x, y ∈ S y T (x, y ) 6= ∅ implica T (x, y ) ∩ S 6= ∅.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Nuevas caracterizaciones Teorema G es dualmente cordal ⇐⇒ ∃ T generador tal que todo separador minimal induce un sub´arbol. Demostraci´ on =⇒) Se prueba que si T es un ´arbol compatible con G todo uv -separador minimal S induce un sub´arbol. Basta ver que ∀x, y , x, y ∈ S y T (x, y ) 6= ∅ implica T (x, y ) ∩ S 6= ∅.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

u = v1 v2 ...vn = v camino cuyo u ´nico v´ertice en S es x. vi v´ertice tal que u ∈ T [vi , v ] con mayor ´ındice. uvi+1 ...v camino sin v´ertices en S (absurdo).

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Nuevas caracterizaciones

Introducci´ on

u = v1 v2 ...vn = v camino cuyo u ´nico v´ertice en S es x. vi v´ertice tal que u ∈ T [vi , v ] con mayor ´ındice. uvi+1 ...v camino sin v´ertices en S (absurdo).

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Nuevas caracterizaciones

Introducci´ on

u = v1 v2 ...vn = v camino cuyo u ´nico v´ertice en S es x. vi v´ertice tal que u ∈ T [vi , v ] con mayor ´ındice. uvi+1 ...v camino sin v´ertices en S (absurdo).

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Nuevas caracterizaciones

Introducci´ on

u = v1 v2 ...vn = v camino cuyo u ´nico v´ertice en S es x. vi v´ertice tal que u ∈ T [vi , v ] con mayor ´ındice. uvi+1 ...v camino sin v´ertices en S (absurdo).

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Nuevas caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Si T (x, y ) ∩ S = ∅: I T (x, y ) est´a en la misma componente conexa que u.

I Por el mismo razonamiento est´a en la misma componente conexa que v (absurdo).

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Si T (x, y ) ∩ S = ∅: I T (x, y ) est´a en la misma componente conexa que u.

I Por el mismo razonamiento est´a en la misma componente conexa que v (absurdo).

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Si T (x, y ) ∩ S = ∅: I T (x, y ) est´a en la misma componente conexa que u.

I Por el mismo razonamiento est´a en la misma componente conexa que v (absurdo).

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Si T (x, y ) ∩ S = ∅: I T (x, y ) est´a en la misma componente conexa que u.

I Por el mismo razonamiento est´a en la misma componente conexa que v (absurdo).

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

⇐=) Sean T con las caracter´ısticas mencionadas, x e y adyacentes y z ∈ T (x, y ).

Si x no es adyacente a z, sea S xz-separador minimal. Se deduce que x e y est´an en la misma componente conexa de G − S (absurdo). Conclusi´ on x adyacente a z. Tambi´en y adyacente a z, T compatible y G dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

⇐=) Sean T con las caracter´ısticas mencionadas, x e y adyacentes y z ∈ T (x, y ).

Si x no es adyacente a z, sea S xz-separador minimal. Se deduce que x e y est´an en la misma componente conexa de G − S (absurdo). Conclusi´ on x adyacente a z. Tambi´en y adyacente a z, T compatible y G dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

⇐=) Sean T con las caracter´ısticas mencionadas, x e y adyacentes y z ∈ T (x, y ).

Si x no es adyacente a z, sea S xz-separador minimal. Se deduce que x e y est´an en la misma componente conexa de G − S (absurdo). Conclusi´ on x adyacente a z. Tambi´en y adyacente a z, T compatible y G dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

⇐=) Sean T con las caracter´ısticas mencionadas, x e y adyacentes y z ∈ T (x, y ).

Si x no es adyacente a z, sea S xz-separador minimal. Se deduce que x e y est´an en la misma componente conexa de G − S (absurdo). Conclusi´ on x adyacente a z. Tambi´en y adyacente a z, T compatible y G dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

⇐=) Sean T con las caracter´ısticas mencionadas, x e y adyacentes y z ∈ T (x, y ).

Si x no es adyacente a z, sea S xz-separador minimal. Se deduce que x e y est´an en la misma componente conexa de G − S (absurdo). Conclusi´ on x adyacente a z. Tambi´en y adyacente a z, T compatible y G dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

⇐=) Sean T con las caracter´ısticas mencionadas, x e y adyacentes y z ∈ T (x, y ).

Si x no es adyacente a z, sea S xz-separador minimal. Se deduce que x e y est´an en la misma componente conexa de G − S (absurdo). Conclusi´ on x adyacente a z. Tambi´en y adyacente a z, T compatible y G dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Teorema

G es dualmente cordal

m Todo separador minimal induce un subgrafo conexo, S(G ) es Helly y L(S(G )) es cordal. =⇒) Tomar T generador tal que todo separador minimal induzca un sub´arbol.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Teorema

G es dualmente cordal

m Todo separador minimal induce un subgrafo conexo, S(G ) es Helly y L(S(G )) es cordal. =⇒) Tomar T generador tal que todo separador minimal induzca un sub´arbol.

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

⇐=) Como S(G ) es Helly y L(S(G )) es cordal existe T tal que: I

V (T ) = V (G )

I

Todo elemento de S(G ) induce un sub´arbol de T .

Elegir ese T de modo que p(T ) :=

P

uv ∈E (T ) d(u, v )

es m´ınima.

Objetivo Probar que T es generador y por tanto compatible con G .

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

⇐=) Como S(G ) es Helly y L(S(G )) es cordal existe T tal que: I

V (T ) = V (G )

I

Todo elemento de S(G ) induce un sub´arbol de T .

Elegir ese T de modo que p(T ) :=

P

uv ∈E (T ) d(u, v )

es m´ınima.

Objetivo Probar que T es generador y por tanto compatible con G .

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

⇐=) Como S(G ) es Helly y L(S(G )) es cordal existe T tal que: I

V (T ) = V (G )

I

Todo elemento de S(G ) induce un sub´arbol de T .

Elegir ese T de modo que p(T ) :=

P

uv ∈E (T ) d(u, v )

es m´ınima.

Objetivo Probar que T es generador y por tanto compatible con G .

Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Suponer que uv ∈ E (T ) − E (G ) y que d(u, v ) = k, k > 1.

Suv : Separadores minimales que contienen a {u, v }. S1 : uv -separador minimal en N[u]. S2 : uv -separador minimal en {w : d(w , v ) = k − 1}. Dos conjuntos cualesquiera de F := Suv ∪ {S1 , S2 } son no disjuntos y S(G ) es Helly. Existe w en todos los elementos de F . Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Suponer que uv ∈ E (T ) − E (G ) y que d(u, v ) = k, k > 1.

Suv : Separadores minimales que contienen a {u, v }. S1 : uv -separador minimal en N[u]. S2 : uv -separador minimal en {w : d(w , v ) = k − 1}. Dos conjuntos cualesquiera de F := Suv ∪ {S1 , S2 } son no disjuntos y S(G ) es Helly. Existe w en todos los elementos de F . Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Suponer que uv ∈ E (T ) − E (G ) y que d(u, v ) = k, k > 1.

Suv : Separadores minimales que contienen a {u, v }. S1 : uv -separador minimal en N[u]. S2 : uv -separador minimal en {w : d(w , v ) = k − 1}. Dos conjuntos cualesquiera de F := Suv ∪ {S1 , S2 } son no disjuntos y S(G ) es Helly. Existe w en todos los elementos de F . Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Suponer que uv ∈ E (T ) − E (G ) y que d(u, v ) = k, k > 1.

Suv : Separadores minimales que contienen a {u, v }. S1 : uv -separador minimal en N[u]. S2 : uv -separador minimal en {w : d(w , v ) = k − 1}. Dos conjuntos cualesquiera de F := Suv ∪ {S1 , S2 } son no disjuntos y S(G ) es Helly. Existe w en todos los elementos de F . Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Se obtiene un nuevo ´arbol T 0 tal que todo elemento de S(G ) induce un sub´arbol.

p(T 0 ) < p(T ). Absurdo. Conclusi´ on T es compatible con G y G es dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Se obtiene un nuevo ´arbol T 0 tal que todo elemento de S(G ) induce un sub´arbol.

p(T 0 ) < p(T ). Absurdo. Conclusi´ on T es compatible con G y G es dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Se obtiene un nuevo ´arbol T 0 tal que todo elemento de S(G ) induce un sub´arbol.

p(T 0 ) < p(T ). Absurdo. Conclusi´ on T es compatible con G y G es dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Se obtiene un nuevo ´arbol T 0 tal que todo elemento de S(G ) induce un sub´arbol.

p(T 0 ) < p(T ). Absurdo. Conclusi´ on T es compatible con G y G es dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Se obtiene un nuevo ´arbol T 0 tal que todo elemento de S(G ) induce un sub´arbol.

p(T 0 ) < p(T ). Absurdo. Conclusi´ on T es compatible con G y G es dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

Se obtiene un nuevo ´arbol T 0 tal que todo elemento de S(G ) induce un sub´arbol.

p(T 0 ) < p(T ). Absurdo. Conclusi´ on T es compatible con G y G es dualmente cordal. Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones

Introducci´ on

Nuevas caracterizaciones

¡¡Gracias por venir!! Pablo De Caria, Marisa Gutierrez Separadores minimales de v´ ertices de grafos dualmente cordales y caracterizaciones