Sesión Matemática Discreta

Diciembre 14, 11:00 ~ 11:20

Link operation and nullity of trees.

Jaume, Daniel A.

t{ tttGiven two disjoint trees \(T_{1}\) and \(T_{2}\), and two vertices, \(v_{1} \in V(T_{1})\) and \(v_{2} \in V(T_{2})\), the \textbf{link between} \(T_{1}\) and \(T_{2}\) \textbf{through} \(v_{1}\) and \(v_{2}\), denoted by ttt\[ ttt(T_{1},v_{1}) \multimap(T_{2},v_{2}), ttt\] tttis the tree obtained by adding an edge between \(v_{1}\) and \(v_{2}\): ttt\begin{itemize} tttt\item\(V\left((T_{1},v_{1}) \multimap (T_{2},v_{2})\right) = V(T_{1}) \cup V(T_{2}) \). tttt\item \( E\left((T_{1},v_{1}) \multimap (T_{2},v_{2}) \right) = E(T_{1}) \cup E(T_{2}) \cup \{v_{1},v_{2}\} \). ttt\end{itemize} tt ttWith \(T_{1} \multimap T_{2}\) we denote an arbitrary link between both trees. t} The nullity of the adjacency matrix of \(T\) is denoted by \(null(T)\). The vertices in the support of \(T\) are called supported-vertices, see \cite{Jaume2015NDT}. Teorema 1: Let \(T_{1}\) and \(T_{2}\) be two disjoint trees. If the linked vertices are both supported, then t\[ tnull(T_{1}\multimap \, T_{2}) = null(T_{1}) + null(T_{2})-2, t\] totherwise t\[ tnull(T_{1} \multimap \, T_{2}) = null(T_{1}) + null(T_{2}). t\] As direct corollaries we have Corollary 1: Let \(T_{1}\) and \(T_{2}\) be two disjoint trees. If the linked vertices are both supported, then t\[\nu (T_{1} \multimap \, T_{2}) = \nu(T_{1}) +\nu(T_{2})+1, \] totherwise t%\begin{enumerate} t\[ \nu (T_{1} \multimap \, T_{2}) = \nu(T_{1} +\nu(T_{2}), \] twhere \(\nu (T)\) is the matching number of \(T\). Corollary 2: Let \(T_{1}\) and \(T_{2}\) be two disjoint trees. If the linked vertices are both supported, then t%\begin{enumerate} t%t\item \( \nu (T_{1} \link \, T_{2}) = \nu(T_{1} +\nu(T_{2})+1 \). t\[\alpha (T_{1} \multimap \, T_{2})= \alpha (T_{1}) + \alpha (T_{2})-1,\] t%\end{enumerate} totherwise t%\begin{enumerate} t%t\item \( \nu (T_{1} \link \, T_{2}) = \nu(T_{1} +\nu(T_{2}) \). t\[\alpha (T_{1} \multimap \, T_{2}) = \alpha (T_{1}) + \alpha (T_{2}),\] t%\end{enumerate} twhere \(\alpha (T)\) is the independent number of \(T\). \begin{thebibliography}{9} t \bibitem{Jaume2015NDT}{ Daniel A. Jaume, and Gonzalo Molina. \textit{Null decomposition of trees}. Preprint, 2017.} \end{thebibliography}

Autores: Jaume, Daniel A..