On interval graphs, minimal vertex separators are well understood: they are cliques, there are no more than $n$ ones. However, when we turn to the minimal edge cut, my search found no even one single paper, which surprised me.

To make it more precise, the edge cuts are defined as follows. In an interval graph $G=(V,E)$, a pair of vertices $u$ and $v$ is called a dominating pair if there is a path $P$ between them such that all vertices of $V$ are adjacent to some vertex in $P$. A partition $(X,Y)$ of $V$ is called an edge cut if $u\in X$ and $v\in Y$.

A slight different way to define edge cuts is through the clique path decomposition. It is known that a graph is an interval graph if and only if there is a linear ordering of its $c$ maximal cliques in a way that each vertex appears in a consecutive subset of them. Then an edge cut is defined as a partition $(X,Y)$ where $K_1\setminus K_2\in X$ and $K_c\setminus K_{c-1}\in Y$.

These two definitions are not exactly the same, and may have different minimum cut sizes. But I believe they are related. Also note that it's uninteresting to study the number of minimal edge cuts, as a clique is an interval graph where each partition decides a different minimal edge cut.

EDIT. My question: what's the properties of the minimum edge cuts?

  • 1
    $\begingroup$ What is your question? Is it what (if any) is the relation between these two? And you are asking about the minimum edge cut in both cases? It can be noted that the existence of a dominating path is a property of AT-free graphs, and that interval graphs are exactly the AT-free chordal graphs. $\endgroup$ – Pål GD Jan 12 '13 at 9:45
  • $\begingroup$ What makes the definition of edge cut specific to interval graphs? And how does a dominating pair feature in the definition? $\endgroup$ – András Salamon Jan 13 '13 at 6:36
  • $\begingroup$ @AndrásSalamon He probably want to know the sizes based on (a) that the vertices of the dominating pair need to be on different sides of the cut and (b) that the end points of the clique path decomposition need to be on different sides of the cut. $\endgroup$ – Pål GD Jan 13 '13 at 11:57
  • $\begingroup$ @PålGD Exactly. My conjecture is: (for the second case) there must be an index $\ell$ such that a vertex appearing only left to $K_{\ell}$ is in $X$, and a vertex appearing only right to $K_{\ell}$ is in $Y$. For the first case, other two possibilities are $X=\{u\}$ and $Y=\{v\}$. $\endgroup$ – Yixin Cao Jan 13 '13 at 21:21

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.