4
$\begingroup$

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.]

  • 1
    I now know that autonomous sets are more commonly called modules, and the recursive decomposition of a graph using modules is called modular decomposition.2011-11-09

2 Answers 2

3

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.

1

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^{-}$.