A note of arbitrarily vertex decomposable graphs

• Autorzy: Marczyk A.
• Języki publikacji: EN

Abstrakty

EN

A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n1,..., nk) of positive integers such that n1 + ... + nk = n there exists a partition (V1,..., Vk) of the vertex set of G such that for each i ∈ {1,..., k}, Vi induces a connected subgraph of G on ni vertices. In this paper we show that if G is a two-connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n - 3, then G is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition, where the bound n - 3 is replaced by n - 2.

Słowa kluczowe

EN

arbitrarily vertex decomposable graphs; traceable graphs; independence number; perfect matching

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2006
• Tom: Vol. 26, no. 1
• Strony: 109--118
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Marczyk A.

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

Bibliografia

• [1] Barth D., Baudon O., Puech J., Network sharing: a polynomial algorithm for tripods, Discrete Applied Mathematics 119 (2002), 205-216.
• [2] Barth D., Fournier H., A degree bound on decomposable trees, Discrete Math. 306 (2006), 469-477.
• [3] Bermond, J. C, On Hamiltonian walks, in: Proc. Fifth British Combinatorial Conference, eds. C.St.J.A. Nash-Wiliams and J. Sheehan, Utilitas Math., Winnipeg, 1976 41-51.
• [4] Cichacz S., Gorlich A., Marczyk A., Przybyło J., Woźniak M., Arbitrarily vertex decomposable caterpillars with four or five leaves, Discuss. Math. Graph Theory 26 (2006), 291-305.
• [5] Gyori E., On division of graphs to connected subgraphs, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, pp. 485-494, Colloq. Math. Soc. Janos Bolyai, 18, North-Holland, Amsterdam-New York, 1978.
• [6] Hornak M., Tuza Z., Woźniak M., On-line arbitrarily vertex decomposable trees, preprint (2005).
• [7] Hornak M., Woźniak M., On arbitrarily vertex decomposable trees, Preprint MD 005 (2004), http://www.ii.uj.edu.pl/preMD/index.htm.
• [8] Hornak M., Woźniak M., Arbitrarily vertex decomposable trees are of maximum degree at most six, Opuscula Mathematica 23 (2003), 49-62.
• [9] Kalinowski R., Pilśniak M., Woźniak M., Zioło I., Arbitrarily vertex decomposable suns with few rays, Preprint MD 015 (2005), http://www.ii.uj.edu.pl /PreMD/index.htm.
• [10] Linial N., A lower bound for the circumference of a graph, Discrete Math. 15 (1976), 297-300.
• [11] Lovasz L., A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar. 30 (1977) 3-4, 241-251.
• [12] Ore O., Note on hamilton circuits, Amer. Math. Monthly 67 (1960), 55.
• [13] Posa L., A theorem concerning Hamiltonian lines, Publ. Math. Inst. Hungar. Acad. Sci. 7 (1962) 225-226.