0
$\begingroup$

I know that strong component in a graph means between any 2 vertices there should be bi-directional path.

My doubt is cycle is always a strong component. can there be any other subgraph with some property P so that it is strong component ie., P implies strong component.

$\endgroup$
1
$\begingroup$

Your question is a bit too broad. There can be a lot of properties $P$ such that if $H$ is a subgraph of $G$ and $P(H)$ holds then all vertices of $H$ are in the same strong component.

For example:

  • $P(H) = $ true iff H is a (directed) clique
  • $P(H) = $ true iff H contains only one vertex
  • $P(H) = $ true iff for every edge $(u,v)$ of $H$, $(v,u)$ is also in $H$.
  • $P(H) = $ true iff $H$ has $n>1$ vertices and more than $(n-1)^2$ edges.
  • ...

You can prove that the last condition implies that the vertices of $H$ are in a strong component by induction on $n$.

If $n=2$ then the graph has more than $1^2 = 1$ edge, i.e., it has at least two edges. The claim trivially follows.

If $n>2$, then let $H'$ be any (not necessarily proper) subgraph of $H$ with $(n-1)^2+1$ edges. Pick a vertex $v$ of minimum degree in $H'$. The degree $\delta$ of $v$ is at most $\frac{(n-1)^2+1}{n}$. Therefore $H-v$ has $n-1$ vertices and at least $(n-1)^2 + 1 - \delta = \frac{n(n-1)^2+n - (n-1)^2 - 1}{n} > (n-2)^2$ edges. By inductive hypothesis $H-v$ is strongly connected. The claim follows since $\delta$ is at least $(n-1)^2 + 1 - (n-1)(n-2) = (n-1)(n-1 -n +2) = (n-1) + 1 = n$, showing that $v$ has at least one incoming and one outgoing edge.

$\endgroup$
1
  • $\begingroup$ Sir i recently started studying graphs from corman. I was just thinking what all other properties could make it strong component. can you please elaborate, if possible, on your last 2 points (atleast some google links is also fine. Searched but could not find) $\endgroup$ – Nascimento de Cos Jun 9 '20 at 12:54
1
$\begingroup$

A strong component in a graph $G$, is a group of vertices $V_s$ such that $\forall v_1,v_2\in V_s:\exists u_1,...,u_n\in V_s:v_1=u_1\rightarrow u_2\rightarrow...\rightarrow u_n=v_2$.

In simpler terms: It means that every two nodes have a path between them (going through only vertices in the strong component).

In the case of a cycle: say, $v_1\rightarrow ...\rightarrow v_k\rightarrow v_1$ is the cycle, then it would be a strong component as every two vertices in it have a path between them.

There could be other cases with strong components, but every (non-trivial) strong component contains a cycle as we know $v\in V_s$ implies there is a path between $v$ and $v$ with nodes within $V_s$.

Furthermore, every (non-trivial) strong component $V_s=\{v_1,...,v_n\}$ has a cycle that goes through every node. Just take the path between $v_1$ and $v_2$, concatenate it with the path from $v_2$ to $v_3$ and so on (and finally also the path between $v_n$ and $v_1$).

$\endgroup$
1
  • $\begingroup$ You are right. I will fix it to every non-trivial strong component (aka, every strong component with at least 2 nodes) $\endgroup$ – nir shahar Jun 9 '20 at 13:15

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.