<p>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.</p>

<p>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 <em>dominating pair</em> 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$.</p>

<p>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$.</p>

<p>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.</p>

<p><strong>EDIT.  My question: what's the properties of the minimum edge cuts?</strong></p>

CC BY-SA 3.0
2013-01-12T09:45:59.667Z
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.
John K.
CC BY-SA 3.0
2013-01-13T06:36:00.260Z
What makes the definition of edge cut specific to interval graphs?  And how does a dominating pair feature in the definition?
András Salamon
CC BY-SA 3.0
2013-01-13T11:57:02.250Z
@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.
John K.
CC BY-SA 3.0
2013-01-13T21:21:05.893Z
@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\}$.
Yixin Cao
<reference-request><max-flow-min-cut><graph-classes>
Edge Cut of interval graphs
Yixin Cao
# Edge Cut of interval graphs

(Asked by: username_0 on 2013-01-12)

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?**

**Tags:** reference-request, max-flow-min-cut, graph-classes

> **Comments:**
> **username_1**: 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.  
> **username_2**: What makes the definition of edge cut specific to interval graphs?  And how does a dominating pair feature in the definition?  
> **username_1**: @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.  
> **username_0**: @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\}$.  

---

## 0 answers

