Abstract
A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n 1, . . . , n k ) of positive integers such that n 1 + · · · + n k = n there exists a partition (V 1, . . . , V k ) of the vertex set of G such that for each \({i \in \{1,\ldots,k\}}\) , V i induces a connected subgraph of G on n i vertices. The main result of the paper reads as follows. Suppose that G is a connected graph on n ≥ 20 vertices that admits a perfect matching or a matching omitting exactly one vertex. If the degree sum of any pair of nonadjacent vertices is at least n − 5, then G is arbitrarily vertex decomposable. We also describe 2-connected arbitrarily vertex decomposable graphs that satisfy a similar degree sum condition.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barth D., Baudon O., Puech J.: Network sharing: a polynomial algorithm for tripods. Discrete Appl. Math. 119, 205–216 (2002)
Barth D., Fournier H.: A degree bound on decomposable trees. Discrete Math. 306, 469–477 (2006)
Bermond, J.C.: On Hamiltonian walks. In: Nash-Wiliams, C.St.J.A., Sheehan, J. (eds.) Proc. Fifth British Combinatorial Conference, Utilitas Math., pp. 41–51 Winnipeg, (1976)
Bondy JA., Murty USR.: Graph Theory with Applications. Elsevier North Holland, New York (1976)
Cichacz S., Görlich A., Marczyk A., Przybyło J., Woźniak M.: Arbitrarily vertex decomposable caterpillars with four or five leaves. Discuss. Math. Graph Theory 26, 291–305 (2006)
Győri, E.: On division of graphs to connected subgraphs. In: Combinatorics. Proc. Fifth Hungarian Colloq., Keszthely, 1976, vol. I, pp. 485–494, Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam, New York (1978)
Horňák M., Wo\'zniak M.: On arbitrarily vertex decomposable trees. Discrete Math. {\bf 308caron;, 1268–1281 (2008)
Horňák M., Wo\'zniak M.: Arbitrarily vertex decomposable trees are of maximum degree at most six. Opuscula Mathematica {\bf 23caron;, 49–62 (2003)
Horňák M., Tuza Zs., Woźniak M.: On-line arbitrarily vertex decomposable trees. Discrete Appl. Math. 155, 1420–1429 (2007)
Kalinowski R., Pilśniak M., Woźniak M., Zioło I.: Arbitrarily vertex decomposable suns with few rays. Discrete Math. 309, 3726–3732 (2009)
Kalinowski R., Pilśniak M., Woźniak M., Zioło I.: On-line arbitrarily vertex decomposable suns. Discrete Math. 309, 6328–6336 (2009)
Linial N.: A lower bound for the circumference of a graph. Discrete Math. 15, 297–300 (1976)
Lovász L.: A homology theory for spanning trees of a graph. Acta Math. Acad. Sci. Hungar. 30, 241–251 (1977)
Marczyk A.: A note on arbitrarily vertex decomposable graphs. Opuscula Math. 26, 109–118 (2006)
Marczyk A.: An Ore-type condition for arbitrarily vertex decomposable graphs. Discrete Math. 309, 3588–3594 (2009)
Ore O.: Note on hamilton circuits. Am. Math. Monthly 67, 55 (1960)
Pósa L.: A theorem concerning Hamiltonian lines. Publ. Math. Inst. Hungar. Acad. Sci. 7, 225–226 (1962)
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of M. Horňák was supported by Science and Technology Assistance Agency under the contract No. APVT-20-004104 and by Grant VEGA 1/3004/06.
Research financially supported in parts by DAAD contracts TU Freiberg-AGH Krakau and TU Freiberg-UPJŠ Košice.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Horňák, M., Marczyk, A., Schiermeyer, I. et al. Dense Arbitrarily Vertex Decomposable Graphs. Graphs and Combinatorics 28, 807–821 (2012). https://doi.org/10.1007/s00373-011-1077-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-011-1077-3