O Problema Quadrático de Alocação, PQA, um dos mais difíceis da classe NP-hard, modela diversas aplicações em diferentes áreas como pesquisa operacional, computação paralela e análise estatística de dados discretos. Além disso, problemas conhecidos como o do caixeiro viajante, o da clique maximal, o de particionamento e o de isomorfismo de grafos podem ser formulados como um PQA. Na tentativa de identificar novas propriedades estruturais para este problema, diversas formulações aparecem na literatura. Reunimos tais formulações, destacando suas principais características para classificá-las segundo as técnicas matemáticas nelas adotadas. Finalizamos o artigo avaliando a extensão das contribuições dadas ao problema, quer na elaboração de algoritmos, quer no cálculo de limites inferiores ou na caracterização de classes de exemplares polinomiais ou não, oriundas das diferentes abordagens aqui estudadas.
A bug Bugp,r1r2 is a graph obtained from a complete graph Kp by deleting an edge uv and attaching the paths Priand Pr2 by one of their end vertices at u and v, respectively. Let Q(G) be the signless Laplacian matrix of a graph G and q1(G) be the spectral radius of Q(G). It is known that the bug maximizes q1(G) among all graphs G of order n and diameter d. For a bug B of order n and diameter d, n - d is an eigenvalue of Q(B) with multiplicity n - d - 1. In this paper, we prove that remainder d +1 eigenvalues of Q(B), among them q1(B), can be computed as the eigenvalues of a symmetric tridiagonal matrix of order d +1. Finally, we show that q1(B0) can be computed as the largest eigenvalue of a symmetric tridiagonal matrix of order whenever d is even.
4 January 2010 in Linear Algebra and its Applications
A complete caterpillar is a caterpillar in which each internal vertex is a quasi-pendent vertex. In this paper, in the class of all complete caterpillars on n vertices and diameter d, the caterpillar attaining the largest Laplacian index is determined. In addition, it is proved that this caterpillar also attains the largest adjacency index.