Link operation and nullity of trees

JAUME, DANIEL ALEJANDRO

Buenos Aires

Congreso; RSME-UMA 2017; 2017

RSME-UMA

Given 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\[(T_{1},v_{1}) \multimap(T_{2},v_{2}),\]is the tree obtained by adding an edge between \(v_{1}\) and \(v_{2}\): \begin{itemize}\item\(V\left((T_{1},v_{1}) \multimap (T_{2},v_{2})\right) = V(T_{1}) \cup V(T_{2}) \).\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}\} \).\end{itemize}With \(T_{1} \multimap T_{2}\) we denote an arbitrary link between both trees.}The nullity of the adjacency matrix of \(T\) is denoted by \(null(T)\). A vertices of 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\[null(T_{1}\multimap \, T_{2}) = null(T_{1}) + null(T_{2})-2,\]otherwise\[null(T_{1} \multimap \, T_{2}) = null(T_{1}) + null(T_{2}).\]As direct corollaries we haveCorollary 1: Let \(T_{1}\) and \(T_{2}\) be two disjoint trees. If the linked vertices are both supported, then\[\nu (T_{1} \multimap \, T_{2}) = \nu(T_{1}) +\nu(T_{2})+1, \]otherwise%\begin{enumerate}\[ \nu (T_{1} \multimap \, T_{2}) = \nu(T_{1} +\nu(T_{2}), \]where \(\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%\begin{enumerate}%\item \( \nu (T_{1} \link \, T_{2}) = \nu(T_{1} +\nu(T_{2})+1 \).\[\alpha (T_{1} \multimap \, T_{2})= \alpha (T_{1}) + \alpha (T_{2})-1,\]%\end{enumerate}otherwise%\begin{enumerate}%\item \( \nu (T_{1} \link \, T_{2}) = \nu(T_{1} +\nu(T_{2}) \).\[\alpha (T_{1} \multimap \, T_{2}) = \alpha (T_{1}) + \alpha (T_{2}),\]%\end{enumerate}where \(\alpha (T)\) is the independent number of \(T\).\begin{thebibliography}{9}\bibitem{Jaume2015NDT}{Daniel A. Jaume, and Gonzalo Molina. \textit{Null decomposition of trees}. Preprint, 2017.}\end{thebibliography}