World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

5-Shredders of Contraction-Critical 5-Connected Graphs

    This article is part of the issue:

    Yoshimi Egawa [8] showed that a 5-connected graph G admits at most 2|V(G)|103 5-shredders. In this paper we shown that a contraction-critical 5-connected graph G admits at most |G|62 5-shredders. Further we show that, for every contraction-critical 5-connected graph G, there is a contraction critical 5-connected graph G̃ such that G is a spanning subgraph of G̃ and G̃ admits at most |G|14 5-shredders.

    References

    • 1. J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (MacMillan, 1976). CrossrefGoogle Scholar
    • 2. J. Cheriyan and R. Thurimella, Fast algorithms for k-shredders and k-node connectivity augmentation, in Proc. 28th Ann. ACM STOC, 1996, pp. 37–46. Google Scholar
    • 3. D. Naor, D. Gasfield and C. Martel, 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. T. S. Hsu and V. Ramachandran, 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. T. S. Hsu, On four-connecting a triconnected graph, in Proc. 33th Annual IEEE Symp. on Foundations of Comput. Sci., 1992, pp. 70–79. CrossrefGoogle Scholar
    • 6. T. S. Hsu, Finding a smallest augmentation to biconnect a graph, SIAM J. Comput. 22(5) (1993) 889–912. Crossref, ISIGoogle Scholar
    • 7. Y. Egawa, Y. Okadome and M. Takatou, 5-shredders in 5-connected graphs, Discrete Mathematics 309(6) (2009) 1565–1754. Crossref, ISIGoogle Scholar
    • 8. Y. Egawa, k-shredders in k-connected graphs, J. Graph Theory 59(3) (2008) 239–259. Crossref, ISIGoogle Scholar
    • 9. T. Jordán, On the number of shredders, J. Graph Theory 31 (1999) 195–200. Crossref, ISIGoogle Scholar
    • 10. N. Martinov, A recursive characterization of the 4-connected graphs, Discrete Mathematics 84 (1990) 105–108. Crossref, ISIGoogle Scholar
    • 11. J. J. Su, Vertices of degree 5 in contraction critical 5-connected graphs, J. Guangxi Normal University 3 (1997) 12–16 (in Chinese). Google Scholar
    • 12. C. F. Qin, X. D. Yuan and J. J. Su, Some properties of contraction critical 5-connected graphs, Discrete Mathematics 308 (2008) 5742–5756. Crossref, ISIGoogle Scholar
    • 13. K. Ando, Small components of the 5-subgraph of a contraction-critically 5-connected graph, Graphs and Combinatorics 33(6) (2017) 1485–1497. Crossref, ISIGoogle Scholar
    • 14. K. Ando and C. F. Qin, Some structural properties of minimally contraction-critically 5-connected graphs, Discrete Mathematics 311(13) (2011) 1084–1097. Crossref, ISIGoogle Scholar
    • 15. M. Kriesell, Triangle density and contractibility, Combinatorics Probability, Computing 14(1–2) (2005) 133–146. Crossref, ISIGoogle Scholar
    • 16. M. Kriesell, A survey on contractible edges in graphs of a given vertex connectivity, Graphs and Combinatorics 18 (2002) 1–30. Crossref, ISIGoogle Scholar
    • 17. M. Kriesell, Average degree and contractibility, J. Graph Theorey 51 (2005) 205–224. Crossref, ISIGoogle Scholar
    • 18. W. Mader, Generalizations of critical connectivity of graphs, Discrete Mathematics 72 (1988) 267–283. Crossref, ISIGoogle Scholar
    • 19. M. Kriesell, 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, ISIGoogle Scholar
    • 20. H. Hanani, The existence and construction of balanced incomplete block designs, Ann. Math. Statist. 32 (1961) 361–386. CrossrefGoogle Scholar
    • 21. H. Hanani, A balanced incomplete block designs, Ann. Math. Statist. 36 (1965) 711. CrossrefGoogle Scholar