Premium
T ‐joins intersecting small edge‐cuts in graphs
Author(s) -
Kaiser Tomáš,
Škrekovski Riste
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20246
Subject(s) - joins , combinatorics , mathematics , enhanced data rates for gsm evolution , graph , discrete mathematics , computer science , artificial intelligence , programming language
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom