Minimally connected graphs

Nicolas Trotignon

Description

Niveau: Supérieur
Decomposition Connectivity Minimally 2-connected graphs Critically 2-connected graphs Open questions Decomposition theorems for classes of graphs defined by constraints on connectivity Nicolas Trotignon — CNRS — LIAFA Universite Paris 7 Danish Graph Theory Meeting April – May 2011

• connected graphs


• danish graph


• links between


• decomposition connectivity


• universite de paris


• theory meeting


• every subgraph


• open question

Sujets

• Université de Paris
• Open problem

Informations

• Publié par: chaeh
• Nombre de lectures: 16
• Langue: English

Extrait

Decomposition Connceitivyt iMinamy 2 ll on-cctne gr ed shpa tirClaci -2 yl ecteconn phs O d gra euts ep q n oisn

Danish Graph Theory Meeting April – May 2011

Decomposition theorems for classes of graphs defined by constraints on connectivity

Nicolas Trotignon — CNRS — LIAFA Universite´Paris7

eDpmoctiso C noi layl -2ocnnceet g d onnectivity Minim tcennoc- shparg de ri s C phra y 2 llcati ques Open stion

Outline

Minimally 2-connected graphs

1

2

Critically 2-connected graphs

Open questions

3

gr edctne enOp hsap noitseuqs nnec2-co raph ted g itacC s ir c-no ll 2 y csihpargAycerevifsslerdhoroldse.scyelsihc

Definitions

A graph isminimally 2-connectedif it is 2-connected and the removal of any edge yields a graph that is not 2-connected.

De allyinim ity M ctivnoen oi C nsotiocpm

eDpmoc neonivct itosn C io pash de rg uqse pOne lly 2 tica nect-con g detcenn irC shpar imin y M it co2- lyal ontis

A graph isminimally 2-connectedif it is 2-connected and the removal of any edge yields a graph that is not 2-connected.

A graph ischordlessif every cycle is chordless.

Definitions

phs O d gra ecteconn iLkn oisneuts ep q n lerdho“cenweetsbyllaminim“dna”ss sition Co Decompo yt iMinam nnceitiv ctne gr ed y 2 ll on-c laci -2 yl shpa tirC -2ocnnceet”d

Plummer’s observations [1968]:

A graphGis chordless if and only if for every subgraphH, eitherHhas connectivity at most 1, orHis minimally 2-connected. A 2-connected graph is chordless if and only if it is minimally 2-connected.

G

has

basic

or

G

is

Theorem(L´evˆeque,Maffray,NT2009)

Let G be a chordless graph. Then either decomposition.

a

Decomposing chordless graphs

ue n q pe s O nsiost cennoc-2 hparg det nnCotiectyvi niMi Dmoceisopnoit graphs Critically amll 2 y c-noentcde