Sesión Matemática DiscretaContando la cantidad de PEDs en algunas clases de grafos
Camilo Vera
Instituto de Cálculo, FCEN, UBA, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dado un grafo $G = (V, E)$ y dos aristas $e, f\in E$, decimos que $e$ domina a $f$ si ambas comparten un extremo o bien si $e = f$. Un subconjunto $P$ de $E$ es un conjunto perfecto de aristas dominantes (PED por sus siglas en inglés) si toda arista de $E\setminus P$ es dominada por exactamente una arista de $P$. Notar que todo grafo posee un PED, ya que el conjunto de aristas $E$ es un PED.
En este trabajo daremos a conocer una serie de resultados en torno a la cantidad de PEDs para ciertas clases de grafos. En primer lugar, obtuvimos una fórmula por recurrencia para calcular el número de PEDs del camino $P_n$, sabiendo que $P_1, P_2$ y $P_3$ tienen 1, 1 y 3 PEDs, respectivamente. De igual manera, probamos que los ciclos $C_n$, $n\geq 3$, cumplen la misma recurrencia que los caminos, donde $C_3, C_4$ y $C_5$ tienen 4, 5 y 6 PEDs, respectivamente. En segundo lugar, probamos que si $T$ es un árbol con $n$ vértices, entonces la cantidad de PEDs de $T$ es menor o igual que la cantidad de PEDs de $P_n$. En tercer lugar, y con ayuda del resultado anterior, probamos que un bosque con $n\geq 13$ vértices tiene una cantidad de PEDs menor o igual que la cantidad de PEDs de $P_n$.
Por otro lado, hallamos un algoritmo lineal para calcular el número de PEDs de un grafo serie-paralelo generalizado y de un grafo cordal, usando las ideas presentadas en [1]. También calculamos la máxima cantidad de PEDs de un grafo cordal con $n$ vértices y damos una familia de grafos de esta clase que alcanza dicho máximo.
Referencias
[1] C. L. Lu, M. T. Ko, C. Y. Tang, Perfect edge domination and efficient edge domination in graphs, Discrete Applied Mathematics 119 (2002)