Sesión Matemática Discreta

Diciembre 13, 12:00 ~ 12:20

Sobre grafos Gallai y antiGallai cordales

Fernández Slezak, Florencia

\newtheorem{defi}{Definición} \newtheorem{thm}{Teorema} \providecommand{\Ga}[1][G]{\ensuremath{\text{Gal}({#1})}} \providecommand{\aG}[1][G]{\ensuremath{\Delta (#1)}} Consideramos grafos finitos, simples y no dirigidos, y usaremos la terminología estándar y notación de \cite{West}. \begin{defi} Para un grafo $G$, \begin{itemize} \item el \emph{grafo Gallai} \Ga~de $G$ tiene como vértices a las aristas de $G$, es decir, $V(\Ga) = E(G)$, y dos vértices distintos $e$ y $f$ de \Ga~son adyacentes en \Ga~si las aristas $e$ y $f$ de $G$ son adyacentes en $G$ pero no forman parte de un triángulo en $G$. \item el \emph{grafo anti-Gallai} \aG~de $G$ es el complemento de \Ga~en $L(G)$, es decir, el conjunto de vértices es $E(G)$ y el conjunto de aristas es $E(L(G)) \setminus E(\Ga)$. \end{itemize} \end{defi} En 2015, Joos, Le y Rautenbach caracterizaron a aquellos grafos en los que su grafo Gallai es una foresta a través de la siguiente equivalencia: \begin{thm}[\cite{Joos}]\label{Joos} El grafo Gallai \Ga de un grafo $G$ es una foresta si y sólo si $G$ es un grafo cordal sin $\{F_1,F_2,...,F_9\}$ como subgrafos inducidos (estos subgrafos se encuentran detallados en el trabajo citado). \end{thm} En el presente trabajo continuamos el estudio de los grafos Gallai y antiGallai, y caracterizamos las siguientes clases de grafos, $$ t \mathscr{F} = \{ G~ \text{grafo}: \aG \text{ es cordal}\} , $$ $$ t \mathscr{F'} = \{ G~ \text{grafo}: \Ga \text{ es cordal} \}. $$ %$$ %\mathscr{F''} = \{ H~ \text{grafo cordal}: \exists G \text{ donde } \Ga = H \}, %$$ En $\mathscr{F'}$ se amplía la lista del Teorema \ref{Joos} en 2 grafos más como subgrafos prohibidos, constituyendo aún una familia finita de subgrafos prohibidos. Además, probamos que $\mathscr{F} = 2-\text{tree} \cup \{\text{vértices aislados}\}$. Como trabajo futuro, nos proponemos caracterizar las familias de los grafos Gallai hereditarios, los antiGallai hereditarios y los grafos cuyo Gallai es un árbol. \begin{thebibliography}{9} \bibitem{Joos} Joos, F., Le, V.B. and Rautenbach, D., \textit{Forests and trees among Gallai graphs}, Discrete Mathematics, 338(2):190--195, 2015. t \bibitem{West} West, Douglas B., \textit{Introduction to Graph Theory}, Prentice Hall, 2nd edition, 2001. \end{thebibliography}

Autores: Durán, Guillermo / Fernández Slezak, Florencia / Grippo, Luciano / Oliveira, Fabiano / Safe, Martín.