Laplacian eigenvectors and eigenvalues and almost equitable partitions

Relations between Laplacian eigenvectors and eigenvalues and the existence of almost equitable partitions (which are generalizations of equitable partitions) are presented. Furthermore, on the basis of some properties of the adjacency eigenvectors of a graph, a necessary and sufficient condition for the graph to be primitive strongly regular is introduced. © 2006 Elsevier Ltd. 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.

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.

Modelo de Kuramoto com campos aleatórios em redes complexas

Neste trabalho é estudado o modelo de Kuramoto num grafo completo, em redes scale-free com uma distribuição de ligações P(q) ~ q-Y e na presença de campos aleatórios com magnitude constante e gaussiana. Para tal, foi considerado o método Ott-Antonsen e uma aproximação "annealed network". Num grafo completo, na presença de campos aleatórios gaussianos, e em redes scale-free com 2 < y < 5 na presença de ambos os campos aleatórios referidos, foram encontradas transições de fase contínuas. Considerando a presença de campos aleatórios com magnitude constante num grafo completo e em redes scale-free com y > 5, encontraram-se transições de fase contínua (h < √2) e descontínua (h > √2). Para uma rede SF com y = 3, foi observada uma transição de fase de ordem infinita. Os resultados do modelo de Kuramoto num grafo completo e na presença de campos aleatórios com magnitude constante foram comparados aos de simulações, tendo-se verificado uma boa concordância. Verifica-se que, independentemente da topologia de rede, a constante de acoplamento crítico aumenta com a magnitude do campo considerado. Na topologia de rede scale-free, concluiu-se que o valor do acoplamento crítico diminui à medida que valor de y diminui e que o grau de sincronização aumenta com o aumento do número médio das ligações na rede. A presença de campos aleatórios com magnitude gaussiana num grafo completo e numa rede scale-free com y > 2 não destrói a transição de fase contínua e não altera o comportamento crítico do modelo de Kuramoto.

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.

Spectral characterization of families of split graphs

An upper bound for the sum of the squares of the entries of the principal eigenvector corresponding to a vertex subset inducing a k-regular subgraph is introduced and applied to the determination of an upper bound on the order of such induced subgraphs. Furthermore, for some connected graphs we establish a lower bound for the sum of squares of the entries of the principal eigenvector corresponding to the vertices of an independent set. Moreover, a spectral characterization of families of split graphs, involving its index and the entries of the principal eigenvector corresponding to the vertices of the maximum independent set is given. In particular, the complete split graph case is highlighted.

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.

A generalization of fiedler's lemma and some applications

In a previous paper [M. Robbiano, E.A. Martins, and I. Gutman, Extending a theorem by Fiedler and applications to graph energy, MATCH Commun. Math. Comput. Chem. 64 (2010), pp. 145-156], a lemma by Fiedler was used to obtain eigenspaces of graphs, and applied to graph energy. In this article Fiedler's lemma is generalized and this generalization is applied to graph spectra and graph energy. © 2011 Taylor & Francis.

The Jordan canonical form for a class of weighted directed graphs

Recently, Cardon and Tuckfield (2011) [1] have described the Jordan canonical form for a class of zero-one matrices, in terms of its associated directed graph. In this paper, we generalize this result to describe the Jordan canonical form of a weighted adjacency matrix A in terms of its weighted directed graph.