All Title Author
Keywords Abstract


On the number of components of a graph

Full-Text   Cite this paper   Add to My Lib

Abstract:

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.

Full-Text

comments powered by Disqus