\documentclass[letterpaper, 10pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{palatino}
\usepackage{latexsym,amssymb,amsfonts,amsmath}
\usepackage{amsthm}
\usepackage{verbatim}
\usepackage{paralist}
\usepackage{graphics}
\usepackage[all]{xy}
\pagestyle{empty}

\addtolength{\voffset}{-2cm}
\addtolength{\textheight}{3cm}
\addtolength{\textwidth}{1.5cm}
\addtolength{\hoffset}{-0.5cm}
% \addtolength{\textwidth}{2cm}

\newcommand{\header}[2]{
	\begin{center}
 		\rule{\linewidth}{1pt}
 		\Large{#1}
 		\rule{\linewidth}{1pt}
 		\normalsize{#2}
 	\end{center}
}

\theoremstyle{plain}
\newtheorem{proposicion}{Proposition}
\newtheorem{lema}{Lema}
\newtheorem{teorema}{Teorema}
\newtheorem{corolario}{Corolario}
\newtheorem{conjetura}{Conjetura}

\theoremstyle{definition}
\newtheorem{definicion}[proposicion]{Definición}

\renewcommand{\figurename}{Figura}

\DeclareMathOperator{\mcd}{mcd}
\DeclareMathOperator{\exc}{e}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\cc}{cc}
\DeclareMathOperator{\Q}{Q}
\DeclareMathOperator{\domatic}{d}

\begin{document}
\header{Teoría de las Gráficas II}{Segunda lista de ejercicios}

\section{Conjuntos independientes y clanes}
Un conjunto de vértices de una gráfica es \emph{independiente} si y sólo si ninguna pareja de vértices en el conjunto es adyacente.  En otras palabras, $S \subseteq V(G)$ es independiente en $G$ si y sólo si la subgráfica inducida por $S$ en $G$, $G[S]$, no posee aristas.  Claramente si $S$ es independiente entonces cualquier $S' \subseteq S$ es independiente.

Un conjunto independiente de vértices es \emph{maximal} si no es subconjunto propio de ningún otro conjunto independiente de vértices.  Un conjunto independiente con el máximo número de elementos es un \emph{conjunto independiente de cardinalidad máxima}.  El número de vértices en un conjunto independiente de cardinalidad máxima en una gráfica $G$ es el \emph{número de independencia} de $G$ y se denota por $\alpha{G}$.

Algunos estimados para el número de independencia son:
\begin{equation}\label{eq:uno}
 \alpha(G) \geq \sum_{v \in V(G)} (1+d_G(v))^{-1}\text{,}
\end{equation}
\begin{equation}\label{eq:dos}
 \alpha{G} \geq \frac{\lvert V(G)\rvert}{1+d}\text{,}
\end{equation}
\begin{equation}\label{eq:tres}
 \alpha(G) \geq \frac{\lvert V(G) \rvert}{1+\Delta}\text{,}
\end{equation}
donde $d=\frac{\sum_{v\in V(G)} d_G(v)}{\lvert V(G) \rvert}$.

La noción de clan es la antípoda de la noción de conjunto independiente.  Un subconjunto no vacío de vértices de una gráfica es un \emph{clan} si y sólo si induce una subgráfica completa.  Un clan es \emph{maximal} si y sólo si no es subconjunto propio de ningún otro clan.  Un clan de cardinalidad máxima es un \emph{clan máximo}.  El número de vértices en un clan máximo es la \emph{rigidez} (en inglés \textit{toughness}) de la gráfica $G$ y se denota por $\phi(G)$.

Claramente, un subconjunto de los vértices de una gráfica $G$ es un clan si y sólo si es un conjunto independiente en la gráfica complementaria $G^c$.  Por lo tanto $\phi(G)=\alpha(G^c)$ y las desigualdades anteriores nos llevan también a cotas para $\phi(G)$.

Tonos los clanes, así como los clanes maximales, constituyen una cubierta de los vértices de una gráfica.  El mínimo número de clanes de $G$ que cubren $V(G)$ lo denotamos por $c(G)$.  Claramente, $c(G) \geq \alpha(G)$ para cualquier $G$.

El mínimo número de gráficas completas cuya unión es $G$ se denota por $\cc(G)$.  Este número también está relacionado con los clanes, ya que los clanes inducen subgráficas completas.

Considera $S$ un conjunto arbitrario y $C_1$, $C_2$, \ldots, $C_n$ una cubierta de $S$ (\textit{i.e.}, $\cup_{i=1}^n C_i = S$).  La \emph{gráfica de intersección} de $C_1$, $C_2$, \ldots, $C_n$ tiene por conjunto de vértices $C_1$, $C_2$, \ldots, $C_n$ y $C_i$ es adyacente a $C_j$ si y sólo si $C_i \cap C_j \neq \emptyset$.

La gráfica de intersección del conjunto de los clanes maximales de $G$ es la \emph{gráfica de clanes} de $G$ y se denota por $\Q(G)$.  Así, existe una biyección entre los vértices de $\Q(G)$ y los clanes maximales de $G$ y dos vértices de $\Q(G)$ son adyacentes si y sólo si los clanes correspondientes se intersectan.

\begin{enumerate}
 \item Cálcula los números de independencia para las gráficas de la primera lista.
 \item (*) Cálcula los números de independencia para las siguientes gráficas: a) $K_n$; b) $K_{1,n}$; c) $K_{m,n}$; d) $P_n$; e) $C_n$; f) la gráfica de Petersen y g) el $k$-cubo.
 \item (*) Cálcula los números de independencia para las gráficas de los sólidos platónicos.
 \item (*) Caracteriza las gráficas en las que:
\begin{enumerate}
\item todo subconjunto de vértices es independiente y
\item ningún conjunto independiente posee más de un vértice.
\end{enumerate}
 \item ¿Es cierto que todo conjunto (de vértices) independiente maximal en una gráfica es un conjunto indepediente de cardinalidad máxima?
 \item (*) ¿Cómo podría cambia el número de independencia de una gráfica
\begin{enumerate}
 \item después de borrar un vértice;
 \item después de borar una arista y
 \item después de agregar una arista?
\end{enumerate}
 \item Considera $G$ una gráfica bipartita con bipartición $(X$, $Y)$.  ¿Es cierto que $\alpha(G)=\max\{\lvert X \rvert$, $\lvert Y \rvert\}$=
 \item (*) Prueba que $G$ es bipartita si y sólo si $\alpha(G) \geq \frac{\lvert V(H) \rvert}{2}$ para toda subgráfica $H$ de $G$.
 \item (*) Prueba que si $G$ es un árbol entonces $\alpha(G) \geq \frac{\lvert V(G) \rvert}{2}$.
 \item (*) Prueba que toda gráfica conexa distinta de $K_2$ posee un un conjunto (de vértices) independiente que contiene todas las hojas de la gráfica.
 \item (*) Propón un algoritmo para la construcción de un conjunto indepediente maximal de vértices de una gráfica.
 \item (*) Prueba que si la distancia entre cualesquiera dos hojas de un árbol es para entonces el árbol tiene un único conjunto independiente de cardinalidad máxima.  ¿El recíproco es cierto?
 \item (*) Denota por $\alpha'(G)$ la mínima cardinalidad de un conjunto independiente maximal de vértices de una gráfica $G$.  Encuentra $\alpha'(G)$ para: a) $K_n$; b) $K_{1,n}$; c) $K_{m,n}$; d) $P_n$; e) $C_n$; f) la gráfica de Petersen y g) el $k$-cubo.
 \item (*) Para cualquier entero positivo $k$, construye una gráfica $G$ tal que:
\begin{displaymath}
 \alpha(G) - \alpha'(G)=k\text{.}
\end{displaymath}
 \item (*) Prueba que para gráficas $G$, $H$:
\begin{enumerate}
 \item $\alpha(G \cup H)=\alpha(G)+\alpha(H)$, si $V(G) \cap V(H) = \emptyset$.
 \item $\alpha(G+H)=\max(\alpha(G)$, $\alpha(H))$.
 \item $\alpha(G\times H) \geq \alpha(G)\alpha(H)$.
\end{enumerate}
 \item 
\begin{enumerate}
 \item (**) Prueba la fórmula~\ref{eq:uno}.
 \item (*) Prueba que la cota de la fórmula~\ref{eq:uno} la alcanzan gráficas no-triviales.
 \item (*) Diseña un algoritmo para encontrar un conjunto independiente de cardinalidad al menos $\sum_{v \in V(G)}(1+d_G(v))^{-1}$ en una gráfica $G$.
\end{enumerate}
 \item (**) Prueba la fórmula~\ref{eq:dos}.
 \item (**) Considera $I$ un conjunto independiente maximal de vértices de una gráfica $G$ y denota por $\rho(I)$ el número de aristas que conectan los vértices de $I$ con los vértices de $V(G)\setminus I$.  Prueba que $\rho(I)+\lvert I \rvert\geq \lvert V(G) \rvert$.
 \item (*) Prueba la fórmula~\ref{eq:tres} sin hacer uso de~\ref{eq:dos}.
 \item (**) Llama $l(G)$ al mínimo número de trayectorais de una gráfica cuya unión cubre $V(G)$.  Prueba que $l(G) \leq \alpha(G)$.
 \item (*) Prueba que $\alpha(G)\leq\frac{\lvert E(G) \rvert}{\delta}$ para todas las gráficas sin vértices aislados.
\end{enumerate}

\section{Cubiertas}
Diremos que un vértice y una arista \emph{se cubren entre sí} si son incidentes.  Así, una arista $e=uv$ cubre a $u$ y a $v$ y cada uno de estos vértices cubre $e$. Un conjunto $S \subseteq V(G)$ es una \emph{cubierta} (\emph{cubierta de vértices}) de una gráfica $G$ si cada arista de la gráfica incide con al menos un vértice de $S$.  Una cubierta de una gráfica es \emph{minimal} si y sólo si no contiene una cubierta con menos vértices y es una \emph{cubierta de cardinalidad mínima} si y sólo si tiene el menor número de elementos de entre todas las cubiertas de $G$.  Este número es el \emph{número de cubierta} o \emph{número de cubierta de vértices} de la gráfica y se denota por $\beta(G)$.  El número de independencia y el númbero de cubierta están relacionados entre sí:
\begin{equation}
 \alpha(G)+\beta(G)=\lvert V(G) \rvert\text{.}
\end{equation}

Una \emph{cubierta de aristas} de una gráfica $G$ es un subconjunto $S$ de las
aristas $E(G)$ de $G$ que cubre todos los vértices de $G$, \textit{i.e.}, cada
vértice de la gráfica es incidente con al menos una arista de $S$.  Una cubierta
de aristas de una gráfica es \emph{minimal} si y sólo si no contiene una
cubierta con un menor número de aristas y es una \emph{cubierta de cardinalidad
mínima} si y sólo sí tiene el menor número de elementos entre todas las
cubiertas de aristas de $G$.  Este número es llamado el \emph{número de cubierta
de aristas} de la gráfica y se denota por $\beta'(G)$.

\begin{enumerate}
 \item Determina $\beta(G)$ y $\beta'(G)$ para las gráficas de la primera lista.
 \item (*) Determina los valores de $\beta(G)$ y $\beta'(G)$ para las siguiente gráficas:  a) $K_n$; b) $K_{1,n}$; c) $K_{m,n}$; d) $P_n$; e) $C_n$; f) la gráfica de Petersen y g) el $k$-cubo.
 \item (*) Da un ejemplo de una gráfica bipartita con $\beta < \min(m$, $n)$, donde $m$ y $n$ son las cardinalidades de cada una de sus partes.
 \item ¿Existe una gráfica conexa en la cuál una cubierta minimal contiene todos los vértices?
 \item (*) Caracteriza las gráficas conexas para las cuales una cubierta minimal de aristas contiene todas las aristas.
 \item (*) Prueba que existe una cubierta de mínima cardinalidad de un árbol distinto de $K_2$ que contiene todos los vértices adyacentes a las hojas.
 \item (*) Da un algoritmo para construir una cubierta de cardinalidad mínima de un árbol.
 \item Encuentra una gráfica donde una cubierta minimal no sea una cubierta de cardinalidad mínima.
 \item Encuentra una gráfica donde una cubierta minimal de aristas no sea una cubierta de aristas de cardinalidad mínima.
 \item (*) Prueba que para una gráfica $G$ sin vértices aislados se tienen las siguientes desigualdades:
\begin{displaymath}
 \frac{\lvert V(G) \rvert}{2} \leq \beta'(G) \leq \lvert V(G) \rvert -1\text{.}
\end{displaymath}
Para cualquier entero positivo $n$, encuentra una gráfica de orden $n$ para la cual alguna de las desigualdades se vuelve igualdad.
\end{enumerate}

\section{Dominación}
Un subconjunto de vértices $S$ de una gráfica $G$ es \emph{dominante} si todo vértice de $V(G)\setminus S$ es adyacente a algún vértice de $S$, \textit{i.e.}, todo vértice de $G$ está a distancia a lo más uno de algún vértice de un conjunto dominante.  Un conjunto dominante es \emph{minimal} si y sólo si no contiene un conjunto dominante propio y es \emph{de cardinalidad mínima} si y sólo si tiene la menor cardinalidad de entre todos los conjuntos dominantes de $G$.  Este número es llamado el \emph{número de dominación} de $G$ y se denota por $\gamma(G)$.

\begin{enumerate}
 \item Cálcula $\gamma(G)$ para las gráficas de la primera lista.
 \item (*) Cálcula $\gamma(G)$ para las siguientes gráficas: a) $K_n$; b) $K_{1,n}$; c) $K_{m,n}$; d) $P_n$; e) $C_n$; f) la gráfica de Petersen y g) el $k$-cubo.
 \item Encuentra una gráfica para la cual un conjunto dominante minimal no sea
de cardinalidad mínima.
 \item (*) Encuentra una gráfica en la cual $\alpha(G)=\gamma(G)=3$ y todo
conjunto independente de cardinalidad máxima sea también dominante de
cardinalidad mínima.
 \item (*) Prueba que un conjunto indepediente de vértices de una gráfica es
maximal si y sólo si es dominante.
 \item (*) Prueba que $\alpha(G) \geq \gamma(G)$ pra cualquier gráfica $G$.
 \item (*) Prueba las desigualdades:
\begin{displaymath}
 \frac{\lvert V(G) \rvert }{\Delta+1}\leq \gamma(G) \leq \lvert
V(G)\rvert-\Delta
\end{displaymath}
para cualquier gráfica $G$.  Da gráficas $G_1$, $G_2$ tales que:
\begin{displaymath}
 \gamma(G_1)=\frac{\lvert V(G_1)\rvert}{\Delta(G_1)+1}\text{,}\qquad
\gamma(G_2)=\lvert V(G_2)\rvert - \Delta(G_2)\text{.}
\end{displaymath}
 \item (**) (Ore, 1962)  Prueba que un conjunto dominante $S$ es minimal si y
sólo para todo $v$ en $S$ se satisfacen una de las dos siguientes condiciones:
\begin{enumerate}
 \item la gráfica no posee aristas $vu$ con $u\in S$ o
 \item si la gráfica posee una arista $vu$ con $u \in S$ entonces existe una
arista $uw$ con $w \notin S$, donde $u$ es el único vértice de $D$ adyacente a
$w$.
\end{enumerate}
 \item (**) (Ore, 1962) Prueba que una gráfica $G$ sin vértices aislados posee
un conjunto dominante $S$ tal que $V(G)\setminus S$ también es dominante.
 \item (*) Prueba que si una gráfica $G$ no posee vértices aislados entonces
$\gamma(G) \leq \frac{\lvert V(G) \rvert}{2}$.  Para $n$ par, encuentra una
gráfica de orden $n$ tal que $\gamma(G)=\frac{\lvert V(G) \rvert}{2}$.
 \item (*) Prueba que si $S$ es un conjunto dominante minimal de $G$ y ésta no
tiene vértices aislados entonces $V(G)\setminus S$ también es dominante.
 \item (*) Prueba que para todo conjunto dominante minimal de una gráfica sin
vértices aislados existe otro conjunto dominante minimal ajeno con el primero.
 \item (*) Prueba toda gráfica posee un conjunto dominante minimal que contiene
todos los vértices adyacentes a todas las hojas.
 \item (*) Da un algoritmo para construir un conjunto dominante de cardinalidad
mínima de un árbol.
 \item (**) Prueba que para toda gráfica $G$ existe una gráfica $H$ que contiene
un conjunto dominante de cardinalidad mínima $S$ tal que $H[S] \cong G$.
 \item (*) Encuentra una gráfica que posea un conjunto dominante independiente
$S$ tal que $\lvert S \rvert = \alpha(G) =\gamma(G)$.
 \item (*) El \emph{número domático} $\domatic(G)$ es el número máximo de
conjuntos dominantes de $G$ que cubren $V(G)$.  Prueba que $\domatic(G) \leq
\Delta + 1$.
 \item (*) Denota por $\gamma_i(G)$ el mínimo número de vértices entre todos
los conjuntos dominantes e independientes de $G$.
\begin{enumerate}
\item Prueba que $\gamma(G) \leq \gamma_i(G) \leq \alpha(G)$ para cualquier
gráfica $G$.
\item Da ejemplos de gráficas para las cuáles las relaciones anteriores
satisfacen la desigualdad estricta y la igualdad.
\item Encuentra una gráfica $G$ de órden mínimo tal que $\gamma(G) <
\gamma_i(G)$.
\item Prueba que $\gamma_i(G) - \gamma(G)$ puede ser arbitrariamente grande. 
\end{enumerate}
 \item Calcula $\gamma_i(G)$ para las gráficas de la primera lista.
 \item Calcula $\gamma_i(G)$ para las siguientes gráficas: a) $K_n$; b)
$K_{1,n}$; c) $K_{m,n}$; d) $P_n$; e) $C_n$; f) la gráfica de Petersen y g) el
$k$-cubo.
 \item (**) Prueba que $\gamma(G) \leq \beta(G)$.  Encuentra una gráfica
$\gamma(G) < \beta(G)$.
 \item (*) Encuentra una gráfica con $\gamma_i(G) > \beta(G)$ y una con
$\gamma_i(G) < \beta(G)$. 
\end{enumerate}
\end{document}