Sesión Matemática Discreta

Diciembre 14, 12:20 ~ 12:40

Nulidad máxima y mínima de una secuencia de grados de árboles

MOLINA MUNAFÓ, Luis Gonzalo

Una secuencia de enteros no negativos $d_1, d_2, \ldots , d_n$ es llamada una secuencia de grados de un grafo $G$, de orden $n$, si los vertices de $G$ existe una rotulación $v_1, v_2, \ldots, v_n$ de los v\'{e}rtices de $G$ tal que $ \deg{v_i} = d_i$ para $1 \leq i \leq n$. ttt tttEn \cite{chartrand2010graphs} se demuestra que una secuencia $s:d_1, d_2,\ldots, d_n$ de $n$ enteros positivos, con $n \geq 2$, es la secuencia de grados de un árbol si y sólo si \[\sum_{i=1}^{n}{d_i}=2n-2.\] ttt tttDado un grafo $G$ de orden \(n\) y tama\~{n}o \(e\), sus vertices se pueden rotular de forma tal que $d_1 \leq d_2 \leq \ldots \leq d_n$, donde $ d_i =\deg{(v_i)}$ y $ V=\{v_1,v_2, \dots,v_n\}$. El \textbf{n\'{u}mero de aniquilación} de \(G\), denotado por $a(G)$, es el máximo $k$ tal que $\sum_{i=1}^{k}{d_i} \leq e$. ver \cite{pepper}. ttt ttt tttDada $s$, una secuencia de grados de árboles. Sea $\mathcal{T}_s$ la familia de árboles que tienen a $s$ como secuencia de grados. Sea $n$ el orden de todo \'{a}rbol en \(\mathcal{T}_{s}\). Sea $\nu(T)$ el tamaño del matching máximo de $T$. Sea $l$ la cantidad de 1's de la secuencia y $a(s)$ el n\'{u}mero de aniquilación de \(s\), que es n\'{u}mero de aniquilación de cualquier \(T \) en \(\mathcal{T}_{s}\). En este trabajo demostramos que ttt$$ n-a(s) \leq \nu(T)\leq \min\{ n-l,\lfloor \frac{n}{2}\rfloor\}$$ tttpara todo $T\in \mathcal{T}_s$. ttt tttPor otro lado tambi\'{e}n probamos que existen dos árboles de \(\mathcal{T}_s\), $T_1$ y $T_2$, para los cuales $\nu(T_1)=n-a(s)$ y $\nu(T_2)= \min\{ n-l,\lfloor \frac{n}{2}\rfloor\}$. ttt tttDefinimos la nulidad m\'{a}xima y la nulidad m\'{\i}nima de \(\mathcal{T}_S\) como: ttt\[ ttt\text{null}_{M}(s):= \max_{T \in \mathcal{T}_{s} }\text{null}\, A(T) ttt\] ttty ttt\[ ttt\text{null}_{m}(s):= \min_{T \in \mathcal{T}_{s}} \text{null}\, A(T) ttt\] tttdonde $A(T)$ es la matriz de adyacencia de \(T\). De \cite{bevis} se sabe que $\text{rank}(T)=2\nu(T)$ lo que junto con el resultado sobre matchings implican ttt tt $$\text{null}_{M}(s)=2a(s)-n$$ y \[\text{null}_{m}(s)=\left\{ ttt\begin{tabular}{c l} ttt$2l-n$&\text{si } $n-l\leq \lfloor \frac{n}{2}\rfloor$ \\ ttt1&\text{si } $n-l> \lfloor \frac{n}{2}\rfloor$ \text{y} $n$ \text{es impar}\\ ttt0&\text{si } $n-l> \lfloor \frac{n}{2}\rfloor$ \text{y} $n$ \text{es par} ttt\end{tabular} ttt\right.\] tttComo corolario de los resultados anteriores tenemos que tttel número de independencia máximo y mínimo de \(\mathcal{T}_s\), denotados $\alpha_M(s)$ y $\alpha_m(s)$ respectivamente, definidos de forma an\'{a}loga, son: ttt $$\alpha_M(s)=a(s)$$ ttt y ttt \[\alpha_m(s)=\left\{ ttt\begin{tabular}{c l} ttt$l$&\text{si } $n-l\leq \lfloor \frac{n}{2}\rfloor$ \\ ttt$\lceil\frac{n}{2}\rceil$&\text{si } $n-l> \lfloor \frac{n}{2}\rfloor$ ttt\end{tabular} ttt\right.\] ttt tttTambi\'{e}n demostramos que la nulidad (de dos en dos), el número de matching y el número de independencia tienen propiedad de intervalo en $s$. \begin{thebibliography}{9} t \bibitem{pepper}{\textit{Graphs with equal Independence ttand Annihilation Numbers}, Larson, Craig E. and Pepper, Ryan. 2011. The electronic journal of combinatorics.} \bibitem{bevis}{\textit{Rank of trees and grid graphs}, Bevis, Jean H. and Domke, Gayla S. and Miller, Valerie A. 1995. The journal of combinatorial mathematics and combinatorial computing.} \bibitem{chartrand2010graphs}{\textit{Graphs \& digraphs}, Chartrand, Gary and Lesniak, Linda and Zhang, Ping, 2010, CRC press. } \end{thebibliography}

Autores: MOLINA MUNAFÓ, Luis Gonzalo / Jaume, Daniel A..