Energy of line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. The energy of a matrix is equal to the sum of its singular values. We establish relations between the energy of the line graph of a graph G and the energies associated with the Laplacian and signless Laplacian matrices of G. © 2010 Elsevier B.V. All rights reserved.

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.

Main eigenvalues and (κ, τ)-regular sets

A (κ, τ)-regular set is a subset of the vertices of a graph G, inducing a κ-regular subgraph such that every vertex not in the subset has τ neighbors in it. A main eigenvalue of the adjacency matrix A of a graph G has an eigenvector not orthogonal to the all-one vector j. For graphs with a (κ, τ)-regular set a necessary and sufficient condition for an eigenvalue be non-main is deduced and the main eigenvalues are characterized. These results are applied to the construction of infinite families of bidegreed graphs with two main eigenvalues and the same spectral radius (index) and some relations with strongly regular graphs are obtained. Finally, the determination of (κ, τ)-regular sets is analyzed. © 2009 Elsevier Inc. All rights reserved.

Dominating induced matchings

We study the problem of determining whether or not a graph G has an induced matching that dominates every edge of the graph, which is also known as efficient edge domination. This problem is known to be NP-complete in general as well as in some restricted domains, such as bipartite graphs or regular graphs. In this paper, we identify a graph parameter to which the complexity of the problem is sensible and produce results of both negative (intractable) and positive (solvable in polynomial time) type. © 2009 Springer Berlin Heidelberg.

Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p ≥ 3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete. © 2008 Elsevier B.V. All rights reserved.

Politopo de Birkhoff acíclico

Neste trabalho estabelece-se uma interpreta c~ao geom etrica, em termos da teoria dos grafos, para v ertices, arestas e faces de uma qualquer dimens~ao do politopo de Birkho ac clico, Tn = n(T), onde T e uma arvore com n v ertices. Generaliza-se o resultado obtido por G. Dahl, [18], para o c alculo do di^ametro do grafo G( t n), onde t n e o politopo das matrizes tridiagonais duplamente estoc asticas. Adicionalmente, para q = 0; 1; 2; 3 s~ao obtidas f ormulas expl citas para a contagem do n umero de q faces do politopo de Birkho tridiagonal, t n, e e feito o estudo da natureza geom etrica dessas mesmas faces. S~ao, tamb em, apresentados algoritmos para efectuar contagens do n umero de faces de dimens~ao inferior a de uma dada face do politopo de Birkho ac clico.

On the Faria's inequality for the Laplacian and signless Laplacian spectra: a unified approach

Let p(G)p(G) and q(G)q(G) be the number of pendant vertices and quasi-pendant vertices of a simple undirected graph G, respectively. Let m_L±(G)(1) be the multiplicity of 1 as eigenvalue of a matrix which can be either the Laplacian or the signless Laplacian of a graph G. A result due to I. Faria states that mL±(G)(1) is bounded below by p(G)−q(G). Let r(G) be the number of internal vertices of G. If r(G)=q(G), following a unified approach we prove that mL±(G)(1)=p(G)−q(G). If r(G)>q(G) then we determine the equality mL±(G)(1)=p(G)−q(G)+mN±(1), where mN±(1) denotes the multiplicity of 1 as eigenvalue of a matrix N±. This matrix is obtained from either the Laplacian or signless Laplacian matrix of the subgraph induced by the internal vertices which are non-quasi-pendant vertices. Furthermore, conditions for 1 to be an eigenvalue of a principal submatrix are deduced and applied to some families of graphs.

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.

F. G. Teixeira e a comunidade matemática europeia nos séculos XIX-XX

Esta dissertação descreve o processo de integração dos matemáticos portugueses na comunidade matemática internacional no final do século XIX e início do século XX, focando-se na vida e obra do matemático Francisco Gomes Teixeira (1851-1933). Tenciona a ser mais um contributo para o reconhecimento nacional e internacional do matemático Gomes Teixeira analisando a sua obra como matemático e organizador científico em Portugal através de fontes, parcialmente ainda não conhecidas. Para esse efeito analisou-se a evolução histórica que ocorreu no mundo científico daquela época, em particular a formação da comunidade matemática através de iniciativas individuais ou coletivas, muitas vezes acompanhadas pela fundação de revistas e elaboração de manuais que contribuíram para a internacionalização e, de certa forma, para uma estandardização do estudo universitário básico. Em particular foi estudada a situação em Portugal, onde o papel de liderança foi assumido por Gomes Teixeira. Mostra-se como Gomes Teixeira, graças ao seu trabalho, ao seu talento como matemático e à sua atividade como organizador académico, conseguiu reduzir significativamente o isolamento científico de Portugal na área da matemática. Estudou-se em extensão a fundação de revistas científicas em diferentes países, acompanhando a sua evolução desde de revistas nacionais até revistas internacionais. Focando-nos no Jornal de Sciencias Matemáticas e Astronómicas, fundado em 1877 por Gomes Teixeira (mais tarde conhecido internacionalmente como Teixeira’s Journal), acompanhamos detalhadamente a sua transformação de uma revista nacional numa revista internacional, sendo esta transformação comum naquela época à maioria de revistas científicas importantes de outros países como, por exemplo, no caso do Jornal de Crelle, do Jornal de Liouville, ou outros. Estudou-se igualmente o reconhecimento a nível internacional, através de referências estrangeiras, da abordagem original de Gomes Teixeira à Análise Infinitesimal patente nos seus manuais. O interesse de Gomes Teixeira pela teoria das funções analíticas e pelos seus diferentes desenvolvimentos em série manifestou-se no grande número de artigos publicados sobre este tema e encontrou reconhecimento justo pela designação de um teorema que completa resultados de Lagrange e de Laurent como Teorema de Teixeira. Na sua análise do mérito científico de Gomes Teixeira esta dissertação restringiu-se conscientemente nesta área da Análise Matemática, uma vez que um estudo abrangente de toda a obra ultrapassasse o nosso objetivo. Foi também discutido o intenso intercâmbio científico levado a cabo por Gomes Teixeira através de correspondência e troca de publicações ou permuta de revistas com os matemáticos de diferentes países. Esta análise permitiu verificar um aumento da popularidade dos matemáticos portugueses através do incremento do número de artigos publicados no estrangeiro durante quase 30 anos. Uma fonte imprescindível nesta análise foi o Jahrbuch über die Fortschritte der Mathematik, cujas referências (em geral na língua alemã e por isso até agora quase nunca usadas na literatura Portuguesa) documentaram as publicações em quase todas as revistas matemáticas durante os anos da sua existência entre 1868 e 1942. Descreve-se a colaboração de Gomes Teixeira com diferentes organizações internacionais e documenta-se o apreço internacional por parte do mundo académico. Novos documentos traçam o processo de eleição como membro da Academia das Ciências Alemã Leopoldina, sob proposta de Georg Cantor e outros matemáticos alemães. Finalmente, incluí-se uma breve descrição das atividades levadas a cabo na Rússia, em Espanha e na Grécia em prol do processo de internacionalização da comunidade matemática europeia tendo em vista uma melhor contextualização do contributo de Gomes Teixeira para a integração de Portugal neste processo.

Necessary and sufficient conditions for a Hamiltonian graph

A graph is singular if the zero eigenvalue is in the spectrum of its 0-1 adjacency matrix A. If an eigenvector belonging to the zero eigenspace of A has no zero entries, then the singular graph is said to be a core graph. A ( k,t)-regular set is a subset of the vertices inducing a k -regular subgraph such that every vertex not in the subset has t neighbours in it. We consider the case when k=t which relates to the eigenvalue zero under certain conditions. We show that if a regular graph has a ( k,k )-regular set, then it is a core graph. By considering the walk matrix we develop an algorithm to extract ( k,k )-regular sets and formulate a necessary and sufficient condition for a graph to be Hamiltonian.

Spectra of graphs obtained by a generalization of the join graph operation

Taking a Fiedler’s result on the spectrum of a matrix formed from two symmetric matrices as a motivation, a more general result is deduced and applied to the determination of adjacency and Laplacian spectra of graphs obtained by a generalized join graph operation on families of graphs (regular in the case of adjacency spectra and arbitrary in the case of Laplacian spectra). Some additional consequences are explored, namely regarding the largest eigenvalue and algebraic connectivity.

Relations between (κ, τ)-regular sets and star complements

Let G be a finite graph with an eigenvalue μ of multiplicity m. A set X of m vertices in G is called a star set for μ in G if μ is not an eigenvalue of the star complement G\X which is the subgraph of G induced by vertices not in X. A vertex subset of a graph is (k ,t)-regular if it induces a k -regular subgraph and every vertex not in the subset has t neighbors in it. We investigate the graphs having a (k,t)-regular set which induces a star complement for some eigenvalue. A survey of known results is provided and new properties for these graphs are deduced. Several particular graphs where these properties stand out are presented as examples.