Dense Arbitrarily Partitionable Graphs

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

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 1, page 5-22
  • ISSN: 2083-5892

Abstract

top
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 | | > n - 4 2 + 12 edges is AP or belongs to few classes of exceptional graphs.

How to cite

top

Rafał Kalinowski, et al. "Dense Arbitrarily Partitionable Graphs." Discussiones Mathematicae Graph Theory 36.1 (2016): 5-22. <http://eudml.org/doc/276974>.

@article{RafałKalinowski2016,
abstract = {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.},
author = {Rafał Kalinowski, Monika Pilśniak, Ingo Schiermeyer, Mariusz Woźniak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {arbitrarily partitionable graph; Erdös-Gallai condition; traceable graph; perfect matching; Erdős-Gallai condition},
language = {eng},
number = {1},
pages = {5-22},
title = {Dense Arbitrarily Partitionable Graphs},
url = {http://eudml.org/doc/276974},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Rafał Kalinowski
AU - Monika Pilśniak
AU - Ingo Schiermeyer
AU - Mariusz Woźniak
TI - Dense Arbitrarily Partitionable Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 5
EP - 22
AB - 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.
LA - eng
KW - arbitrarily partitionable graph; Erdös-Gallai condition; traceable graph; perfect matching; Erdős-Gallai condition
UR - http://eudml.org/doc/276974
ER -

References

top
  1. [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] Zbl1002.68107
  2. [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. Zbl1288.05212
  3. [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] Zbl1305.05185
  4. [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] Zbl1300.05245
  5. [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] Zbl1259.05135
  6. [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] Zbl1234.05182
  7. [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] Zbl1248.05152
  8. [8] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008). 
  9. [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] Zbl1267.05245
  10. [10] P. Erdős, Remarks on a paper of Pósa, Magyar Tud. Akad. Mat. Kutató Int. Kőzl. 7 (1962) 227–229. Zbl0114.40004
  11. [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] Zbl0090.39401
  12. [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] Zbl1256.05136
  13. [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. Zbl1093.05510
  14. [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. [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] Zbl1214.05125
  16. [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] Zbl1218.05138
  17. [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] Zbl1244.05136
  18. [18] A. Marczyk, A note on arbitrarily vertex decomposable graphs, Opuscula Math. 26 (2006) 109–118. Zbl1134.05083
  19. [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] Zbl1179.05089
  20. [20] D.R. Woodall, Maximal circuits of graphs I, Acta Math. Acad. Sci. Hungar. 28 (1976) 77–80. doi:10.1007/BF01902497[Crossref] Zbl0337.05128

NotesEmbed ?

top

You must be logged in to post comments.