Recursively arbitrarily vertex-decomposable graphs

• Autorzy: Baudon O. , Gilbert F. , Woźniak M.
• Języki publikacji: EN

Abstrakty

EN

A graph G = (V, E) is arbitrarily vertex decomposable if for any sequence ϒ of positive integers adding up to/V/, there is a sequence of vertex-disjoint subsets of V whose orders are given by ϒ, and which induce connected graphs. The main aim of this paper is to study the recursive version of this problem. We present a solution for trees, suns, and partially for a class of 2-connected graphs called balloons.

Słowa kluczowe

EN

arbitrary vertex decomposable (AVD) graph; recursively AVD graphs

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2012
• Tom: Vol. 32, no. 4
• Strony: 689--706
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Baudon O.

autor

Gilbert F.

autor

Woźniak M.

• AGH University of Science and Technology Faculty of Applied Mathematics al. Mickiewicza 30, 30-059 Krakow, Poland,

Bibliografia

• [1] D. Barth, O. Baudon, J. Puech, Network sharing: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002), 205–216.
• [2] D. Barth, H. Fournier, A degree bound on decomposable trees, Discrete Math. 306 (2006), 469–477.
• [3] D. Barth, H. Fournier, R. Ravaux, On the shape of decomposable trees, Discrete Math. 309 (2008), 3882–3887.
• [4] O. Baudon, F. Gilbert, M. Wozniak, Recursively arbitrarily vertex-decomposable suns, Opuscula Math. 31 (2011), 533–547.
• [5] D. Duffus, R.J. Gould, M.S. Jacobson, Forbidden Subgraphs and the Hamiltonian Theme, [in:] The Theory and Application of Graphs (Kalamazoo, Mich., 1980), 297–316, Wiley, New York, 1981.
• [6] R. Diestel, Graph Theory, Springer, 2005.
• [7] M. Hornák, Zs. Tuza, M. Wozniak, On-line arbitrarily vertex decomposable trees, Discrete Applied Math. 155 (2007), 1420–1429.
• [8] M. Hornák, M. Wozniak, Arbitrarily vertex decomposable trees are of maximum degree at most six, Opuscula Math. 23 (2003), 49–62.
• [9] R. Kalinowski, M. Pilsniak, M. Wozniak, I. Zioło, Arbitrarily vertex decomposable suns with few rays, Discrete Math. 309 (2009), 3726–3732.
• [10] R. Kalinowski, M. Pilsniak, M. Wozniak, I.A. Zioło, On-line arbitrarily vertex decomposable suns, Discrete Math. 309 (2009), 6328–6336.
• [11] A. Marczyk, An Ore-type condition for arbitrarily vertex decomposable graphs, Discrete Math. 309 (2009), 3588–3594.
• [12] R. Ravaux, Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques, PhD thesis, Université de Versailles Saint-Quentin, 2009.