It is known that graph invariants, which contain a great quantity of information on graph structure (for example, spectral invariants), are obtained by solving some extremal problems on graphs. Recently, such highly informative graph invariants are applied in solving optimization problems on graphs (e.g., the travelling salesman problem (TSP�. Using these paradigms, several relations, interconnections and interactions between graph theory and mathematical programming are described in this study. A model of TSP based on semidefinite programming and algebraic connectivity of graphs is described. A class of relaxations of this TSP model is defined and some solution techniques based on this class are proposed. Several examples of graph invariants defined by some kind of optimization tasks are also presented. Using several spectrally based graph invariants we treat the graph isomorphism problem.