# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 23.04.2009 at 12:20 in S6, there is the following noon lecture:

# The Disconnected Cut problem

## Daniel Paulusma

## University of Durham

## Abstract

Let G=(V,E) be a finite connected undirected graph without multiple edges or self-loops. Let G[U] denote the subgraph induced by a subset U of V. Then U is a cut if G[V\U] is disconnected. We call a cut U a disconnected cut if G[U] is disconnected as well. This leads to the following decision problem

DISCONNECTED CUT Instance: A graph G Question: Does G have a disconnected cut?

As far as we know the computational complexity of this problem is open. We pinpoint relationships with other graph-theoretic concepts such as graph homomorphisms and graph contractions, discuss partial results and mention other related open (sub)problems.

Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010