Minimally connected graphs
66
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
66
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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
Voir
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
Danish Graph Theory Meeting April – May 2011
Decomposition theorems for classes of graphs defined by constraints on connectivity
Nicolas Trotignon — CNRS — LIAFA Universite´Paris7
Outline
Minimally 2-connected graphs
1
2
Critically 2-connected graphs
Open questions
3
Definitions
A graph isminimally 2-connectedif it is 2-connected and the removal of any edge yields a graph that is not 2-connected.
DeallyinimityMctivnoenoiCnsotiocpm
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
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
uenqpesOnsiostcennoc-2hpargdetnnCotiectyviniMiDmoceisopnoitgraphsCriticallyamll2yc-noentcde
