Dense Arbitrarily Partitionable Graphs

• Autorzy: Rafał Kalinowski , Monika Pilśniak , Ingo Schiermeyer , Mariusz Woźniak
• Języki publikacji: EN

Abstrakty

EN

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( {\matrix{{n - 4} \cr 2 \cr } } \right) + 12$ edges is AP or belongs to few classes of exceptional graphs.

Słowa kluczowe

EN

arbitrarily partitionable graph; Erdös-Gallai condition; traceable graph; perfect matching

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing
• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 1
• Strony: 5-22

Daty

wydano

2016-02-01

otrzymano

2015-01-19

poprawiono

2015-03-18

zaakceptowano

2015-03-18

online

2016-01-19

Twórcy

autor

Rafał Kalinowski

• AGH University of Science and Technology Kraków, Poland

autor

Monika Pilśniak

• AGH University of Science and Technology Kraków, Poland

autor

Ingo Schiermeyer

• AGH University of Science and Technology Kraków, Poland
• TU Bergakademie Freiberg, Freiberg, Germany

autor

Mariusz Woźniak

• AGH University of Science and Technology Kraków, Poland

Bibliografia

• [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]
• [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.
• [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]
• [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]
• [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]
• [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]
• [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]
• [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]
• [10] P. Erdős, Remarks on a paper of Pósa, Magyar Tud. Akad. Mat. Kutató Int. Kőzl. 7 (1962) 227–229.
• [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]
• [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]
• [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.
• [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]
• [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]
• [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]
• [18] A. Marczyk, A note on arbitrarily vertex decomposable graphs, Opuscula Math. 26 (2006) 109–118.
• [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]
• [20] D.R. Woodall, Maximal circuits of graphs I, Acta Math. Acad. Sci. Hungar. 28 (1976) 77–80. doi:10.1007/BF01902497[Crossref]

Identyfikatory

DOI

10.7151/dmgt.1833