# How to call subgraphs that are node-induced and connected?

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.

• 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. – bof Feb 29 '16 at 9:09
• I agree that this is even more common. – Max Flow Mar 1 '16 at 13:04
• 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. – 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.