International Journal of Mathematics and Mathematical Sciences
Volume 2011 (2011), Article ID 206404, 11 pages
doi:10.1155/2011/206404
Review Article

Graph Invariants and Large Cycles: A Survey

Institute for Informatics and Automation Problems, National Academy of Sciences, P. Sevak 1, Yerevan 0014, Armenia

Received 30 December 2010; Accepted 1 February 2011

Academic Editor: Howard Bell

Copyright © 2011 Zh. G. Nikoghosyan. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Graph invariants provide a powerful analytical tool for investigation of abstract substructures of graphs. This paper is devoted to large cycle substructures, namely, Hamilton, longest and dominating cycles and some generalized cycles including Hamilton and dominating cycles as special cases. In this paper, we have collected 36 pure algebraic relations between basic (initial) graph invariants ensuring the existence of a certain type of large cycles. These simplest kind of relations having no forerunners in the area actually form a source from which nearly all possible hamiltonian results (including well-known Ore's theorem, Posa's theorem, and many other generalizations) can be developed further by various additional new ideas, generalizations, extensions, restrictions, and structural limitations.