T‐joins intersecting small edge‐cuts in graphs |
| |
| Authors: | Tomá? Kaiser Riste ?krekovski |
| |
| Institution: | 1. Email:kaisert@ kma.zcu.cz;4. Department of Mathematics and Institute for, Theoretical Computer Science, University of West Bohemia, Univerzitní 8, 306 14 Plzeň, Czech Republic;5. " href="mailto:skreko@ fmf.uni%E2%80%90lj.si">skreko@ fmf.uni‐lj.si;6. Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia |
| |
| Abstract: | In an earlier paper 3 , we studied cycles in graphs that intersect all edge‐cuts of prescribed sizes. Passing to a more general setting, we examine the existence of T‐joins in grafts that intersect all edge‐cuts whose size is in a given set A ?{1,2,3}. In particular, we characterize all the contraction‐minimal grafts admitting no T‐joins that intersect all edge‐cuts of size 1 and 2. We also show that every 3‐edge‐connected graft admits a T‐join intersecting all 3‐edge‐cuts. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 64–71, 2007 |
| |
| Keywords: | graft T‐join small edge‐cut contraction A‐covering join |
|
|
