ON THE LENGTH OF LONGEST DOMINATING CYCLES IN GRAPHS

A cycle C in an undirected and simple graph G is dominating if G - C i s edgeless. A graph G is called cycle-dominable if G contains a domina ting cycle. There exists 1-tough graph in which no longest cycle is do minating. Moreover, the difference of the length of a longest cycle an d of a longest dominating cycle in a 1-tough cycle-dominable graph may be made arbitrarily large. Some lower bounds for the length of domina ting cycles in cycle-dominable graph are given. These results generali ze and strengthen some well-known theorems of Jung and Fraisse (1989) and Bauer and Veldman et al. (1988).