Typically, any connected subgraph of a graph $G$ is called a component of $G$. More specific are those subgraphs of a graph $G$ that are both connected and node-induced.

In areas of applied mathematics, I have come across different terms for the latter. In machine learning research, they are called clusters. In image analysis research, they are called segments. Personally, I prefer to call connected subgraphs just connected subgraphs, and to use the term component for every subgraph that is node-induced and connected. This way, a decomposition of a graph $G = (V,E)$ can be defined as a partition $\Pi$ of the node set such that, for every $V' \in \Pi$, the subgraph of $G$ induced by $V'$ is connected (and hence a component of $G$). However, my using the term this way sometimes causes confusion.

Although I am fully aware that terms are not essential, ultimately, I would like to avoid confusion. Thus, my question is which others terms are typically used for the subgraphs that are both node-induced and connected.

  • 1
    $\begingroup$ Is it really common to call any connected subgraph a component? I've only seen "component" used for a maximal connected subgraph; as such, of course it's an induced subgraph. $\endgroup$ – bof Feb 29 '16 at 9:09
  • $\begingroup$ I agree that this is even more common. $\endgroup$ – Max Flow Mar 1 '16 at 13:04
  • $\begingroup$ This is (extremely, I think) niche terminology, but they have been called "tubes" in at least one situation: "A tube is a proper nonempty set of nodes of [a graph] $\Gamma$ whose induced graph is a proper, connected subgraph of $\Gamma$" from Carr and Devadoss. $\endgroup$ – pjs36 Jul 9 '16 at 17:36

To answer your question, I would call a node-induced connected subgraph a "connected, induced subgraph".

I wanted to address a few other things you mentioned though. I should start by noting that I am a student studying graph theory from a theoretical rather than applied setting, so the terminology I use may be different than what you are used to.

First, I would be very confused if you used the term "component" to mean "node-induced connected subgraph". As mentioned in a comment, I have only heard and seen "component" used to describe a "maximal node-induced connected subgraph."

Second, I'm not sure if you didn't fully write out your definition of "decomposition", but it is far off from the concept I am familiar with. In the circle I run in, a "decomposition" $\mathcal{D}$ of $G=(V,E)$ is a collection $\{H_1,H_2,...,H_n\}$ of nonempty edge-induced subgraphs such that $\{E(H_1),E(H_2),...,E(H_n)\}$ is a partition of $E$.

This differs from your definition in a few crucial ways. First, in my circle, a decomposition is some sense an "edge-inspired concept"(you decompose the edge set, not the vertex set.) Second, with your definition, one could choose to partition $V$ into singletons, but then all of the edge information is lost. Third, while most of the uses of "decomposition" I have seen decompose into connected graphs, there is no requirement for connectivity as long as each edge is present exactly once in the decomposition.

This may be just a difference in terminology due to a difference in research areas, but I would advise caution using these words as you have described without further qualification.


It really depends on the background of the research and the goal.

  • Clusters are used in Percolation Theory.

  • Component such as weakly-connected component for digraph and strongly-connected component for digraph are used in Graph Theory.

  • Bayesian networks sometimes synonyms with DAGs (directed acyclic graphs) used more by applied practioners.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.