Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Pål GD Jan 12 '13 at 9:45
    
What makes the definition of edge cut specific to interval graphs? And how does a dominating pair feature in the definition? –  András Salamon Jan 13 '13 at 6:36
    
@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. –  Pål GD Jan 13 '13 at 11:57
    
@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 Jan 13 '13 at 21:21
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.