%0 Journal Article
%T On the number of components of a graph
%A Hamza Si Kaddour
%A Elias Tahhan Bittar
%J Contributions to Discrete Mathematics
%D 2010
%I University of Calgary
%X Let $G:=(V,E)$ be a simple graph; for $Isubseteq V$ we denote by $l(I)$ the number of components of $G[I]$, the subgraph of $G$ induced by $I$. For $V_1,ldots , V_n$ subsets of $V$, we define a function $eta (V_1,ldots , V_n)$ which is expressed in terms of $lleft(igcup _{i=1} ^{n} V_i ight)$ and $l(V_icup V_j)$ for $ileq j$. If $V_1,ldots , V_n$ are pairwise disjoint independent subsets of $V$, the number $eta (V_1,ldots , V_n)$ can be computed in terms of the cyclomatic numbers of $Gleft[igcup _{i=1} ^{n} V_i ight]$ and $G[ V_icup V_j]$ for $i eq j$. In the general case, we prove that $eta (V_1,ldots , V_n)geq 0$ and characterize when $eta (V_1,ldots , V_n)= 0$. This special case yields a formula expressing the length of members of an interval algebra cite{s} as well as extensions to pseudo-tree algebras. Other examples are given.
%U http://cdm.math.ucalgary.ca/cdm/index.php/cdm/article/view/140