Please use this identifier to cite or link to this item:

`http://repositorio.unicamp.br/jspui/handle/REPOSIP/70884`

Type: | Artigo |

Title: | Removable paths and cycles with parity constraints |

Author: | Kawarabayashi, Ken-ichi Lee, Orlando Reed, Bruce |

Abstract: | We consider the following problem. For every positive integer k there is a smallest integer f(k) such that for any two vertices s and t in a non-bipartite f(k)-connected graph G, there is an s-t path P in G with specified parity such that G - V(P) is k-connected. This conjecture is a variant of the well-known conjecture of Lovasz with the parity condition. Indeed, this conjecture is strictly stronger. Lovasz' conjecture is wide open for k >= 3. In this paper, we show that f(1) = 5 and 6 <= f(2) <= 8. We also consider a conjecture of Thomassen which says that there exists a function f(k) such that every f(k)-connected graph with an odd cycle contains an odd cycle C such that G - V(C) is k-connected. We show the following strengthening of Thomassen's conjecture for the case k = 2. Namely; let G be a 5-connected graph and s be a vertex in G such that G - s is not bipartite. Then there is an odd cycle C avoiding s such that G - V(C) is 2-connected. (C) 2014 Elsevier Inc. All rights reserved. We consider the following problem. For every positive integer k there is a smallest integer f(k) such that for any two vertices s and t in a non-bipartite f(k)-connected graph G, there is an s-t path P in G with specified parity such that G - V(P) is k-co |

Subject: | Teoria dos grafos Árvores (Teoria dos grafos) Conectividade em grafos |

Country: | Estados Unidos |

Editor: | Academic Press |

Citation: | Journal Of Combinatorial Theory Series B. Academic Press Inc Elsevier Science, v. 106, n. 115, n. 133, 2014. |

Rights: | Aberto |

Identifier DOI: | 10.1016/j.jctb.2014.01.005 |

Address: | https://www.sciencedirect.com/science/article/pii/S0095895614000069 |

Date Issue: | 2014 |

Appears in Collections: | IC - Artigos e Outros Documentos |

Files in This Item:

File | Size | Format | |
---|---|---|---|

000335427100006.pdf | 393.13 kB | Adobe PDF | View/Open |

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.