Dense Arbitrarily Partitionable Graphs

Rafał Kalinowski ; Monika Pilśniak ; Ingo Schiermeyer ; Mariusz Woźniak

Discussiones Mathematicae Graph Theory, Tome 36 (2016), p. 5-22 / Harvested from The Polish Digital Mathematics Library

Résumé

A graph G of order n is called arbitrarily partitionable (AP for short) if, for every sequence (n1, . . . , nk) of positive integers with n1 + ⋯ + nk = n, there exists a partition (V1, . . . , Vk) of the vertex set V (G) such that Vi induces a connected subgraph of order ni for i = 1, . . . , k. In this paper we show that every connected graph G of order n ≥ 22 and with [...] ‖G‖ > (n−42)+12 $||G||\; > \;\left( {{{n - 4} \cr 2 \cr } } \right) + 12$ edges is AP or belongs to few classes of exceptional graphs.

Détail

Publié le : 2016-01-01

Zbl 1329.05163

EUDML-ID : urn:eudml:doc:276974

Bibliographie

[1] D. Barth, O. Baudon and J. Puech, Network sharing: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002) 205–216. doi:10.1016/S0166-218X(00)00322-X[Crossref] | Zbl 1002.68107

[2] O. Baudon, J. Bensmail, R. Kalinowski, A. Marczyk, J. Przybyło and M. Woźniak, On the Cartesian product of an arbitrarily partitionable graph and a traceable graph, Discrete Math. Theor. Comput. Sci. 16 (2014) 225–232. | Zbl 1288.05212

[3] O. Baudon, J. Bensmail, J. Przybyło and M. Woźniak, Partitioning powers of traceable or Hamiltonian graphs, Theoret. Comput. Sci. 520 (2014) 133–137. doi:10.1016/j.tcs.2013.10.016[Crossref] | Zbl 1305.05185

[4] O. Baudon, F. Foucaud, J. Przybyło and M. Woźniak, On the structure of arbitrarily partitionable graphs with given connectivity, Discrete Appl. Math. 162 (2014) 381–385. doi:10.1016/j.dam.2013.09.007[Crossref][WoS] | Zbl 1300.05245

[5] O. Baudon, F. Gilbert and M. Woźniak, Recursively arbitrarily vertex decomposable graphs, Opuscula Math. 32 (2012) 689–706. doi:10.7494/OpMath.2012.32.4.689[Crossref] | Zbl 1259.05135

[6] O. Baudon, F. Gilbert and M. Woźniak, Recursively arbitrarily vertex decomposable suns, Opuscula Math. 31 (2011) 533–547. doi:10.7494/OpMath.2011.31.4.533[Crossref] | Zbl 1234.05182

[7] O. Baudon, J. Przybyło and M. Woźniak, On minimal arbitrarily partitionable graphs, Inform. Process. Lett. 112 (2012) 697–700. doi:10.1016/j.ipl.2012.06.010[Crossref] | Zbl 1248.05152

[8] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[9] H.J. Broersma, D. Kratsch and G.J. Woeginger, Fully decomposable split graphs, Lecture Notes in Comput. Sci. 5874 (2009) 4105–4112. doi:10.1007/978-3-642-10217-2_13[Crossref] | Zbl 1267.05245

[10] P. Erdős, Remarks on a paper of Pósa, Magyar Tud. Akad. Mat. Kutató Int. Kőzl. 7 (1962) 227–229. | Zbl 0114.40004

[11] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337–356. doi:10.1007/BF02024498[Crossref] | Zbl 0090.39401

[12] M. Horňák, A. Marczyk, I. Schiermeyer and M. Woźniak, Dense arbitrarily vertex decomposable graphs, Graphs Combin. 28 (2012) 807–821. doi:10.1007/s00373-011-1077-3[Crossref] | Zbl 1256.05136

[13] M. Horňák and M. Woźniak, Arbitrarily vertex decomposable trees are of maximum degree at most six, Opuscula Math. 23 (2003) 49–62. | Zbl 1093.05510

[14] M. Horňák, Zs. Tuza and M. Woźniak, On-line arbitrarily vertex decomposable trees, Discrete Appl. Math. 155 (2007) 1420–1429. doi:10.1016/j.dam.2007.02.011[WoS][Crossref]

[15] R. Kalinowski, M. Pilśniak, M. Woźniak and I.A. Zioło, Arbitrarily vertex decomposable suns with few rays, Discrete Math. 309 (2009) 3726–3732. doi:10.1016/j.disc.2008.02.019[WoS][Crossref] | Zbl 1214.05125

[16] R. Kalinowski, M. Pilśniak, M. Woźniak and I.A. Zioło, On-line arbitrarily vertex decomposable suns, Discrete Math. 309 (2009) 6328–6336. doi:10.1016/j.disc.2008.11.025[WoS][Crossref] | Zbl 1218.05138

[17] A. Kemnitz and I. Schiermeyer, Improved degree conditions for Hamiltonian properties, Discrete Math. 312 (2012) 2140–2145. doi:10.1016/j.disc.2011.07.013[WoS][Crossref] | Zbl 1244.05136

[18] A. Marczyk, A note on arbitrarily vertex decomposable graphs, Opuscula Math. 26 (2006) 109–118. | Zbl 1134.05083

[19] A. Marczyk, An Ore-type condition for arbitrarily vertex decomposable graphs, Discrete Math. 309 (2009) 3588–3594. doi:10.1016/j.disc.2007.12.066[Crossref][WoS] | Zbl 1179.05089

[20] D.R. Woodall, Maximal circuits of graphs I, Acta Math. Acad. Sci. Hungar. 28 (1976) 77–80. doi:10.1007/BF01902497[Crossref] | Zbl 0337.05128