Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason (other than the potentially large size of centers) why such a notion isn't fruitful (e.g. subsumed by other notion)?

I'm looking for something similar to this:

Let $G=(V,E)$ be an undirected graph. Its central decomposition is

  • If $G$ is not connected: the set of central decompositions of its connected components.
  • If $G$ is self-centered (radius equals diameter): $G$
  • If $G$ is connected and not self-centered and its center is $C$: the pair $(I,O)$ where $I$ is the central decomposition of $G[C]$ and $O$ is the central decomposition of $G[V\setminus C]$ (induced subgraphs of center and its complement)

Its central width shall be the size of largest self-centered graph which appears in its central decomposition.

The notion may also use other concepts (like complements, trees etc.), but it should use centers recursively. There is no need for uniqueness.

I'm not looking for e.g. path distance decompositions (see here) where the root is the center, i.e. a map $d$ of a path $\{p_0,\dots,p_k\}$ to $V$ where $d(p_i)=\{v\in V\mid \min_{c \in C}\mathrm{dist}(v,c) = i\}$ ($C$ being the center of $G$).


Your Answer

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

Browse other questions tagged or ask your own question.