Search

Let G be a graph with adjacency matrix A(G) and degree diagonal matrix D(G). In 2017, Nikiforov [1] defined the matrix Aalpha(G), as a convex combination of A(G) and D(G), the following way, Aalpha(G) = alpha A(G) + (1 - alpha)D(G), where alpha belongs to [0,1]. In this paper, we present some new upper and lower bounds for the largest, second largest, and smallest eigenvalue of the Aalpha-matrix. Moreover, extremal graphs attaining some of these bounds are characterized, 14 pages, 3 figures, 2 tables

Let G be a graph of order $n$ with adjacency matrix $A(G)$ and diagonal matrix of degree $D(G)$. For every $α\in [0,1]$, Nikiforov \cite{VN17} defined the matrix $A_α(G) = αD(G) + (1-α)A(G)$. In this paper we present the $A_α(G)$-characteristic polynomial when $G$ is obtained by coalescing two graphs, and if $G$ is a semi-regular bipartite graph we obtain the $A_α$-characteristic polynomial of the line graph associated to $G$. Moreover, if $G$ is a regular graph we exhibit the $A_α$-characteristic polynomial for the graphs obtained from some operations., 19 pages, 5 figures

Neste trabalho, apresentamos alguns resultados relacionados, principalmente às propriedades algorítmicas e de complexidade de um produto de grafos chamado prisma complementar. Respondendo algumas questões deixadas em aberto por Haynes, Slater e van der Merwe, mostramos o problema de clique, conjunto independente e conjunto com kdominantes é NP-Completo para prismas complementares em geral. Além disso, mostramos resultados de NP-completude em relação ao cálculo de alguns parâmetros da convexidade P3 para o prisma complementar de grafos em geral, como o número P3, número envoltório P3 e número de Carathéodory. Mostramos que o cálculo do número P3 é NPcompleto para o prisma complementar de grafos em geral. Já para o número envoltório P3, mostramos que o mesmo pode ser calculado de forma eficiente em tempo polinomial. Para o número de Carathéodory, mostramos que é NP-completo para os prismas complementares de grafos bipartidos, mas que para árvores, este pode ser calculado em tempo polinomial e ainda, para classe dos cografos, o cálculo do número de Carathéodory do prisma complementar desses é 3. Encontramos também, uma relação entre a cardinalidade de um conjunto de Carathéodory de um grafo qualquer e um conjunto de Carathéodory do seu prisma complementar. Por fim, estabelecemos um limite superior do cálculo dos parâmetros: número geodésico, número envoltório e número de Carathéodory para operações prisma complementar de grafos caminho, ciclos e completos considerando as convexidades P3 e geodésica. In this work, we present some related results, especially the properties algoritimics and of complexity of a product of graphs called complementary prism. Answering some questions left open by Haynes, Slater and van der Merwe, we show that the problem of click, independent set and k-dominant set is NP-Complete for complementary prisms in general. Furthermore, we show NP-completeness results regarding the calculation of some parameters of the P3-convexity for the complementary prism graphs in general, as the P3-geodetic number, P3-hull number and P3-Carathéodory number. We show that the calculation of P3-geodetic number is NP-complete for complementary prism graphs in general. As for the P3-hull number, we can show that the same can be efficiently computed in polynomial time. For the P3-Carathéodory number, we show that it is NPcomplete complementary to prisms bipartite graphs, but for trees, this may be calculated in polynomial time and, for class of cografos, calculating the P3-Carathéodory number of complementary prism of these is 3. We also found a relationship between the cardinality Carathéodory set of a graph and a any Carathéodory set of complementary prism. Finally, we established an upper limit calculation the parameters: geodetic number, hull number and Carathéodory number to operations complementary prism of path, cycles and complete graphs considering the convexities P3 and geodesic. Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq

Due to great difficulty of accurate solution of Combinatorial Optimization Problems, some heuristic methods have been developed and during many years, the analysis of performance of these approaches was not carried through in a systematic way. The proposal of this work is to make a statistical analysis of heuristic approaches to the Traveling Salesman Problem (TSP). The focus of the analysis is to evaluate the performance of each approach in relation to the necessary computational time until the attainment of the optimal solution for one determined instance of the TSP. Survival Analysis, assisted by methods for the hypothesis test of the equality between survival functions was used. The evaluated approaches were divided in three classes: Lin-Kernighan Algorithms, Evolutionary Algorithms and Particle Swarm Optimization. Beyond those approaches, it was enclosed in the analysis, a memetic algorithm (for symmetric and asymmetric TSP instances) that utilizes the Lin-Kernighan heuristics as its local search procedure Devido à grande dificuldade de solução exata dos Problemas de Otimização Combinatória, vários métodos heurísticos têm sido desenvolvidos e durante muitos anos, a análise de desempenho dessas abordagens não foi realizada de maneira sistemática. A proposta deste trabalho é fazer uma análise estatística de abordagens heurísticas aplicadas ao Problema do Caixeiro Viajante. O foco da análise é avaliar o desempenho de cada abordagem em relação ao tempo computacional necessário até a obtenção da solução ótima para uma determinada instância do PCV. Para essa análise, foi utilizada uma metodologia estatística chamada Análise de Sobrevivência, auxiliada por métodos para o teste da hipótese de igualdade entre funções. Para uma melhor compreensão, as abordagens avaliadas foram divididas em três classes: Algoritmos Lin-Kernighan, Algoritmos Evolucionários e Algoritmos de Otimização por Nuvem de Partículas. Além das abordagens já existentes, foi incluído na análise, um algoritmo memético (para instâncias simétricas e assimétricas do PCV) que utiliza o algoritmo de Lin e Kernighan como procedimento de busca local