Bounds for the signless laplacian energy

The energy of a graph G is the sum of the absolute values of the eigenvalues of the adjacency matrix of G. The Laplacian (respectively, the signless Laplacian) energy of G is the sum of the absolute values of the differences between the eigenvalues of the Laplacian (respectively, signless Laplacian) matrix and the arithmetic mean of the vertex degrees of the graph. In this paper, among some results which relate these energies, we point out some bounds to them using the energy of the line graph of G. Most of these bounds are valid for both energies, Laplacian and signless Laplacian. However, we present two new upper bounds on the signless Laplacian which are not upper bounds for the Laplacian energy. © 2010 Elsevier Inc. All rights reserved.

A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.

A study of singular integral operators with shift

Nesta tese, consideram-se operadores integrais singulares com a acção extra de um operador de deslocacamento de Carleman e com coeficientes em diferentes classes de funções essencialmente limitadas. Nomeadamente, funções contínuas por troços, funções quase-periódicas e funções possuíndo factorização generalizada. Nos casos dos operadores integrais singulares com deslocamento dado pelo operador de reflexão ou pelo operador de salto no círculo unitário complexo, obtêm-se critérios para a propriedade de Fredholm. Para os coeficientes contínuos, uma fórmula do índice de Fredholm é apresentada. Estes resultados são consequência das relações de equivalência explícitas entre aqueles operadores e alguns operadores adicionais, tais como o operador integral singular, operadores de Toeplitz e operadores de Toeplitz mais Hankel. Além disso, as relações de equivalência permitem-nos obter um critério de invertibilidade e fórmulas para os inversos laterais dos operadores iniciais com coeficientes factorizáveis. Adicionalmente, aplicamos técnicas de análise numérica, tais como métodos de colocação de polinómios, para o estudo da dimensão do núcleo dos dois tipos de operadores integrais singulares com coeficientes contínuos por troços. Esta abordagem permite também a computação do inverso no sentido Moore-Penrose dos operadores principais. Para operadores integrais singulares com operadores de deslocamento do tipo Carleman preservando a orientação e com funções contínuas como coeficientes, são obtidos limites superiores da dimensão do núcleo. Tal é implementado utilizando algumas estimativas e com a ajuda de relações (explícitas) de equivalência entre operadores. Focamos ainda a nossa atenção na resolução e nas soluções de uma classe de equações integrais singulares com deslocamento que não pode ser reduzida a um problema de valor de fronteira binomial. De forma a atingir os objectivos propostos, foram utilizadas projecções complementares e identidades entre operadores. Desta forma, as equações em estudo são associadas a sistemas de equações integrais singulares. Estes sistemas são depois analisados utilizando um problema de valor de fronteira de Riemann. Este procedimento tem como consequência a construção das soluções das equações iniciais a partir das soluções de problemas de valor de fronteira de Riemann. Motivados por uma grande diversidade de aplicações, estendemos a definição de operador integral de Cauchy para espaços de Lebesgue sobre grupos topológicos. Assim, são investigadas as condições de invertibilidade dos operadores integrais neste contexto.

Resultados espectrais relacionados com a estrutura dos grafos

Nesta tese são estabelecidas novas propriedades espectrais de grafos com estruturas específicas, como sejam os grafos separados em cliques e independentes e grafos duplamente separados em independentes, ou ainda grafos com conjuntos (κ,τ)-regulares. Alguns invariantes dos grafos separados em cliques e independentes são estudados, tendo como objectivo limitar o maior valor próprio do espectro Laplaciano sem sinal. A técnica do valor próprio é aplicada para obter alguns majorantes e minorantes do índice do espectro Laplaciano sem sinal dos grafos separados em cliques e independentes bem como sobre o índice dos grafos duplamente separados em independentes. São fornecidos alguns resultados computacionais de modo a obter uma melhor percepção da qualidade desses mesmos extremos. Estudamos igualmente os grafos com um conjunto (κ,τ)-regular que induz uma estrela complementar para um valor próprio não-principal $. Além disso, é mostrado que $=κ-τ. Usando uma abordagem baseada nos grafos estrela complementares construímos, em alguns casos, os respectivos grafos maximais. Uma caracterização dos grafos separados em cliques e independentes que envolve o índice e as entradas do vector principal é apresentada tal como um majorante do número da estabilidade dum grafo conexo.

Computational methods in the fractional calculus of variations and optimal control

The fractional calculus of variations and fractional optimal control are generalizations of the corresponding classical theories, that allow problem modeling and formulations with arbitrary order derivatives and integrals. Because of the lack of analytic methods to solve such fractional problems, numerical techniques are developed. Here, we mainly investigate the approximation of fractional operators by means of series of integer-order derivatives and generalized finite differences. We give upper bounds for the error of proposed approximations and study their efficiency. Direct and indirect methods in solving fractional variational problems are studied in detail. Furthermore, optimality conditions are discussed for different types of unconstrained and constrained variational problems and for fractional optimal control problems. The introduced numerical methods are employed to solve some illustrative examples.

Majorantes para a ordem de subgrafos induzidos k-regulares

Muitos dos problemas de otimização em grafos reduzem-se à determinação de um subconjunto de vértices de cardinalidade máxima que induza um subgrafo k-regular. Uma vez que a determinação da ordem de um subgrafo induzido k-regular de maior ordem é, em geral, um problema NP-difícil, são deduzidos novos majorantes, a determinar em tempo polinomial, que em muitos casos constituam boas aproximações das respetivas soluções ótimas. Introduzem-se majorantes espetrais usando uma abordagem baseada em técnicas de programação convexa e estabelecem-se condições necessárias e suficientes para que sejam atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro das matrizes de adjacência, laplaciana e laplaciana sem sinal. É ainda apresentado um algoritmo não polinomial para a determinação de umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular de ordem máxima para uma classe particular de grafos. Finalmente, faz-se um estudo computacional comparativo com vários majorantes e apresentam-se algumas conclusões.

Upper palaeozoic stratigraphy and palynology of OMZ, NW and SW Portugal

Neste trabalho descreve-se e interpreta-se a estratigrafia e palinologia de rochas sedimentares e metassedimentos de idade devónica e carbónica aflorantes ao longo da zona de cisalhamento Porto-Tomar, a Sul na Bacia de Santa Susana e em vários locais onde afloram os Calcários de Odivelas. Existe um registo de sedimentação descontínuo possivelmente associado a esta zona de cisalhamento desde o Devónico Superior até ao Pennsylvaniano. Desde o Devónico Superior até ao Mississippiano esta sedimentação é marinha, de carácter essencialmente turbiditico com uma tendência geral para se tornar mais proximal. A maturação térmica atingida por estas rochas (Unidade de Albergaria-a-Velha) é alta e a unidade é considerada pós-madura em termos de potencial gerador de hidrocarbonetos. O metamorfismo incipiente é acompanhado por intensa deformação. A bacia do Buçaco é inteiramente terrestre e tem a sua idade restrita ao Gjeliano (Pennsylvaniano superior). O controlo da sedimentação pela actividade da zona de cisalhamento Porto-Tomar é evidente. A sua maturação térmica é relativamente baixa (dentro da catagénese) e a deformação menos intensa, contrastando com a Unidade de Albergaria-a-Velha com a qual parece ter uma relação geométrica complexa, de origem tectónica. As relações de campo e dados da maturação térmica permitem inferir um evento térmico e de deformação à escala regional entre o Serpukoviano e o Gjeliano e outro, essencialmente de deformação, entre o Gjeliano e o Carniano (Triássico Superior). A bacia de Santa Susana tem características semelhantes à do Buçaco, visto estar enquadrada também numa zona de cisalhamento importante que neste caso separa a Zona de Ossa-Morena da Zona Sul Portuguesa. A sua idade é kasimoviana, possivelmente também moscoviana (Pennsylvaniano médio). A evolução térmica da bacia e a relação estrutural com as unidades circundantes permite inferir um evento térmico e de deformação regionalmente importante entre o Viseano e o (?)Moscoviano-Kasimoviano. O estudo detalhado de vários locais onde afloram os Calcários de Odivelas permite desenhar uma paleogeografia regional durante o intervalo Emsiano terminal-Givetiano (fim do Devónico Inferior – Devónico Médio) para o sector Oeste da Zona de Ossa-Morena: Actividade vulcânica em regime marinho (e talvez subaéreo), formando edifícios vulcânicos no topo dos quais (e possivelmente também em altos fundos estruturais) se instalaram recifes, tendo a comunidade recifal, em termos de diversidade, persistido durante todo ou grande parte deste intervalo de tempo. O evento Choteč basal é observável num destes locais.

O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.