×

Partitioning a graph into highly connected subgraphs. (English) Zbl 1342.05110

Summary: Given \(k\geq 1\), a \(k\)-proper partition of a graph \(G\) is a partition \(\mathcal P\) of \(V(G)\) such that each part \(P\) of \(\mathcal P\) induces a \(k\)-connected subgraph of \(G\). We prove that if \(G\) is a graph of order \(n\) such that \(\delta(G)\geq \sqrt{n}\), then \(G\) has a 2-proper partition with at most \(n/\delta(G)\) parts. The bounds on the number of parts and the minimum degree are both best possible. We then prove that if \(G\) is a graph of order \(n\) with minimum degree \(\delta(G)\geq \sqrt{c(k-1)n}\), where \(c=\frac{2123}{180}\), then \(G\) has a \(k\)-proper partition into at most \(\frac{cn}{\delta(G)}\) parts. This improves a result of M. Ferrara et al. [Discrete Math. 313, No. 6, 760–764 (2013; Zbl 1260.05086)], and both the degree condition and the number of parts is best possible up to the constant \(c\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C40 Connectivity

Citations:

Zbl 1260.05086
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. Akiyama M. Kano Factors and Factorizations of Graphs: Proof Techniques in Factor Theory 2011 · Zbl 1229.05001
[2] Alon, What is the furthest graph from a hereditary property, Random Struct Algor 33 pp 87– (2008) · Zbl 1146.05046 · doi:10.1002/rsa.20209
[3] Axenovich, On the editing distance of graphs, J Graph Theory 58 pp 123– (2008) · Zbl 1156.05027 · doi:10.1002/jgt.20296
[4] Bollobás, Modern Graph Theory pp xiii– (1998) · doi:10.1007/978-1-4612-0619-4
[5] Ferrara, Conditions for families of disjoint k-connected subgraphs in a graph, Discrete Math 313 pp 760– (2013) · Zbl 1260.05086 · doi:10.1016/j.disc.2012.12.013
[6] Gould, Updating the Hamiltonian problem-A survey, J Graph Theory 15 pp 122– (1991) · Zbl 0746.05039 · doi:10.1002/jgt.3190150204
[7] Gould, Advances on the Hamiltonian problem-A survey, Graphs Comb 19 pp 7– (2003) · Zbl 1024.05057 · doi:10.1007/s00373-002-0492-x
[8] R. Gould Recent advances on the Hamiltonian problem: Survey III 30 2014 1 46 · Zbl 1292.05163
[9] Gould, A look at cycles containing specified elements of a graph, Discrete Math 309 pp 6299– (2009) · Zbl 1229.05169 · doi:10.1016/j.disc.2008.04.017
[10] Hajnal, Partition of graphs with condition on the connectivity and minimum degree, Combinatorica 3 pp 95– (1983) · Zbl 0529.05030 · doi:10.1007/BF02579344
[11] Hartuv, A clustering algorithm based on graph connectivity, Inform Process Lett 76 pp 175– (2000) · Zbl 0996.68525 · doi:10.1016/S0020-0190(00)00142-3
[12] Mader, Surveys in Combinatorics (1979)
[13] Nikiforov, Making the components of a graph k-connected, Discrete Appl Math 155 (3) pp 410– (2007) · Zbl 1117.05059 · doi:10.1016/j.dam.2006.07.007
[14] Ore, A note on Hamilton circuits, Amer Math Monthly 67 pp 55– (1960) · Zbl 0089.39505 · doi:10.2307/2308928
[15] Plummer, Graph factors and factorization: 1985-2003: A survey, Discrete Math 307 pp 791– (2007) · Zbl 1112.05088 · doi:10.1016/j.disc.2005.11.059
[16] D. C. Richer PhD thesis 2000
[17] Thomassen, Graph decomposition with constraints on the connectivity and minimum degree, J Graph Theory 7 pp 165– (1983) · Zbl 0515.05045 · doi:10.1002/jgt.3190070204
[18] Yuster, A note on graphs without k-connected subgraphs, Ars Combin 67 pp 231– (2003) · Zbl 1078.05054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.