5-Shredders of Contraction-Critical 5-Connected Graphs
Abstract
Yoshimi Egawa [8] showed that a 5-connected graph G admits at most 5-shredders. In this paper we shown that a contraction-critical 5-connected graph G admits at most 5-shredders. Further we show that, for every contraction-critical 5-connected graph G, there is a contraction critical 5-connected graph such that G is a spanning subgraph of and admits at most 5-shredders.
References
- 1. , Graph Theory with Applications (MacMillan, 1976). Crossref, Google Scholar
- 2. , Fast algorithms for k-shredders and k-node connectivity augmentation, in Proc. 28th Ann. ACM STOC,
1996 , pp. 37–46. Google Scholar - 3. , A fast algorithm for optimally increasing the edge-connectivity, in Proc. 31th Annual IEEE Symp. on Foundations of Comput. Sci.,
1990 , pp. 698–707. Google Scholar - 4. , A linear time algorithm for triconnectivity augmentation, in Proc. 32th Annual IEEE Symp. on Foundations of Comput. Sci.,
1991 , pp. 548–559. Google Scholar - 5. , On four-connecting a triconnected graph, in Proc. 33th Annual IEEE Symp. on Foundations of Comput. Sci.,
1992 , pp. 70–79. Crossref, Google Scholar - 6. , Finding a smallest augmentation to biconnect a graph, SIAM J. Comput. 22(5) (1993) 889–912. Crossref, ISI, Google Scholar
- 7. , 5-shredders in 5-connected graphs, Discrete Mathematics 309(6) (2009) 1565–1754. Crossref, ISI, Google Scholar
- 8. , k-shredders in k-connected graphs, J. Graph Theory 59(3) (2008) 239–259. Crossref, ISI, Google Scholar
- 9. , On the number of shredders, J. Graph Theory 31 (1999) 195–200. Crossref, ISI, Google Scholar
- 10. , A recursive characterization of the 4-connected graphs, Discrete Mathematics 84 (1990) 105–108. Crossref, ISI, Google Scholar
- 11. , Vertices of degree 5 in contraction critical 5-connected graphs, J. Guangxi Normal University 3 (1997) 12–16 (in Chinese). Google Scholar
- 12. , Some properties of contraction critical 5-connected graphs, Discrete Mathematics 308 (2008) 5742–5756. Crossref, ISI, Google Scholar
- 13. , Small components of the 5-subgraph of a contraction-critically 5-connected graph, Graphs and Combinatorics 33(6) (2017) 1485–1497. Crossref, ISI, Google Scholar
- 14. , Some structural properties of minimally contraction-critically 5-connected graphs, Discrete Mathematics 311(13) (2011) 1084–1097. Crossref, ISI, Google Scholar
- 15. , Triangle density and contractibility, Combinatorics Probability, Computing 14(1–2) (2005) 133–146. Crossref, ISI, Google Scholar
- 16. , A survey on contractible edges in graphs of a given vertex connectivity, Graphs and Combinatorics 18 (2002) 1–30. Crossref, ISI, Google Scholar
- 17. , Average degree and contractibility, J. Graph Theorey 51 (2005) 205–224. Crossref, ISI, Google Scholar
- 18. , Generalizations of critical connectivity of graphs, Discrete Mathematics 72 (1988) 267–283. Crossref, ISI, Google Scholar
- 19. , A degree sum condition for the existence of a contractible edge in a -connected graph, J. Combin. Theory, Ser. B 82 (2001) 81–101. Crossref, ISI, Google Scholar
- 20. , The existence and construction of balanced incomplete block designs, Ann. Math. Statist. 32 (1961) 361–386. Crossref, Google Scholar
- 21. , A balanced incomplete block designs, Ann. Math. Statist. 36 (1965) 711. Crossref, Google Scholar


