Premium
3‐connected graphs with non‐cut contractible edge covers of size k
Author(s) -
Yu Xingxing
Publication year - 1994
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.3190180410
Subject(s) - contractible space , combinatorics , mathematics , vertex (graph theory) , graph , cardinality (data modeling) , enhanced data rates for gsm evolution , vertex connectivity , discrete mathematics , connectivity , computer science , telecommunications , data mining
In this paper, we show that if a 3‐connected graph G other than K 4 has a vertex subset K that covers the set of contractible edges of G and if | K | 3 and | V(G) | 3| K | − 1, then K is a cutset of G . We also give examples to show that this result is best possible. In particular, the result does not hold for K with smaller cardinality.
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