全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133