Sesión Matemática Discreta

Diciembre 15, 11:00 ~ 11:20

Grafos de intervalos propios como geomtrí a convexa

Tondato, Silvia B.

Sea $V$ un conjunto finito, $\mathcal{M}$ una colección de subconjuntos de $V$, cerrada por intersecciones y conteniendo a $\emptyset$ y $V$. Los elementos de $\mathcal{M}$ se denominan \textit{convexos} y el par $(V,\mathcal{M})$ recibe el nombre de \textit{espacio de convexidad}. Dado un conjunto $S \subseteq V$, el menor conjunto convexo que contiene al conjunto $S$ se denomina \textit{cápsula convexa} de $S$. Un vértice $x \in S$, $S \subseteq V$ un conjunto convexo, se dice \textit{extremo} de $S$ si $S-\{x\}$ es un también un conjunto convexo. Una \textit{geometrí a convexa} es un espacio de convexidad que satisface: \textit{Cada convexo es cápsula convexa de sus extremos} \cite{v}. Las convexidades más naturales definidas en un grafo $G$ son aquellas que surgen de un sistema de caminos $\mathcal{P}$ en el grafo $G$, que contienen a todos los caminos geódesicos. Un $A \subseteq V(G)$ es $\mathcal{P}-convexo$ si para todo par de vértices $u$ y $v$ de $A$ resulta $\mathcal{P}(u,v) \subseteq A$, siendo $\mathcal{P}(u,v) $ el conjunto de todos los vértices de caminos de $\mathcal{P}$ uniendo $u$ y $v$. Las elecciones canónicas para $\mathcal{P}$ son tomar todos los caminos, caminos triangulados, inducidos, mí nimos y geódesicos. Algunas convexidades pueden coincidir para ciertos grafos. Por ejemplo los árboles son aquellos grafos para los cuales las cuatro convexidades antes mencionadas coinciden. Se sabe que los grafos cordales son una geomtrí a respecto de la convexidad definida por los caminos inducidos \cite{fj} y que los grafos de intervalos son una geomtrí a respecto de la convexidad definida por los caminos toll \cite{lm}. En este trabajo se introduce el concepto de caminos toll débiles. Un \textit{camino toll débil} entre $u$ y $v$ es una secuencia de vértices de la forma:\\ $\mathcal{P}(u,v): u,w_1, . . . ,w_k, v$, donde $k \geq 1$, satisfaciendo las siguientes condiciones:\begin{itemize} \item $w_iw_{i+1} \in E(G)$ para todo $i$, $uw_1 \in E(G)$ y $vw_k \in E(G)$,\item para $i \neq 1$, $uw_i \in E(G)$ si y sólo si $w_i=w_1$,\item para $i \neq k$, $vw_i \in E(G)$ si y sólo si $w_i=w_k$.\end{itemize} Se prueba que los grafos de intervalos propios son una geometrí a respecto de la convexidad definida por los caminos toll débiles. {\small \begin{thebibliography}{999} \bibitem{lm} L. Alcón, B. Be\v{s}ar, T. Gologranc, M. Gutierrez, T. Kraner \v{S}umenjake, I. Peterin, A. Tepehf: Toll convexity. \textit{European Journal of Combinatorics.} {\bf 46} (2015), 161-–175. \bibitem{fj} M. Farber, R.E. Jamison: Convexity in graphs and hypergraphs. SIAM J. Algebr. \textit{Discrete Mathematics.} {\bf 7} (1986), 433-–444. \bibitem{v} M.L.J. van de Vel: Theory of Convex Structures, \textit{North Holland, Amsterdam}. (1993). \end{thebibliography}}

Autores: Tondato, Silvia B. / GUTIERREZ, Marisa.