Let P = {P1,..., Pl} be a set of internally disjoint paths contained in a graph G, and let S be the subgraph defined by ∪ti=1 Pi. A P-bridge is either an edge of G - E(S) with both endpoints in V(S) or a component C of G - V(S) along with all the edges from V(C) to V(S). The attachments of a bridge B are the vertices of V(B) ∪ V(S). A bridge B is k-stable if there does not exist a subset of at most k - 1 paths in P containing every attachment of B. A classic theorem of Tutte [Graph Theory, Addison-Wesley, Menlo Park, CA, 1984] states that if G is a 3-connected graph, there exists a set of internally disjoint paths P′ = {P′1{,..., P′l} such that Pi and P′i have the same endpoints for 1 ≤ i ≤ t and every P′-bridge is 2-stable. We prove that if the graph is sufficiently connected, the paths P′1,..., P′l may be chosen so that every bridge containing at least two edges is, in fact, k-stable. We also give several simple applications of this theorem related to a conjecture of Lovász [Problems in Graph Theory, Recent Advances in Graph Theory, M. Felder, ed., Acadamia, Prague, 1975] on deleting paths while maintaining high connectivity. © 2010 Society for Industrial and Applied Mathematics.

Bridges in highly connected graphs / Wollan, PAUL JOSEPH. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - 24:4(2010), pp. 1731-1741. [10.1137/070710214]

Bridges in highly connected graphs

WOLLAN, PAUL JOSEPH
2010

Abstract

Let P = {P1,..., Pl} be a set of internally disjoint paths contained in a graph G, and let S be the subgraph defined by ∪ti=1 Pi. A P-bridge is either an edge of G - E(S) with both endpoints in V(S) or a component C of G - V(S) along with all the edges from V(C) to V(S). The attachments of a bridge B are the vertices of V(B) ∪ V(S). A bridge B is k-stable if there does not exist a subset of at most k - 1 paths in P containing every attachment of B. A classic theorem of Tutte [Graph Theory, Addison-Wesley, Menlo Park, CA, 1984] states that if G is a 3-connected graph, there exists a set of internally disjoint paths P′ = {P′1{,..., P′l} such that Pi and P′i have the same endpoints for 1 ≤ i ≤ t and every P′-bridge is 2-stable. We prove that if the graph is sufficiently connected, the paths P′1,..., P′l may be chosen so that every bridge containing at least two edges is, in fact, k-stable. We also give several simple applications of this theorem related to a conjecture of Lovász [Problems in Graph Theory, Recent Advances in Graph Theory, M. Felder, ed., Acadamia, Prague, 1975] on deleting paths while maintaining high connectivity. © 2010 Society for Industrial and Applied Mathematics.
2010
bridges; connectivity; graph; nonseparating cycles
01 Pubblicazione su rivista::01a Articolo in rivista
Bridges in highly connected graphs / Wollan, PAUL JOSEPH. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - 24:4(2010), pp. 1731-1741. [10.1137/070710214]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/443288
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact