Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G = (V,E)$ be an undirected finite simple graph with no loops.

Definition Let's call a subset $U\subset V$ autonomous if every vertex of $V\ \setminus U$ is either adiacent to every vertex of $U$ or not adiacent to any of them.

This notion is used in J. Körner, G. Simonyi, Zs. Tuza, Perfect couples of graphs, Combinatorica, 12 (2) (1992), 179-192 to derive an equation that graph entropy must satisfy. This equation relates the entropy of $G$ with the entropy of the smaller graph obtained by collapsing $U$ to a single vertex, connected with each vertex that was connected to every vertex of $U$.

I was surprised to learn in chat that a similar construction is used in automata theory to simplify certain finite state machines.

Are there other constructions that are usually employed to link a certain function on a graph with the same function calculated on a smaller but related graph?

[My motivation is to conjecture their equivalent for graph entropy and try to prove them.]

share|cite|improve this question
I now know that autonomous sets are more commonly called modules, and the recursive decomposition of a graph using modules is called modular decomposition. – Jacopo Notarstefano Nov 9 '11 at 12:47
up vote 3 down vote accepted

We have the notion of split decomposition, defined as follows.

Let $S$ be a subset of the vertices, and let's define $N(S)=\{t\in V\ \setminus S : \exists\ s\in S, (t,s)\in E\}$ as the set of neighbors of $S$.

Let $\{V_1, V_2\}$ be a partition of the set of vertices such that $|V_1|\ge 2$, $|V_2|\ge 2$. Let's also define $V_{1}' = N(V_2)$, $V_{2}' = N(V_1)$.

Definition. $\{V_1, V_2\}$ is a split for the graph $G$ if $\forall v\in V_{1}'$, $\forall w \in V_{2}'$ we have $(v,w)\in E$. If $G$ has no such split we say that $G$ is prime for the split decomposition.

If $\{V_1, V_2\}$ is a split for $G$ we might add a new node $m$ to the vertex set, connected with exactly the nodes in $V_{1}'\cup V_{2}'$, called a marker.

Definition If $\{V_1, V_2\}$ is a split for $G$ with marker $m$ we call split decomposition of $G$ the set of prime graphs obtained by recursively finding a split for the graphs whose vertex sets are $V_1\cup m$ and $V_2\cup m$.

Computing the split decomposition is polynomial in the size of the graph, as shown in T.H. Ma, J. Spinrad, Split Decomposition of Undirected Graphs, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms(1990), 252-260.

share|cite|improve this answer

We have the following well-known lemma about colorings.

Let $G$ be a graph, and $v$, $w$ non-adjacent vertices. Let's define the graph $G^{+}$, where we have added to $G$ the edge $(v,w)$. Let's also define $G^{-}$, the graph were we identify $v$ and $w$ in a new vertex adjacent to every vertex that was adjacent to at least one of them.

Lemma. $\chi(G)=\min\{\chi(G^{+}),\chi(G^{-})\}$

To prove this we notice that there is a bijection between colorings of $G$ where $v$ and $w$ have different colors and colorings of $G^{+}$. There is also a bijection between colorings of $G$ where $v$ and $w$ have the same color and colorings of $G^{-}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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