PDF

Discussiones Mathematicae Graph Theory 26(3) (2006) 403-412
DOI: https://doi.org/10.7151/dmgt.1332

ON ARBITRARILY VERTEX DECOMPOSABLE UNICYCLIC GRAPHS WITH DOMINATING CYCLE

Sylwia Cichacz  and  Irmina A. Zioło

Faculty of Applied Mathematics
AGH University of Science and Technology
Al. A. Mickiewicza 30, 30-059 Kraków, Poland
e-mail: cichacz@agh.edu.pl
e-mail: ziolo@agh.edu.pl

Abstract

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,☐,n_k) of positive integers such that ∑^k_{i = 1} n_i = n, there exists a partition (V₁,☐,V_k) of vertex set of G such that for every i ∈ {1,☐,k} the set V_i induces a connected subgraph of G on n_i 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.

Keywords: arbitrarily vertex decomposable graph, dominating cycle.

2000 Mathematics Subject Classification: 05C35, 05C38, 05C99.

References

[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.
[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.
[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.
[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.
[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/.
[6]	A. Marczyk, Ore-type condition for arbitrarily vertex decomposable graphs, preprint (2005).

Received 30 November 2005
Revised 31 March 2006