# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## 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 (n1,☐,nk) of positive integers such that ∑ki = 1 ni = n, there exists a partition (V1,☐,Vk) 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.

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