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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.