On arbitrarily vertex decomposable unicyclic graphs with dominating cycle
Sylwia Cichacz ; Irmina A. Zioło
Discussiones Mathematicae Graph Theory, Tome 26 (2006), p. 403-412 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,...,nₖ) of positive integers such that ∑i=1kni=n, there exists a partition (V₁,...,Vₖ) of vertex set of G such that for every i ∈ 1,...,k the set Vi induces a connected subgraph of G on ni vertices. We consider arbitrarily vertex decomposable unicyclic graphs with dominating cycle. We also characterize all such graphs with at most four hanging vertices such that exactly two of them have a common neighbour.

Publié le : 2006-01-01
EUDML-ID : urn:eudml:doc:270726 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1332,
     author = {Sylwia Cichacz and Irmina A. Zio\l o},
     title = {On arbitrarily vertex decomposable unicyclic graphs with dominating cycle},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {26},
     year = {2006},
     pages = {403-412},
     zbl = {1131.05071},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1332}
}

Sylwia Cichacz; Irmina A. Zioło. On arbitrarily vertex decomposable unicyclic graphs with dominating cycle. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 403-412. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1332/

[000] [1] D. Barth, O. Baudon and J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002) 205-216, doi: 10.1016/S0166-218X(00)00322-X. | Zbl 1002.68107

[001] [2] D. Barth and H. Fournier, A degree bound on decomposable trees, Discrete Math. 306 (2006) 469-477, doi: 10.1016/j.disc.2006.01.006. | Zbl 1092.05054

[002] [3] S. Cichacz, A. Görlich, A. Marczyk, J. Przybyło and M. Woźniak, Arbitrarily vertex decomposable caterpillars with four or five leaves, Preprint MD-010 (2005), http://www.ii.uj.edu.pl/preMD/, to appear. | Zbl 1142.05065

[003] [4] M. Hornák and M. Woźniak, Arbitrarily vertex decomposable trees are of maximum degree at most six, Opuscula Math. 23 (2003) 49-62. | Zbl 1093.05510

[004] [5] R. Kalinowski, M. Pilśniak, M. Woźniak and I.A. Zioło, Arbitrarily vertex decomposable suns with few rays, preprint (2005), http://www.ii.uj.edu.pl/preMD/. | Zbl 1214.05125

[005] [6] A. Marczyk, Ore-type condition for arbitrarily vertex decomposable graphs, preprint (2005).