Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n - 1, G is said to be k-extendable if for every matching M of size k in G there is a perfect matching in G containing all the edges of M. A k-extendable graph G is said to be k-critical (k-minimal) if G+uv (G-uv) is not k-extendable for every non-adjacent (adjacent) pair of vertices u and v of G. The problem that arises is that of characterizing k-extendable, k-critical and k-minimal graphs.In Chapter 2, we establish that δ(G) ≥ 1/2(n + k) is a sufficient condition for a bipartite graph G on 2n vertices to be k-extendable. For a graph G on 2n vertices with δ(G) ≥ n + k 1, n - k even and n/2 ≤ k ≤ n - 2, we prove that a necessary and sufficient condition for G to be k-extendable is that its independence number is at most n - k. We also establish that a k-extendable graph G of order 2n has k + 1 ≤ δ(G) n or δ(G) ≥ 2k + 1, 1 ≤ k ≤ n - 1. Further, we establish the existence of a k-extendable graph G on 2n vertices with δ(G) = j for each integer j Є [k + 1, n] u [2k + 1, 2n 1]. For k = n - 1 and n - 2, we completely characterize k-extendable graphs on 2n vertices. We conclude Chapter 2 with a variation of the concept of extendability to odd order graphs.In Chapter 3, we establish a number of properties of k-critical graphs. These results include sufficient conditions for k-extendable graphs to be k-critical. More specifically, we prove that for a k-extendable graph G ≠ K2n on 2n vertices, 2 ≤ k ≤ n - 1, if for every pair of non-adjacent vertices u and v of G there exists a dependent set S ( a subset S of V (G) is dependent if the induced subgraph G[S] has at least one edge) of G-u-v such that o(G-(S u {u,v})) = S, then G is k-critical. Moreover, for k = 2 this sufficient condition is also a necessary condition for non-bipartite graphs. We also establish a ++ / necessary condition, in terms of the minimum degree, for k-critical graphs.We conclude Chapter 3 by completely characterizing k-critical graphs on 2n vertices for k = 1, n - 1 and n - 2.Chapter 4 contains results on k-minimal graphs. These results include necessary and sufficient conditions for k-extendable graphs to be k-minimal. More specifically, we prove that for a k-extendable graph G on 2n vertices, 1 ≤ k ≤ n - 1, the following are equivalent:G is minimalfor every edge e = uv of G there exists a matching M of size k in G-e such that V(M) n {u,v} = ø and for every perfect matching F in G containing M, e Є F.for every edge e = uv of G there exists a vertex set S of G-u-v such that: M(S) ≥ k; o(G-e-S) = S - 2k + 2; and u and v belong to different odd components of G-e-S, where M(S) denotes a maximum matching in G[S].We also establish a necessary condition, in terms of minimum degree, for k-minimal and k-minimal bipartite graphs. In fact, we prove that a k-minimal graph G ≠ K2n on 2n vertices, 1 ≤ k ≤ n - 1, has minimum degree at most n + k - 1. For a k-minimal bipartite graph G ≠ Kn,n , 1 ≤ k ≤ n - 3, we show that δ(G) < ½(n + k).Chapter 1 provides the notation, terminology, general concepts and the problems concerning extendability graphs and (k,t)-critical graphs.

Submitted by Geyciane Santos (geyciane_thamires@hotmail.com) on 2015-10-02T15:09:09Z No. of bitstreams: 1 Dissertação - Fábio Júnior Pimentel da Silva.pdf: 1344786 bytes, checksum: c099c822dce738552cf54d2d4a0b6113 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-10-08T20:24:29Z (GMT) No. of bitstreams: 1 Dissertação - Fábio Júnior Pimentel da Silva.pdf: 1344786 bytes, checksum: c099c822dce738552cf54d2d4a0b6113 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-10-08T20:37:38Z (GMT) No. of bitstreams: 1 Dissertação - Fábio Júnior Pimentel da Silva.pdf: 1344786 bytes, checksum: c099c822dce738552cf54d2d4a0b6113 (MD5) / Made available in DSpace on 2015-10-08T20:37:38Z (GMT). No. of bitstreams: 1 Dissertação - Fábio Júnior Pimentel da Silva.pdf: 1344786 bytes, checksum: c099c822dce738552cf54d2d4a0b6113 (MD5) Previous issue date: 2015-04-27 / OUTRAS / This paper presents an algorithm that uses the descent method to for solve a vector optimization problem unconstrained multiobjective where the functions considered are continuously differentiable. It will also be a study on the theoretical foundations, namely: elements of convex analysis, induced partial order by a generic cone K, as well as multi-objective and vectorial programming fundamentals, required for formulation of the mathematical model. To calculate the direction of descent, an auxiliary function strongly convex and is used for the step size, the Armijo rule type. It is shown that the whole point of accumulation of the generated sequence the algorithm is K-critical for the vector. / Neste trabalho, apresenta-se um algoritmo que utiliza o método de descida para resolver um problema de otimização vetorial ou multiobjetivo irrestrito, onde as funções consideradas são continuamente diferenciáveis. Apresenta-se um estudo sobre os fundamentos teóricos, a saber: elementos da análise convexa, ordem parcial induzida por um cone K convexo, fechado, pontiagudo e com o interior não vazio bem como alguns fundamentos para programação multiobjetivo e vetorial, necessários para formulação do modelo matemático. Para o cálculo da direção de descida, utiliza-se uma função auxiliar fortemente convexa e, para o tamanho do passo, um procedimento tipo Armijo. Demonstra-se que todo ponto de acumulação da sequência gerada por esse algoritmo é K-crítico.