Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+
 All Title Author Keywords Abstract
 Publish in OALib Journal ISSN: 2333-9721 APC: Only \$99

 Relative Articles On the connected components of a random permutation graph with a given number of edges The resolving number of a graph On the Number of cycles in a Graph On the Number of Cycles in a Graph The overlap number of a graph The regular number of a graph A measure of graph vulnerability: scattering number The incidence chromatic number of some graph Number of components of the nullcone The number of trees in a graph More...

# On the number of components of a graph

 Full-Text   Cite this paper

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