On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

Abstract

A cut \((A, B)\) (where \(B = V – A\)) in a graph \(G = (V, E)\) is called internal if and only if there exists a vertex \(x \in A\) that is not adjacent to any vertex in \(B\) and there exists a vertex \(y \in B\) such that it is not adjacent to any vertex in \(A\). In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut \((A, B)\) in a chordal graph \(G\), there exists a clique with \(\kappa(G) + 1\) vertices (where \(\kappa(G)\) is the vertex connectivity of \(G\)) such that it is (approximately) bisected by the cut \((A, B)\). In fact, we give a stronger result: For any internal cut \((A, B)\) of a chordal graph, and for each \(i\), \(0 \leq i \leq \kappa(G) + 1\), there exists a clique \(K_i\) such that \(|A \cap K_i| = \kappa(G) + 1\), \(|A \cap K_i| = i\), and \(|B \cap K_i| = \kappa(G) + 1- i\).

An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be \(\Omega(k^2)\) where \(\kappa(G)\). Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least \(\frac{\kappa(G)(\kappa(G) + 1)}{2}\), where \(\kappa(G)\) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to \(\kappa(G)\). This result is tight.