app.uff.br§ão... · 2020. 7. 27. · Lucas Lima Silva Portugal Q-ESPECTRO E D-ESPECTRO DOS GRAFOS ARANHA Dissertação apresentada por Lucas Lima Silva Portugal ao Curso de Mestrado

Centro de Estudos Gerais Curso de Mestrado em Matemática Coordenação de Pós Graduação em Matemática

Lucas Lima Silva Portugal

Q-espectro e D-espectro dos grafos aranha

Orientadora: Renata Raposo Del-Vecchio

NITERÓI Março/2017


Q-ESPECTRO E D-ESPECTRO DOS GRAFOS ARANHA

Dissertação apresentada por Lucas Lima Silva Portugal ao Curso de Mestrado em Matemática - Universidade Federal Fluminense, como requisito parcial para a obtenção do Grau de Mestre. Linha de Pesquisa: Teoria espectral de grafos.

Orientadora: Renata Raposo Del-Vecchio

Niterói 2017

P853 S 59 Portugal, Lucas Lima Silva

Q-espectro e D-espectro dos grafos aranha / Lucas Lima Silva Portugal. - Niterói: [s.n.], 2017.

Dissertação (Mestrado em Matemática) -

Universidade Federal Fluminense, 2017.

1. Matemática 2. Matemática Discreta. 3. Teoria espectral de grafos

CDD: 510


Q-ESPECTRO E D-ESPECTRO DOS GRAFOS ARANHA Dissertação apresentada por Lucas Lima Silva Portugal ao Curso de Mestrado em Matemática - da Universidade Federal Fluminense, como requisito parcial para a obtenção do Grau de Mestre. Linha de Pesquisa: Teoria espectral de grafos.

Aprovada em: 30/03/2017

Banca Examinadora

_______________________________________________

Prof. Renata Raposo Del-Vecchio - Orientadora

Doutora – Universidade Federal Fluminense

_______________________________________________

Prof. Celso Marques da Silva Junior - Membro

Doutor – Centro Federal de Educação Tecnológica Celso Suckow da Fonseca _______________________________________________

Prof. Leonardo Lima - Membro

Doutor – Centro Federal de Educação Tecnológica Celso Suckow da Fonseca

_______________________________________________

Prof. Miriam del Milagro Abdón - Membro

Doutora – Universidade Federal Fluminense

NITERÓI

2017

AGRADECIMENTOS

Agradeço à minha família e namorada pelo suporte, especialmente à minha

mãe que continua me ensinando apesar de tudo que está passando.

Agradeço ao colega Átila pela ajuda em vários momentos deste trabalho e

minha orientadora, a professora Renata Del-Vecchio, por toda sua

paciência e compreensão, sua disposição me ajudando e guiando esse

trabalho. Finalmente, agradeço a CAPES pelo apoio financeiro a este

trabalho.

RESUMO

Os grafos do tipo aranha tem características interessantes, pois são todos

conexos com complementar conexo (mais ainda, o complementar de qualquer

grafo aranha também é um grafo aranha). Além disso, são os únicos grafos na

classe dos P4-esparsos que são conexos com complementar conexo. Neste

trabalho, investigamos o espectro da matriz laplaciana sem sinal e da matriz

distância nesta classe de grafos.

Sobre o Q-espectro dos grafos aranha, obtemos resultados sobre quantidades

de q-autovalores distintos, além de apresentar um resultado do tipo Nordhaus-

Gaddum, resultado que foi estendido para a classe dos P4-esparsos.

Investigando o D-espectro, novamente obtemos resultados sobre a

quantidade de d-autovalores distintos e seus sinais. Além disso, investigamos

algumas relações entre parâmetros D-espectrais e invariantes de grafos.

ABSTRACT

There are some interesting characteristics about the spider graphs, they are all

connected and so are their complement graph (even more, the complement of a

spider graph is still a spider graph). Furthermore, the spider graphs are the only

graphs that belongs to the P4-sparse class that are connected with their

complement still connected. In this work we investigate the signless laplacian and

distance matrix spectrum on the spider graphs.

About the Q-espectrum of a spider, we obtained results about the number of

distinct q-eigenvalues and a Nordhaus-Gaddum type result, which was extended

to the P4-sparse class.

Investigating the D-spectrum, again we obtained results about the number of

distinct d-eigenvalues and their signals. Furthermore, we investigated some

relationships between D-spectrum parameters and graph invariants.

Palavras chaves: Grafos, espectro, matriz laplaciana sem sinal, matriz distância, grafos aranha, q-espectro, d-espectro, Nordhaus-Gaddum, p4-esparso. Key words: Graphs, spectrum, signless laplacian matrix, distance matrix, spider graphs, q-spectrum, d-spectrum, Nordhaus-Gaddum, p4-sparse.

Lista de Figuras

2.1 Exemplo de um grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Complementar do grafo do Exemplo 2.1.1 . . . . . . . . . . . . . . . . . . 62.3 Na esquerda um grafo conexo e na direita um grafo desconexo com 2 com-

ponentes conexas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.4 Sm[5,2,K2] e Sg[3,2,K2], respectivamente. . . . . . . . . . . . . . . . . . . 8

1

Sumário

1 Introdução 3

2 Noções Básicas 5

2.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Álgebra Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3 Teoria Espectral de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3.1 Matriz de adjacência . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3.2 Matriz Laplaciana sem Sinal . . . . . . . . . . . . . . . . . . . . . 12

2.3.3 Matriz Distância . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Matriz laplaciana sem sinal 15

3.1 Q-Espectro de aranhas com cabeças especiais . . . . . . . . . . . . . . . . 15

3.2 Propriedades Q-espectrais para qualquer aranha . . . . . . . . . . . . . . . 32

3.3 Propriedades do tipo Nordhaus-Gaddum para aranhas . . . . . . . . . . . . 33

3.4 Propriedades do tipo Nordhaus-Gaddum para grafos P4-esparsos . . . . . . 34

4 Matriz distância 35

4.1 D-Espectro de algumas aranhas especiais . . . . . . . . . . . . . . . . . . 35

4.2 Propriedades D-espectrais para qualquer aranhas . . . . . . . . . . . . . . 49

4.3 Cabeças r-regulares com diâmetro 2 . . . . . . . . . . . . . . . . . . . . . 49

5 Conjecturas sobre a matriz Distância 51

5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.2 Resultados Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.3 Resultados para a inércia da matriz D . . . . . . . . . . . . . . . . . . . . 54

6 Conclusão 58

Capı́tulo 1

Introdução

Várias matrizes podem ser associadas a grafos. A matriz de adjacência é a mais natural

delas e a mais estudada. Muitas outras matrizes podem também ser associadas a grafos. As

relações entre autovalores dessas matrizes e propriedades estruturais dos grafos é o foco da

teoria espectral de grafos, campo onde se insere esta dissertação.

A matriz laplaciana sem sinal, embora tenha sido definida há bastante tempo, despertou

a atenção de pesquisadores mais recentemente, a partir de Cvetkovic em 2007 [11]. A

matriz distância também definida há bastante tempo, tem sido abordada em artigos de teoria

espectral de grafos mais recentemente, ver [10].

Nesta dissertação trataremos destas duas matrizes em uma classe especial de grafos, os

grafos do tipo aranha. Estes grafos têm caracterı́sticas interessantes, pois são todos conexos

com complementar conexo (além disso, o complementar de qualquer grafo desta classe

também está na classe).

A classe dos grafos P4-esparsos, definida em [4], contém os cografos que, por sua vez,

contém os thresholds. São duas classes importantes de grafos e muito estudadas, inclusive

do ponto de vista espectral. É sabido que todo grafo P4-esparso conexo com complementar

conexo é uma aranha [5]. Daı́, com o estudo espectral dos grafos aranha, foi possı́vel gene-

ralizar um importante resultado apresentado por Lima em [9] para todo grafo P4-esparso.

Esta dissertação está estruturada em seis capı́tulos que, além desta introdução, estão

assim distribuı́dos.

No segundo capı́tulo apresentamos algumas noções básicas de teoria dos grafos, além

de alguns resultados de álgebra linear e teoria espectral de grafos, os quais são necessários

à compreensão do texto.

No terceiro capı́tulo estudamos o espectro da matriz laplaciana sem sinal das aranhas,

obtendo resultados acerca da quantidade de autovalores distintos, que é um tema rele-

vante em teoria espectral de grafos. Apresentamos, explicitamente, autovalores laplacianos

sem sinal para a classe dos grafos aranha. Obtemos ainda propriedade do tipo Nordhaus-

Gaddum para os grafos aranha e concluı́mos o capı́tulo estendendo o importante resultado

apresentado em [9] para a classe dos grafos P4-esparsos.

O quarto capı́tulo é dedicado ao estudo do espectro da matriz distância das aranhas.

Aqui também encontramos famı́lias de grafos com poucos autovalores distintos e apresen-

tamos explicitamente autovalores da matriz distância para a classe dos grafos aranha.

Em [10] são discutidas várias conjecturas sobre o espectro da matriz distância de um

grafo qualquer. Muitas destas conjecturas já foram refutadas em geral. Porém, se chegaram

a ser consideradas como conjecturas é porque deviam valer para muitos grafos. Examina-

mos no capı́tulo cinco a validade delas para os grafos aranha, obtendo assim novos resulta-

3

dos nesta classe. Esses resultados relacionam parâmetros espectrais com outros invariantes

de grafos.

Finalmente, o capı́tulo seis apresenta as conclusões e aponta algumas direções de traba-

lhos futuros.

4

Capı́tulo 2

Noções Básicas

Este capı́tulo está dividido em três seções. Na primeira apresentamos as definições e resul-

tados da teoria de grafos necessários ao que se segue, além de fixar as notações que serão

utilizadas no decorrer do texto. A segunda seção é dedicada à apresentação de resultados

de Álgebra linear que serão aplicados às matrizes de grafos estudados. Na terceira seção

serão apresentadas as matrizes estudadas nesta dissertação e alguns resultados referentes a

elas.

2.1 Grafos

Iniciaremos esta seção apresentando definições gerais de grafos e introduzindo alguns parâ-

metros importantes.

Definição 2.1.1. Um grafo G = G(V (G),E(G)) é uma estrutura formada por dois con-juntos finitos chamados conjuntos de vértices e de arestas, denotados respectivamente por

V (G) e E(G), onde o segundo é formado por pares não ordenados de vértices distintosu,v ∈ V (G), denotado por {u,v} ∈ E(G), ou simplesmente uv. Indicamos por | V | e | E |,respectivamente, o número de vértices e o número de arestas de G; Quando existir a aresta

{u,v}, dizemos que os vértices u e v são adjacentes. O grau do vértice v ∈V (G), denotadopor d(v), é o número de vértices adjacentes a v; o menor grau dentre os graus dos vérticesé chamado grau mı́nimo, denotado por δ(G) = min{d(v);v ∈ V} e, analogamente, graumáximo é ∆(G) = max{d(v),v ∈ V}. O grau médio do grafo é d(G) = ∑v∈V d(v)|V (G)| , onde éfácil verificar que d(G) =

2|E(G)||V (G)| .

Exemplo 2.1.1. Considere o grafo H, ilustrado na figura 2.1, onde:

V (H) = {v1,v2,v3,v4,v5} eE(H) = {v1v2,v1v3,v2v3,v3v4,v4v5}

Figura 2.1: Exemplo de um grafo

5

Definição 2.1.2. O grafo complementar de um grafo G é o grafo G que tem o mesmo

conjunto de vértices do grafo original G, porém uma aresta {u,v} ∈ E(G) se, e somentese {u,v} 6∈ E(G). Na figura abaixo temos o complementar do grafo do Exemplo 2.1.1. Éclaro que G = G.

Figura 2.2: Complementar do grafo do Exemplo 2.1.1

Definição 2.1.3. Dizemos que G′(V ′,E ′) é um subgrafo de G(V,E) quando V ′ ⊆V e E ′ ⊆E, e neste caso escrevemos G′ ⊂G. No caso em que G′ é subgrafo de G tal que dois vérticesem V (G′) são adjacentes em G′ se, e somente se, eles são adjacentes em G, dizemos que G′

é subgrafo induzido de G e escrevemos G′ como G[V ′], pois trata-se do grafo original Grestrito a um conjunto de vértices.

Definição 2.1.4. Uma sequência finita de vértices distintos v1,v2, ...,vk de um grafo G édito um caminho de v1 a vk quando {vi,vi+1} ∈ E(G) para todos 1 ≤ i ≤ k − 1. Umcaminho fechado, isto é, um caminho acrescido da aresta {v1,vk}, é chamado de ciclo. Ocomprimento de um caminho ou de um ciclo é o número de arestas que neles ocorrem.

Indicamos por Pn e Cn respectivamente o caminho e o ciclo com n vértices.

Definição 2.1.5. Se dados quaisquer dois vértices u,v ∈ V (G), existe um caminho de u av, então dizemos que o grafo G é conexo, caso contrário o grafo é desconexo. Se G é um

grafo desconexo, dizemos que G′ ⊂ G é uma componente de G quando G′ é conexo e nãoexiste um grafo conexo H ⊂ G tal que G′ ⊂ H e G′ 6= H.

Figura 2.3: Na esquerda um grafo conexo e na direita um grafo desconexo com 2 compo-

nentes conexas.

Definição 2.1.6. Se G é um grafo conexo, definimos a distância entre os vértices v e u,

denotada por d(u,v), como o mı́nimo dos comprimentos dos caminhos entre os vértices ue v. O máximo das distâncias entre dois vértices quaisquer de G é o diâmetro do grafo, e

denotado por diam(G)

Definição 2.1.7. Um subconjunto X ⊂ V (G) é dito conjunto independente de vértices senão há par de vértices adjacentes no conjunto, ou seja, ∀v,u ∈ X, vu /∈ E(G). Por outrolado, se vu ∈ E(G) para todo u,v ∈ X então o conjunto é uma clique (induz um subgrafocompleto).

6

Definição 2.1.8. O número de independência de um grafo G, denotado por α = α(G), é otamanho do maior conjunto independente de G.

Definição 2.1.9. Uma clique máxima é a maior clique possı́vel em um dado grafo. O

número clique ω(G) de um grafo G é o número de vértices de uma clique máxima em G.

Definição 2.1.10. O número cromático χ = χ(G) de um grafo G é o menor número decores dadas aos vértices de G de forma que nenhum par de vértices adjacentes tenha a

mesma cor.

Apresentamos a seguir alguns tipos especiais de grafos.

•grafo trivial: é um grafo G tal que V (G) consiste em apenas um vértice e E(G) = Ø

•grafo r-regular: é qualquer grafo onde todos os vértices de G têm o mesmo grau r.

• grafo completo: é um grafos onde quaisquer dois vértices distintos são adjacentes. Ografo completo com n vértices é denotado por Kn

•Caminho: grafo formado por apenas um caminho de vértices. O caminho de n vértices édontado por Pn.

•Ciclo: grafo onde todas suas arestas e vértices fazem parte de um único ciclo. O ciclo den vértices é denotado por Cn.

• Árvore: s ão grafos conexos que não possuem ciclos.

Vamos apresentar agora a definição dos grafos aranha, que serão os grafos estudados

nestre trabalho.

Definição 2.1.11. [5] Um grafo G(V,E) é uma aranha se V (G) pode ser particionado emconjuntos K,L e R ,chamados respectivamente de corpo, pernas e cabeça da aranha, taisque:

• |K|= |L|> 2

• K = {c1, . . . ,ck} é uma clique;

• L = {l1, . . . , lk} é um conjunto independente;

• Todos os vértices de K são adjacentes aos de R e não há arestas entre os vértices deL e R.

• Entre K e L temos somente um dos casos abaixo:(i) ci é adjacente a l j ⇔ i = j, então o grafo é denominado aranha magra; ou(ii) ci é adjacente a l j ⇔ i 6= j, ∀ 1≤ i, j ≤ k, o grafo é chamado de aranha gorda.

Se R = Ø então a aranha é dita aranha magra (ou gorda) sem cabeça.

7

Um grafo do tipo aranha magra será denotado por Sm[k, j,G], onde seu corpo e suaspernas possuem k vértices cada um, a cabeça possui j vértices, e G é o subgrafo indu-

zido pela cabeça R. Analogamente Sg[k, j,G] representa a aranha gorda e denotaremos porS[k, j,G] quando quisermos nos referir a ambas. No caso das aranhas sem cabeça ( j = 0)denotaremos simplesmente por Sm[k] ou Sg[k].

Para facilitar a compreensão da definição de Aranha Magra e Gorda observe o exemplo

abaixo.

Exemplo 2.1.2. Nas figuras abaixo vemos a aranha magra onde o corpo e as pernas tem

cinco vértices (k=5), o subgrafo induzido pela cabeça é o grafo sem arestas com dois

vértices(j=2), e uma aranha gorda com k=3 e j=2 onde também temos G = K2 .

Figura 2.4: Sm[5,2,K2] e Sg[3,2,K2], respectivamente.

Veremos agora algumas propriedades estruturais dos grafos aranha, que seguem direto

da definição.

OBSERVAÇ ÃO 2.1.1. Sejam c e l, respectivamente, vértices arbitrários do corpo e da

perna. Podemos concluir direto da definição que todo grafo aranha S = S[k, j,G] satis-faz um, e somente um, dos casos abaixo:

• d(c) = |V |− |L|= (2k+ j)− k = k+ j e d(l) = 1, se S é aranha magra; ou

• d(c) = |V |−2 = 2k+ j−2 e d(l) = |K|−1 = k−1, se S é aranha gorda.

OBSERVAÇ ÃO 2.1.2. Todo grafo aranha é conexo, independente do grafo induzido pela

cabeça.

OBSERVAÇ ÃO 2.1.3. Sm[k, j,G] = Sg[k, j,G] e Sg[k, j,G] = Sm[k, j,G]. Daı́, se S é aranha,então S é conexo com complementar conexo.

8

OBSERVAÇ ÃO 2.1.4. Toda aranha magra é subgrafo de uma aranha gorda, com mesmo

número de vértices nas pernas, cabeça e corpo. Mais especificamente Sm[k, j,G]⊂ Sg[k, j,G],para qualquer k ≥ 2 e j ≥ 0.

Importantes classes de grafos são definidas por subgrafos proibidos (grafos que nunca

aparecem como subgrafos induzidos em certas classes de grafos). A classe dos cografos,

por exemplo, são grafos livres de P4, isto é, grafos que não admitem P4 como subgrafo

induzido. Esta classe contém os grafos threshold (grafos livres de 2K2, P4 e C4).

Estas duas classes possuem caracterı́sticas interessantes e foram bem estudadas, como

pode ser visto em [18], [19], [20], [21] e [22].

Em [4], Hoàng propôs uma generalização dos cografos, definindo os grafos P4-esparsos.

Definição 2.1.12. Um grafo G é um P4-esparso se qualquer subconjunto de cinco vértices

induz no máximo um subgrafo P4 em G.

Em [5], é apresentada uma caracterização dos grafos P4-esparsos, a partir dos grafos

aranha.

Teorema 2.1.1. [5] Seja G um grafo não trivial, então G é um P4-esparso se, e somente se

qualquer subgrafo induzido H de G com ao menos dois vértices satisfaz exatamente uma

das condições abaixo:

(i) H é desconexo;

(ii) H é desconexo;

(iii) H é uma aranha cuja cabeça, caso exista, induz um grafo P4-esparso.

Vale ressaltar que o subgrafo induzido H pode ser tomado como o próprio grafo G,

então, em particular, se G é P4-esparso ele deve satisfazer exatamente uma das condições

acima. Esta nova caracterização será de grande importância para o nosso resultado da seção

posterior.

• Nordhaus e Gaddum [6] estudaram o número cromático de um grafo G e de seucomplementar ao mesmo tempo. Eles provaram cotas superiores e inferiores na soma (e

produto) do número cromático de G e G em termos do número de vértices de G.

Desde então, qualquer desigualdade envolvendo parâmetros de um grafo G e seu grafo

complementar G ficaram conhecidas como Desigualdades do tipo Nordhaus-Gaddum.

Vamos mais adiante ver propriedades deste tipo para grafos aranha e, mais geralmente,

grafos P4-esparsos.

2.2 Álgebra Linear

Os teoremas abaixo serão necessários no decorrer do texto. Denotaremos por Mn o espaço

das matrizes reais quadradas de ordem n.

Os próximos três teoremas são conhecidos respectivamente como Teorema de Perron

Frobenius, Teorema do Entrelaçamento e Teorema das Partições Equilibradas.

Teorema 2.2.1. [7] Seja M ∈ Mn com entradas não negativas, irredutı́vel e autovaloresλ1 ≥ λ2 ≥ ...λn. Então:

9

(i) λ1 > 0 e tem multiplicidade 1 ;(ii) existe um autovetor positivo associado a λ1;(iii) | λi | ≤ λ1, para todo i ∈ {1,2, ...,n}.

OBSERVAÇ ÃO 2.2.1. As matrizes de adjacência, laplaciana sem sinal e distância (as quais

veremos na próxima seção) de um grafo G conexo são irredutı́veis e portanto satisfazem a

hipótese do teorema 2.2.1 acima.

Teorema 2.2.2. [2] Seja M ∈Mn uma matriz simétrica e N ∈Mn− j uma submatriz princi-pal de M. Então λi+1(M)≤ λi(N)≤ λi(M), para todo i ∈ {1,2, ...,n− j}, onde λi(M) sãoos autovalores de M e λi(N) são os autovalores de N.

Teorema 2.2.3. [2] Seja M ∈Mn tal que M é da forma:

M =

M1,1 M1,2 . . . M1,kM2,1 M2,2 . . . M2,k

......

...

Mk,1 Mk,2 . . . Mk,k

,

onde Mi, j, 1 ≤ i, j ≤ k, é uma matriz de ni × n j tal que suas linhas têm somas constantesiguais a ci j. Se M

′ = [ci j]k×k, então seus os autovalores também são autovalores de M.

O próximo resultado está relacionado com o teorema 2.2.3 acima e pode ser encontrado

em [3].

Proposição 2.2.1. [3] Seja M ∈Mn uma matriz que pode ser escrita em blocos como noTeorema 2.2.3. Chamemos a matriz formada pela soma das linhas de cada bloco de M′.Então o maior autovalor de M é também um autovalor de M′.

2.3 Teoria Espectral de grafos

Apresentaremos agora as matrizes que serão estudadas neste trabalho, a saber a matriz

laplaciana sem sinal e a matriz distância. Precisaremos antes, introduzir a matriz de ad-

jacência.

2.3.1 Matriz de adjacência

Definição 2.3.1. Seja G = G(V,E) um grafo com n vértices. A matriz de adjacência A(G)de G é a matriz quadrada de ordem n cujas entradas são

ai j =

{

1, se {vi,v j} ∈ E(G);0, caso contrário.

10

A matriz de adjacência é a representação matricial mais comum de um grafo. Ela é

formada por zeros e uns que indicam, naturalmente, se dois vértices são adjacentes ou não.

Definição 2.3.2. Definimos os autovalores de um grafo G com n vértices como os autova-

lores da matriz A(G), dados pelas raı́zes do polinômio caracterı́stico pG(x) = det(A(G)−xI). Denotaremos os n autovalores (não necessariamente distintos) de A(G) por λ1 ≥ λ2 ≥...≥ λn.

Definição 2.3.3. O espectro de um grafo G é definido como a matriz 2 x s, onde a primeira

linha é formada pelos autovalores distintos de A(G) ordenados de forma crescente e asegunda linha é formada pelas suas respectivas multiplicidades e é denotado por:

σ(G) =

(

λs λs−1 . . . λ2 λ1m(λs) m(λs−1) . . . m(λ2) m(λ1)

)

,

onde s ∈ {1,2, ...,n} é o número de autovalores distintos de A(G).O maior autovalor do grafo G é chamado de ı́ndice de G.

Exemplo 2.3.1. A matriz de adjacência, polinômio caracterı́stico e o espectro do grafo G

do Exemplo 2.1.1 são:

A(G) =

0 1 1 0 0

1 0 1 0 0

1 1 0 1 0

0 0 1 0 1

0 0 0 1 0

,

onde seu polinômio caracterı́stico é pG(x) =−x5 +5x3 +2x2 −4x−2 e seu espectro é

σ(G) =

(

−1,67513 −1 −0,53919 1 2,214321 1 1 1 1

)

.

Veremos agora algumas propriedades, que podemos obter direto da definição desta ma-

triz.

OBSERVAÇ ÃO 2.3.1. A matriz de adjacência é real e simétrica então ela é diagonalizável,

todos seus autovalores são reais e admite uma base ortogonal de autovetores.

OBSERVAÇ ÃO 2.3.2. Como o traço de A(G) é zero então seus autovalores somam zero.

OBSERVAÇ ÃO 2.3.3. Como A(G) é diagonalizável, então todo autovalor λi possui mul-tiplicidade algébrica igual à multiplicidade geométrica. Sendo as multiplicidades iguais,

chamaremos apenas de multiplicidade e denotaremos por m(λi).

OBSERVAÇ ÃO 2.3.4. Cada linha (ou coluna) da matriz se refere a um único vértice e a

soma dos elementos de cada linha (ou coluna) resulta no grau do vértice correspondente.

11

• A fim de fixar a notação, daqui em diante Jn denotará a matriz quadrada de ordem nonde todas as entradas valem 1, já a matriz nula será simbolizada por Θn e a identidade porIn. O vetor cujas entradas são 1 será denotado por~1n ∈Rn e o vetor nulo por~0n ∈Rn. Emcasos livres de ambiguidade a dimensão da matriz ou do vetor será omitida.

Proposição 2.3.1. [1] Seja G um grafo r-regular com n vértices.Então:

(i) r é um autovalor de G e está associado ao autovetor~1n.(ii) G é conexo ⇔ a multiplicidade de r é 1.

2.3.2 Matriz Laplaciana sem Sinal

Como dito anteriormente, esta matriz despertou interesse de pesquisadores a partir de 2007.

Desde então muitos artigos sobre ela foram publicados. Por exemplo, [11] e [12].

Definição 2.3.4. A matriz diagonal dos graus de um grafo G com n vértices é definida por

Deg(G) = diagonal(d(v1),d(v2), ...,d(vn)).

Definição 2.3.5. A matriz laplaciana sem sinal de um grafo G é definida por Q(G) =Deg(G)+A(G). De forma equivalente:

qi j =

1, se {viv j} ∈ E(G);d(vi), se i = j0, se {viv j} /∈ E(G).

O polinômio caracterı́stico da matriz laplaciana sem sinal é definido por pQ(x) =det(Q(G)− xI). Os autovalores laplacianos sem sinal de um grafo G com n vértices,obtidos de Q(G), são denotados por q1 ≥ q2 ≥ ...≥ qn. Seu espectro laplacino sem sinal(chamado também de Q-espectro) é definido analogamente ao espectro da matriz de ad-

jacência e será denotado por σQ(G).

Exemplo 2.3.2. A matriz laplaciana sem sinal do Exemplo 2.1.1 e seu espectro σQ são:

Q(G) =

2 1 1 0 0

1 2 1 0 0

1 1 3 1 0

0 0 1 2 1

0 0 0 1 1

,

onde seu polinômio caracterı́stico é pQ(x) =−x5 +10x4 −34x3 +48x2 −27x+4 e seuespectro é

σQ(G) =

(

0,22429 1 1,41078 2,72374 4,641191 1 1 1 1

)

.

12

OBSERVAÇ ÃO 2.3.5. Pelo teorema 2.2.1, temos que m(q1(G)) = 1 para qualquer grafo Gconexo.

Lema 2.3.1. [1] Para qualquer grafo G temos sempre que q1 ≥ q2 ≥ ...≥ qn ≥ 0.

O seguinte resultado será bastante usado no próximo capı́tulo e é consequência do Teo-

rema do entrelaçamento:

Teorema 2.3.1. [8] Seja G um grafo de n vértices e seja H um subgrafo de G obtido

removendo uma aresta em G. Então

q1(G)≥ q1(H)≥ q2(G)≥ q2(H)...≥ qn−1(G)≥ qn−1(H)≥ qn(g)≥ qn(H).

2.3.3 Matriz Distância

Esta matriz será o foco principal deste trabalho.

Definição 2.3.6. Seja G = G(V,E) um grafo conexo com n vértices tal que para todosvi,v j ∈V , d(vi,v j) = di j é a distância entre os vertices vi e v j. A matriz distância D(G) dografo G é a matriz quadrada de ordem n em que as linhas e colunas são indexadas pelos

vértices de G e cuja entrada correspondente a (vi,v j) é dada pelo valor di j.

O polinômio caracterı́stico da matriz distância de um grafo G com n vértices é deno-

tado por pD(x) = det(D(G)−xI) e seus autovalores são denotados por ∂1 ≥ ∂2 ≥ ...≥ ∂n.Seu espectro distância (chamado também de D-espectro) é denotado por σD(G) e é defi-nido de forma análoga aos casos anteriores.

Exemplo 2.3.3. A matriz distância e seu espectro σD do Exemplo 2.1.1 são:

D(G) =

0 1 1 2 3

1 0 1 2 3

1 1 0 1 2

2 2 1 0 1

3 3 2 1 0

,

onde seu polinômio caracterı́stico é pD(x) =−x5+35x3+88x2+74x+20 e seu espec-tro é

σD(G) =

(

−4,26261 −1,17742 −1 −0,56858 7,008611 1 1 1 1

)

.

OBSERVAÇ ÃO 2.3.6. Como o traço de D(G) é zero, existem autovalores positivos e nega-tivos para qualquer grafo G não trivial.

OBSERVAÇ ÃO 2.3.7. Pelo teorema 2.2.1, temos que m(∂1) = 1.

13

Definição 2.3.7. A transmissão de um vértice v, denotada por Tr(v), é a soma das distânciasde v para todos os outros vértices de G. Em outras palavras:

Tr(v) = ∑u∈V

d(u,v)

Denotaremos por Tr1(G) a maior transmissão do grafo G.

Agora veremos alguns resultados que serão necessários posteriormente. Primeiro ob-

temos um resultado que relaciona os espectros da matriz distância e matriz de adjacência

de um grafo r-regular de diamêtro 2. No outro resultado relacionamos ∂1(G) com a trans-missão máxima Tr1(G).

Lema 2.3.2. Se G é um grafo conexo, r-regular e de diamêtro 2 com n vértices, então

(2n-r-2) é um autovalor de D(G) associado ao autovetor~1n ∈Rn.

Demonstração. Pela definição da matriz distância, temos que se G é um grafo de diamêtro

2 então D(G) = 2J−A(G)−2I.Como G é um grafo r-regular, temos pela Proposição 2.3.1 que A(G).~1 = r~1

Portanto, D(G).~1 = 2J.~1−A(G).~1−2I.~1 = (2n− r−2)~1.

Lema 2.3.3. [13] Seja G um grafo conexo. Temos que ∂1 ≤ Tr1(G).

14

Capı́tulo 3

Matriz laplaciana sem sinal

Neste capı́tulo vamos estudar o Q-espectro de grafos na classe das aranhas. A partir desses

resultados obteremos uma propriedade do tipo Nordhaus-Gaddum para grafos P4-esparsos.

Observe que podemos rotular os vértices de uma aranha qualquer de forma que a matriz

laplaciana sem sinal (e distância) de (S[k, j,G]) seja escrita em blocos que expressem asseguintes relações:

corpo x corpo corpo x perna corpo x cabeça

perna x corpo perna x perna perna x cabeça

cabeça x corpo cabeça x perna cabeça x cabeça

OBSERVAÇ ÃO 3.0.1. Toda vez que escrevermos qualquer matriz de uma aranha, ela estará

nessa forma. Caso a aranha não tenha cabeça, removemos os blocos da última coluna e

da última linha.

3.1 Q-Espectro de aranhas com cabeças especiais

Nesta seção estudamos o Q-espectro de aranhas magras e gordas considerando o sub-grafo

induzido pela cabeça como K j, K j e ainda a cabeça vazia.

As proposições 3.1.1, 3.1.2, 3.1.3 a seguir fornecem o Q-espectro das aranhas ma-

gras para essas três cabeças. Nos três casos usamos as mesmas técnicas para obtenção

do Q-espectro, o Teorema 2.2.3 (Partições Equilibradas). A parte mais trabalhosa das

demonstrações refere-se à ordenação dos autovalores.

Proposição 3.1.1. Seja Sm[k], aranha magra sem cabeça (j=0) com k ≥ 2. Então seuespectro laplaciano sem sinal está determinado da seguinte forma:

σQ(Sm[k]) =

k−√

k2−4(k−2)2 k−

√k2 −2k+2 k+

√k2−4(k−2)

2 k+√

k2 −2k+2

k−1 1 k−1 1

Demonstração. Como o grau dos vértices do corpo é k, das pernas é 1, então a matriz

laplaciana sem sinal Q(Sm[k]), que vamos denotar somente por Q, é dada por:

15

k 1 . . . 1 | 1 0 . . . 01 k . . . 1 | 0 1 . . . 0...

.... . .

... | ... ... . . . ...1 1 . . . k | 0 0 . . . 1

−− −− −− −− −− −− −− −−1 0 . . . 0 | 1 0 . . . 00 1 . . . 0 | 0 1 . . . 0...

.... . .

... | ... ... . . . ...0 0 . . . 1 | 0 0 . . . 1

Esta matriz pode ser reescrita como uma matriz em blocos:

Q =

[

(k−1)Ik +Jk IkIk Ik

]

,

Observe que todas as matrizes blocos que compõem a matriz Q somam, em suas linhas,

o mesmo valor para cada bloco. Assim consideremos a matriz Q′2x2 cujas entradas são taissomas:

Q′ =(

2k−1 11 1

)

.

Temos que o polinômio caracterı́stico de Q′ é dado por

pQ′(x) = x2 −2kx+2k−2,

cujas raizes são k −√

k2 −2k+2 e k +√

k2 −2k+2, que também são autovalores de Qpelo teorema 2.2.3.

Afirmação 01: Temos que k−√

k2−4k+82 e

k+√

k2−4k+82 são autovalores de Q com multi-

plicidade k-1.

Para não sobrecarregar a escrita faremos a substituição b = k2 −4k+8.De fato, pela definição de aranha, seu corpo deve possuir ao menos dois vértices (ou

seja, k ≥ 2) então podemos tomar u ∈ Rk perpendicular a ~1k e considerar o vetor w =[

u−k+2+

√b

2 u

]

em R2k. Logo

Q.w = Q.

[

u−k+2+

√b

2 u

]

=

[

(k−1)u+(−k+2+√

b2 )u

u+(−k+2+√

b2 )u

]

=

=

[

k+√

b2 u

−k+4+√

b2 u

]

=k+

√b

2

[

u−k+2+

√b

2 u

]

=k+

√b

2.w

Portanto k+√

b2 =

k+√

k2−4k+82 é autovalor do grafo com multiplicidade ao menos k−1

(pois existem k−1 vetores linearmente independentes do Rk perpendiculares a~1k).

Com procedimento semelhante podemos concluir que k−√

b2 =

k−√

k2−4k+82 é autovalor

com multiplicidade ao menos k−1, referente ao autovetor w =[

u−k+2−

√b

2 u

]

∈R2k.

16

Além disso, como já temos dois autovalores de Q com multiplicidade ao menos k−1,outros dois com multiplicidade ao menos 1 e a soma das multiplicidades tem que ser 2k,

então só podem valer as igualdades. Assim o Q-espectro está determinado, vamos agora

ordenar os Q-autovalores.

Afirmação 02: Temos para todo k ≥ 2 que: k−√

k2−4k+82 < k−

√k2 −2k+2.

De fato, isso vale se, e somente se: −√

k2 −4k+8 < k−2√

k2 −2k+2⇔ 2

√k2 −2k+2 < k+

√k2 −4k+8

⇔(elevando ao quadrado) 4k2 −8k+8 < 2k2 −4k+8+2k√

k2 −4k+8⇔ 2k2 < 4k+2k

√k2 −4k+8

⇔ 2k−4 < 2√

k2 −4k+8⇔(elevando ao quadrado) 4k2 −16k+16 < 4k2 −16k+32⇔ 16 < 32

Afirmação 03: Temos para todo k ≥ 2 que k−√

k2 −2k+2 < k+√

k2−4k+82 .

De fato, isso vale se, e somente se: k−2√

k2 −2k+2 <√

k2 −4k+8⇔ k < 2

√k2 −2k+2+

√k2 −4k+8

⇔ (elevando ao quadrado) 0 < 4k2 −12k+16+4√

(k2 −2k+2)(k2−4k+8),O que sempre vale para k ≥ 2.

Daı́, e como temos que k+√

k2 −2k+2 é o maior autovalor de Q pela proposição 2.2.1,concluimos a demonstração.

Proposição 3.1.2. Consideremos Sm[k, j,K j] com k ≥ 2 e j ≥ 1. Então seu espectro lapla-ciano sem sinal está determinado da seguinte forma:

σQ(Sm[k, j,K j]) =

ϕ3k+ j−

√(k+ j)2−4(k+ j−2)

2 ϕ2 kk+ j+

√(k+ j)2−4(k+ j−2)

2 ϕ1

1 k−1 1 j−1 k−1 1

no caso de k ≤ j;

σQ(Sm[k, j,K j]) =

k+ j−√

(k+ j)2−4(k+ j−2)2 ϕ3 ϕ2 k

k+ j+√

(k+ j)2−4(k+ j−2)2 ϕ1

k−1 1 1 j−1 k−1 1

no caso de k > j.Onde, nos dois casos, ϕ3 ≤ ϕ2 ≤ ϕ1 são as raı́zes do polinômio:

pQ′(x) =−x3 +(3k+ j)x2 +(−2k2 −2k− j+2)x+2k2 −2k.

Demonstração. Como o grau dos vértices do corpo é k+ j, das pernas é 1 e da cabeça ék, então a matriz laplaciana sem sinal Q(Sm[k, j,K j]), que vamos denotar somente por Q, édada por:

17

k+ j 1 . . . 1 | 1 0 . . . 0 | 1 1 . . . 11 k+ j . . . 1 | 0 1 . . . 0 | 1 1 . . . 1...

.... . .

... | ... ... . . . ... | ... ... . . . ...1 1 . . . k+ j | 0 0 . . . 1 | 1 1 . . . 1

−− −− −− −− −− −− −− −− −− −− −− −− −−1 0 . . . 0 | 1 0 . . . 0 | 0 0 . . . 00 1 . . . 0 | 0 1 . . . 0 | 0 0 . . . 0...

.... . .

... | ... ... . . . ... | ... ... . . . ...0 0 . . . 1 | 0 0 . . . 1 | 0 0 . . . 0

−− −− −− −− −− −− −− −− −− −− −− −− −−1 1 . . . 1 | 0 0 . . . 0 | k 0 . . . 01 1 . . . 1 | 0 0 . . . 0 | 0 k . . . 0...

.... . .

... | ... ... . . . ... | ... ... . . . ...1 1 . . . 1 | 0 0 . . . 0 | 0 0 . . . k


Q =

(k+ j−1)Ik +Jk Ik Jk, jIk Ik Θk, jJ j,k Θ j,k kI j

,



Q′ =

2k+ j−1 1 j1 1 0

k 0 k

.

Então, pelo Teorema 2.2.3, garantimos que os autovalores de Q′ também são autovaloresda matriz Q. Denotamos por ϕ3 ≤ ϕ2 ≤ ϕ1 os três autovalores distintos de Q′, que são asraizes do polinômio caracterı́stico pQ′ , dado por:

pQ′(x) =−x3 +(3k+ j)x2 +(−2k2 −2k− j+2)x+2k2 −2k

Embora não seja possı́vel explicitar os valores de ϕ3, ϕ2, ϕ1 em função de k e j, vamosachar os outros autovalores explicitamente e ordená-los, estudando os sinais de pQ′ .

Afirmação 01: Se j ≥ 2, então k é um autovalor de Q com multiplicidade ao menos j-1.

De fato, se j ≥ 2 então podemos tomar u ∈ R j ortogonal a ~1 j e construir o vetor

v =

~0k~0ku

∈ R2k+ j. Observe que Q.v = k.v, daı́ temos que k é autovalor da matriz Q

correspondente ao autovetor v ∈R2k+ j . Como existem j−1 vetores linearmente indepen-dentes do R j perpendiculares a~1 j, então k é autovalor de Q com multiplicidade ao menosj− 1. Se a cabeça só tiver um vértice ( j = 1) o vetor u não existe e consequentemente knão é autovalor.

18

Afirmação 02:k+ j−

√(k+ j)2−4(k+ j−2)

2 ek+ j+

√(k+ j)2−4(k+ j−2)

2 são autovalores de Q

com multiplcidade ao menos k-1.

De fato, pela definição de aranha, seu corpo deve possuir ao menos dois vértices (ou

seja, k ≥ 2) então podemos tomar u ∈ Rk perpendicular à ~1 e considerar o vetor w =

u−(k+ j−2)−

√(k+ j)2−4(k+ j−2)

2 u~0 j

em R2k+ j.

Para não sobrecarregar a escrita faremos as substituições a = k+ j−2 e b = (k+ j)2 −4(k+ j−2).

Q.w = Q.

u

−(a+√

b2 )u

~0 j

=

(k+ j+1)u− (a+√

b2 )u+

~0k

u− (a+√

b2 )u+

~0k~0 j

=

=

a+2−√

b2 u

−a+2−√

b2 u~0 j

=

a+2−√

b

2

u

−(a+√

b2 )u

~0 j

=a+2−

√b

2.w

Portanto a+2−√

b2 =

k+ j−√

(k+ j)2−4(k+ j−2)2 é autovalor do grafo com multiplicidade ao me-

nos k−1.

Com procedimento semelhante podemos concluir que a+2+√

b2 =

k+ j+√

(k+ j)2−4(k+ j−2)2

é autovalor com multiplicidade ao menos k−1, referente ao autovetor w =

u−a+

√b

2 u~0 j

∈

R2k+ j.

Afirmação 03: m

(

k+ j−√

(k+ j)2−4(k+ j−2)2

)

=m

(

k+ j+√

(k+ j)2−4(k+ j−2)2

)

= k−1 e m(k)=j−1

Considerando as multiplicidades mı́nimas para os autovalores apresentados nas afirmações

(1) e (2), além dos três autovalores obtidos incialmente, obtemos todos os 2k+ j autovalo-res procurados (basta notar que 2(k−1)+( j−1)+3 = 2k+ j).

Passaremos agora a ordernação dos autovalores de Q.

Afirmação 04:Temosk+ j−

√(k+ j)2−4(k+ j−2)

2 < k <k+ j+

√(k+ j)2−4(k+ j−2)

2 < ϕ1 para to-dos k ≥ 2, j ≥ 1.

A desiguldade da direita vem direto da proposição 2.2.1, que garante que ϕ1 é o maiorautovalor de Q. Além disto,

• k < k+ j+√

(k+ j)2−4(k+ j−2)2 ⇔ 0

O que é verdade, pois:

−k + j +√

(k+ j)2−4(k+ j−2) = −k + j +√

(k+ j)2−4(k+ j)+8 > −k + j +√

(k+ j)2 −4(k+ j)+4 = −k + j+√

[(k+ j)−2]2 = −k + j + k+ j − 2 = 2 j− 2 ≥ 0,para todo j ≥ 1.

• k+ j−√

(k+ j)2−4(k+ j−2)2 < k ⇔ 0 < k− j+

√

(k+ j)2 −4(k+ j−2)

O que é verdade, pois:

k− j+√

(k+ j)2 −4(k+ j−2)> k− j+√

[(k+ j)−2]2 = 2k−2> 0, para todo k ≥ 2.

Vamos agora ordenar os outros autovalores no caso k ≤ j.

Afirmação 05: Existe pelo menos uma raiz de pQ′ entre os autovaloresk+ j−

√(k+ j)2−4(k+ j−2)

2

e k.

De fato, para isso basta mostrar que pQ′

(

k+ j−√

(k+ j)2−4(k+ j−2)2

)

e pQ′(k) tem sinais

distintos.

Com uma conta simples, vemos que

pQ′(k) = k3 − k2 > 0

Por outro lado,

pQ′

(

k+ j−√

(k+ j)2 −4(k+ j−2)2

)

=

√

(k+ j)2 −4(k+ j−2)2

(−2k j+ k)+ k2 j− k2

2+ k j2 − 5k j

2+2k

Logo,

pQ′

(

k+ j−√

(k+ j)2 −4(k+ j−2)2

)

< 0

se, e somente se,

k2 j− k2

2+ k j2 − 5k j

2+2k <

√

(k+ j)2 −4(k+ j−2)2

(−2k j+ k)

Elevando ambos os lados ao quadrado, obtemos que a desigualdade acima vale se, e

somente se,

0

Temos que pQ′(0) = 2k2 −2k > 0 ,pois k ≥ 2. Como

pQ′

(

k+ j−√

(k+ j)2−4(k+ j−2)2

)

< 0, temos que existe uma raiz entre esses dois valores.

Pela afirmação 05, existe outra raiz entrek+ j−

√(k+ j)2−4(k+ j−2)

2 e k. Disto e das afirmações

(4) e (5), essas raizes só podem ser ϕ3 e ϕ2, respectivamente, e temos o espectro totalmenteordenado para o caso k ≤ j.

Agora vamos ordenar os autovalores obtidos no caso k > j.

Afirmação 07: pQ′

(

k+ j−√

(k+ j)2−4(k+ j−2)2

)

> 0 para k > j

Temos pelas mesmas contas da afirmação (5) que:

pQ′

(

k+ j−√

(k+ j)2−4(k+ j−2)2

)

> 0 ⇔ 0 < 2k j− k−2 j2 − j+2

Definimos f (k) = 2k j− k−2 j2 − j+2. Então, f ′(k) = 2 j−1 > 0 para todo j ≥ 1.

Logo f é crescente em relação à variável k. Como k > j é um número inteiro, então omenor valor para k é k = j+1. Portanto basta mostrarmos que f ( j+1)> 0 para mostrarmosque f (k)> 0 para todo k > j. E de fato:

f ( j+1) = 2 j( j+1)− j−1−2 j2 − j+2 = 2 j2 +2 j−2 j2 −2 j+1 = 1 > 0

Afirmação 08: Para k > j vale que:k+ j−

√(k+ j)2−4(k+ j−2)

2 < ϕ3 < ϕ2 < k, valendo as-sim a proposição.

Notemos primeiro quek+ j−

√(k+ j)2−4(k+ j−2)

2 < 1Além disso, como pQ′(0)> 0, pQ′(1)< 0 e pQ′(k)> 0 temos que:

0 < ϕ3 < 1 < ϕ2 < k

Daı́ e pelas afirmações 04 e 07, só podemos ter

0 <k+ j−

√

(k+ j)2 −4(k+ j−2)2

< ϕ3 < 1 < ϕ2 < k

Concluı́mos assim a ordenação para o caso k > j e, consequentemente, a proposição.

OBSERVAÇ ÃO 3.1.1. Para mostrar a afirmação 02 na Proposição 3.1.2 acima, não usamos

em nenhum momento o bloco cabeça x cabeça da matriz Q. Logo essa afirmação vale para

QUALQUER aranha magra, independente da cabeça (pois todos os blocos menos o bloco

cabeça x cabeça são iguais em qualquer aranha magra).

21

Proposição 3.1.3. Seja Sm[k, j,K j], com k ≥ 2 e j ≥ 1. Então seu espectro laplaciano semsinal está determinado da seguinte forma:

σQ(Sm[k, j,K j]) =

k+ j−√

(k+ j)2−4(k+ j−2)2 ϕ3 k+ j−2 ϕ2

k+ j+√

(k+ j)2−4(k+ j−2)2 ϕ1

k−1 1 j−1 1 k−1 1

Onde ϕ3 ≤ ϕ2 ≤ ϕ1 são as raı́zes do polinômio:pQ′(x) =−x3 +(3k+3 j−2)x2 +(−2k2 −4k j+2k−2 j2 + j+2)x+2k2 +4k j−6k+2 j2 −6 j+4

.

Demonstração. Como o grau dos vértices do corpo é k+ j, das pernas é 1 e da cabeça ék+ j− 1, então a matriz laplaciana sem sinal Q(Sm[k, j,K j]), que vamos denotar somentepor Q, pode ser escrita em bloco, como abaixo.

Q =

(k+ j−1)Ik +Jk Ik Jk, jIk Ik Θk, jJ j,k Θ j,k (k+ j−2)I j +J j

,

Como as matrizes blocos que compõem a matriz Q somam, em suas linhas, o mesmo

valor para cada bloco. Consideremos, como anteriormente, a matriz Q′3x3 cujas entradassão tais somas:

Q′ =

2k+ j−1 1 j1 1 0

k 0 k+2 j−2

.

Então, pelo Teorema 2.2.3, garantimos que os autovalores ϕ3 ≤ ϕ2 ≤ ϕ1 de Q′ também sãoautovalores da matriz Q. Esses são as raizes do polinômio caracterı́stico de Q′, dado por:

pQ′(x) =−x3 +(3k+3 j−2)x2 +(−2k2 −4k j+2k−2 j2 + j+2)x+2k2 +4k j−6k+2 j2 −6 j+4

Afirmação 01: Se j ≥ 2, então k + j − 2 é um autovalor de Q com multiplicidade aomenos j-1.

De fato, se j ≥ 2 então podemos tomar u ∈ R j ortogonal a ~1 j (logo u.J jx j = 0) e

construir o vetor v =

~0k~0ku

∈R2k+ j. Observe que

Q.v =

~0k~0k

u.[(k+ j−2)I+J] jx j

= (k+ j−2).v,

daı́ temos que k+ j−2 é autovalor da matriz Q correspondente ao autovetor v ∈R2k+ j.

Afirmação 02:k+ j−

√(k+ j)2−4(k+ j−2)

2 ek+ j+

√(k+ j)2−4(k+ j−2)

2 são autovalores de Q

com multiplcidade ao menos k-1.

22

Já vimos que isso vale para toda aranha magra (Observação 3.1.1).

Afirmação 03: m

(

k+ j−√

(k+ j)2−4(k+ j−2)2

)

=m

(

k+ j+√

(k+ j)2−4(k+ j−2)2

)

= k−1 e m(k+j−2) = j−1

A demonstração é igual a da afirmação 03 anterior.

Afirmação 04:Temosk+ j−

√(k+ j)2−4(k+ j−2)

2 < k+ j−2 <k+ j+

√(k+ j)2−4(k+ j−2)

2 < ϕ1para todos k ≥ 2, j ≥ 1.

• A desiguldade da direita vem direto da proposição 2.2.1.

• k+ j−2 < k+ j+√

(k+ j)2−4(k+ j−2)2 ⇔ 0 −k− j+4+√

[(k+ j)−2]2 = 2 > 0

• k+ j−√

(k+ j)2−4(k+ j−2)2 < k+ j−2 ⇔ 0 < k+ j−4+

√

(k+ j)2 −4(k+ j−2)O que é verdade, pois:

k+ j−4+√

(k+ j)2 −4(k+ j−2)> k+ j−4+√

[(k+ j)−2]2 = 2k+2 j−6 ≥ 0para todos k ≥ 2, j ≥ 1.

Afirmação 05: Existe pelo menos uma raiz de pQ′ entre os autovaloresk+ j−

√(k+ j)2−4(k+ j−2)

2

e k+ j−2.

Com uma conta relativamente simples, vemos que

pQ′(k+ j−2) =−k j− j2 +2 j < 0

Por outro lado, temos que

pQ′

(

k+ j−√

(k+ j)2 −4(k+ j−2)2

)

=

√

(k+ j)2−4(k+ j−2)2

.(−k)+ k2

2+

k j

2

Logo

pQ′

(

k+ j−√

(k+ j)2 −4(k+ j−2)2

)

> 0

se, e somente se,k

2+

j

2>

√

(k+ j)2 −4(k+ j−2)2

Multiplicando por 2 e elevando ambos os lados ao quadrado, obtemos que a desigual-

dade acima vale se, e somente se,

(k+ j)2 > (k+ j)2 −4(k+ j−2)⇔ 4(k+ j−2)> 0,o que é sempre verdade.

23

Afirmação 06: Existe pelo menos uma raiz de pQ′ entre os autovalores k + j − 2 ek+ j+

√(k+ j)2−4(k+ j−2)

2 .

Já vimos que

pQ′(k+ j−2)< 0Já por um cálculo maior, achamos que

pQ′

(

k+ j+√

(k+ j)2 −4(k+ j−2)2

)

=

√

(k+ j)2 −4(k+ j−2)2

(k)+k2

2+

k j

2,

que só tem termos positivos, logo é sempre maior do que zero.

Como pQ′ só tem 3 autovalores distintos e ϕ1 é o maior autovalor de Q, então só pode-mos ter ϕ3 como o autovalor da afirmação 05 e ϕ2 o autovalor da afirmação 06.

Apresentamos agora as três proposições para aranhas gordas, análogas às anteriores.

OBSERVAÇ ÃO 3.1.2. Note que para k = 2 (e qualquer grafo G) temos que Sm[k, j,G] =Sg[k, j,G]. Logo, sem perda de generalidade, vamos considerar k ≥ 3 para aranhas gordas.

Proposição 3.1.4. Seja Sg[k], aranha gorda sem cabeça (j=0) e com k ≥ 3. Então seuespectro laplaciano sem sinal está determinado da seguinte forma:

σQ(Sg[k]) =

(2−√

2)(k−1) 3k−4−√

k2−4(k−2)2

3k−4−√

k2−4(k−2)2 (2+

√2)(k−1)

1 k−1 k−1 1

Demonstração. Como o grau dos vértices do corpo é k, das pernas é 1 , então a matriz

laplaciana sem sinal Q(Sm[k]), que vamos denotar somente por Q, é dada por:

2k−2 1 . . . 1 | 0 1 . . . 11 2k−2 . . . 1 | 1 0 . . . 1...

.... . .

... | ... ... . . . ...1 1 . . . 2k−2 | 1 1 . . . 0

−− −− −− −− −− −− −− −−0 1 . . . 1 | k−1 0 . . . 01 0 . . . 1 | 0 k−1 . . . 0...

.... . .

... | ... ... . . . ...1 1 . . . 0 | 0 0 . . . k−1


Q =

[

(2k−3)Ik +Jk Jk − IkJk − Ik (k−1)Ik

]

,

24



Q′ =

(

3k−3 k−1k−1 k−1

)

.

Temos que o polinômio caracterı́stico de Q′ é dado por

pQ′(x) = x2 +(−4k+4)x+2k2 −4k+2

cujas raizes são (2−√

2)(k−1) e (2+√

2)(k−1), que também são autovalores de Qpelo Teorema 2.2.3.

Afirmação 01: Temos que 3k−4−√

k2−4k+82 e

3k−4+√

k2−4k+82 são autovalores de Q com

multiplicidade k-1.

Para não sobrecarregar a escrita faremos a substituição b = k2 −4k+8.De fato, pela definição de aranha, seu corpo deve possuir ao menos dois vértices (ou

seja, k ≥ 2) então podemos tomar u ∈ Rk perpendicular à ~1 e considerar o vetor w =[

uk−2−

√b

2 u

]

em R2k. Logo

Q.w = Q.

[

uk−2−

√b

2 u

]

=

[

(2k−3)u− ( k−2−√

b2 )u

−u+(k−1)( k−2−√

b2 )u

]

=

=

[

3k−4+√

b2 u

k2−3k−(k−1)√

b2 u

]

=3k−4+

√b

2

[

uk−2−

√b

2 u

]

=3k−4+

√b

2.w

Portanto 3k−4+√

b2 =

3k−4+√

k2−4k+82 é autovalor do grafo com multiplicidade ao menos

k−1.Com procedimento semelhante podemos concluir que 3k−4−

√b

2 =3k−4−

√k2−4k+82 é au-

tovalor com multiplicidade ao menos k−1, referente ao autovetor w=[

uk−2+

√b

2 u

]

∈R2k.

Afirmação 02: Temos para todo k ≥ 3 que (2−√

2)(k−1)< 3k−4−√

k2−4(k−2)2

De fato, isso vale se, e somente se (4−2√

2)(k−1)< 3k−4−√

k2 −4(k−2)⇔√

k2 −4(k−2)< (2√

2−1)k−2√

2

⇔(elevando ao quadrado) 0 < (8−4√

2)k2 +(4√

2−12)k

Como as raı́zes do polinômio f (k) = (8−4√

2)k2 +(4√

2−12)k são 0 e 3−√

2

2−√

2, vemos

que f (k)> 0 para k ≥ 3 > 3−√

2

2−√

2.

Valendo assim a afirmação 02 e consequentemente a proposição.

Proposição 3.1.5. Seja Sg[k, j,K j] com k ≥ 3 e j ≥ 1. Então seu espectro laplaciano semsinal está determinado da seguinte forma:

25

σQ(Sg[k, j,K j]) =

ϕ33k+ j−4−

√(k+ j)2−4(k+ j−2)

2 ϕ2 k3k+ j−4+

√(k+ j)2−4(k+ j−2)

2 ϕ1

1 k−1 1 j−1 k−1 1

Onde ϕ3 ≤ ϕ2 ≤ ϕ1 são as raı́zes do polinômio:

pQ′(x) =−x3 +(5k+ j−4)x2 +(−6k2 − k j+8k+ j−2)x+2k3 −4k2 +2k.

Demonstração. Como o grau dos vértices do corpo é 2k+ j − 2, das pernas é k− 1 e dacabeça é k, então a matriz laplaciana sem sinal Q(Sg[k, j,K j]), que vamos denotar somentepor Q, é dada por:

2k+ j−2 1 . . . 1 | 0 1 . . . 1 | 1 1 . . . 11 2k+ j−2 . . . 1 | 1 0 . . . 1 | 1 1 . . . 1...

.... . .

... | ... ... . . . ... | ... ... . . . ...1 1 . . . 2k+ j−2 | 1 1 . . . 0 | 1 1 . . . 1

−− −− −− −− −− −− −− −− −− −− −− −− −−0 1 . . . 1 | k−1 0 . . . 0 | 0 0 . . . 01 0 . . . 1 | 0 k−1 . . . 0 | 0 0 . . . 0...

.... . .

... | ... ... . . . ... | ... ... . . . ...1 1 . . . 0 | 0 0 . . . k−1 | 0 0 . . . 0

−− −− −− −− −− −− −− −− −− −− −− −− −−1 1 . . . 1 | 0 0 . . . 0 | k 0 . . . 01 1 . . . 1 | 0 0 . . . 0 | 0 k . . . 0...

.... . .

... | ... ... . . . ... | ... ... . . . ...1 1 . . . 1 | 0 0 . . . 0 | 0 0 . . . k


Q =

(2k+ j−3)Ik +Jk Jk − Ik Jk, jJk − Ik (k−1)Ik Θk, jJ j,k Θ j,k kI j

,

Novamente consideremos a matriz 3x3 onde cada entrada é o valor da soma da linha de

cada bloco, onde pelo Teorema 2.2.3 temos que os autovalores dessa matriz também serão

autovalores de Q.

Q′ =

3k+ j−3 k−1 jk−1 k−1 0

k 0 k

.

Denotaremos por ϕ3 ≤ ϕ2 ≤ ϕ1 os 3 autovalores de Q’, que são as raizes do polinômiocaracterı́stico de Q’ dado por:

pQ(x) =−x3 +(5k+ j−4)x2 +(−6k2 − k j+8k+ j−2)x+2k3 −4k2 +2k

Afirmação 01: Se j ≥ 2, então k é um autovalor de Q com multiplicidade ao menos j-1.

26

A demonstração é a mesma da proposição 3.1.2, tendo em conta que o bloco cabeça xcabeça é o único usado na prova.

Afirmação 02:3k+ j−4−

√(k+ j)2−4(k+ j−2)

2 e3k+ j−4+

√(k+ j)2−4(k+ j−2)

2 são autovalores

de Q com multiplcidade ao menos k-1.


seja, k ≥ 2) então podemos tomar u ∈ Rk perpendicular à ~1 e considerar o vetor w =

u(k+ j−2)+

√(k+ j)2−4(k+ j−2)

2 u~0 j

em R2k+ j.

Para não sobrecarregar a escrita faremos as substituições a = k+ j−2, b = (k+ j)2 −4(k+ j−2).

Q.w = Q.

ua+

√b

2 u~0 j

=

(2k+ j−3)u− (a+√

b2 )u+

~0k

−u+(k−1)(a+√

b2 )u+

~0k~0 j

=

=

3k+ j−4−√

b2 u

k2+k j−3k− j+(k−1)√

b2 u~0 j

=

3k+ j−4−√

b

2

ua+

√b

2 u~0 j

=3k+ j−4−

√b

2.w

Portanto 3k+ j−4−√

b2 =

3k+ j−4−√

(k+ j)2−4(k+ j−2)2 é autovalor do grafo com multiplicidade

ao menos k−1.Com procedimento semelhante podemos concluir que 3k+ j−4+

√b

2 =3k+ j−4+

√(k+ j)2−4(k+ j−2)

2

é autovalor com multiplicidade ao menos k−1, do autovetor w =

ua−

√b

2 u~0 j

∈R2k+ j.

Afirmação 03: m

(

3k+ j−4−√

(k+ j)2−4(k+ j−2)2

)

= m

(

3k+ j−4+√

(k+ j)2−4(k+ j−2)2

)

= k−1 e m(k) = j−1

Prova igual aos casos anteriores.

Afirmação 04:Temos3k+ j−4−

√(k+ j)2−4(k+ j−2)

2 < k <3k+ j−4+

√(k+ j)2−4(k+ j−2)


De fato:3k+ j−4−

√

(k+ j)2 −4(k+ j−2)2

< k

⇔

0 −k− j+4+√

[(k+ j)−2]2 = 2

27

Já a desigualdade do meio vale ⇔

0 < k+ j−4+√

(k+ j)2 −4(k+ j)+8)

o que é verdade pelo mesmo argumento usado acima.

Já a desigualdade da direita é verdade pela proposição 2.2.1.

Afirmação 05: Existe pelo menos uma raiz de pQ′ entre os autovalores k e

3k+ j−4−√

(k+ j)2−4(k+ j−2)2 , para k ≥ 3 e j ≥ 1.

• Sem dificuldade pode-se confirmar que pQ′(k) = k j, logo temos que pQ′(k)> 0 parak ≥ 3, j ≥ 1

• Com maior dificuldade, confirmamos que

pQ′

(

3k+ j−4−√

(k+ j)2−4(k+ j−2)2

)

=

√(k+ j)2−4(k+ j)+8)

2 (−2k2 −2k j+5k)+ k3 +2k2 j−112 k

2 + k j2 − 92k j+8k

Vamos mostrar que pQ′

(

3k+ j−4−√

(k+ j)2−4(k+ j−2)2

)

< 0 para k ≥ 3 e j ≥ 1.

Multiplicando a desigualdade acima por 2k, obtemos:

(i)√

(k+ j)2−4(k+ j)+8)(−2k−2 j+5)+2k2+4k j−11k+2 j2 −9 j+16 < 0

⇔√

(k+ j)2 −4(k+ j)+8)(2k+2 j−5)−2k2−4k j+11k−2 j2 +9 j−16 > 0

O que de fato ocorre:

√

(k+ j)2 −4(k+ j)+8)(+2k+2 j−5)−2k2−4k j+11k−2 j2 +9 j−16 >√

[(k+ j)−2]2(2k+2 j−5)−2k2−4k j+11k−2 j2+9 j−16 = (k+ j−2)(2k+2 j−5)−2k2−4k j+11k−2 j2 +9 j−16 = (2k2+2k j−4k+2k j+2 j2−4 j−5k−5 j+10)−2k2 −4k j+11k−2 j2 +9 j−16 = 2k−6 ≥ 0, para k ≥ 3 e j ≥ 1.

Afirmação 06: A raiz da afirmação 05 é ϕ2. Isto é:3k+ j−4−

√(k+ j)2−4(k+ j−2)

2 < ϕ2 < k.

De fato, pela afirmação 05 e como

pQ′(0) = k(2k2 −4k+2)> 0

e

pQ′

(

3k+ j−4−√

(k+ j)2 −4(k+ j−2)2

)

< 0

Temos que ter também uma raiz de pQ′ entre esses dois valores.

Logo, só podemos ter ϕ3 entre 0 e3k+ j−4−

√(k+ j)2−4(k+ j−2)

2

28

e só podemos ter ϕ2 entre3k+ j−4−

√(k+ j)2−4(k+ j−2)

2 e k

Logo pelas afirmações 04,05 e 06 temos que:

ϕ3 <3k+ j−4−

√

(k+ j)2 −4(k+ j−2)2

Afirmação 01: Se j ≥ 2, então k + j − 2 é um autovalor de Q com multiplicidade aomenos j-1.

A demonstração é a mesma da proposição 3.1.3, tendo em conta que o bloco cabeça xcabeça é o único usado na prova.


√(k+ j)2−4(k+ j−2)

2 e3k+ j−4+

√(k+ j)2−4(k+ j−2)

2 são autovalores

de Q com multiplcidade ao menos k-1.

Vimos na proposição 3.1.5 que isso é verdade para qualquer aranha gorda.

Afirmação 03: m

(

3k+ j−4−√

(k+ j)2−4(k+ j−2)2

)

= m

(

3k+ j−4+√

(k+ j)2−4(k+ j−2)2

)

= k−1 e m(k+ j−2) = j−1

Prova igual aos casos anteriores.


√(k+ j)2−4(k+ j−2)

2 < k+ j−2 <3k+ j−4+

√(k+ j)2−4(k+ j−2)


De fato:3k+ j−4−

√

(k+ j)2 −4(k+ j−2)2

< k+ j−2⇔

0 −k+ j+√

[(k+ j)−2]2 = 2 j−2 ≥ 0

Já a desigualdade do meio vale se, e somente se

0 < k− j+√

(k+ j)2−4(k+ j)+8)

o que é verdade pelo mesmo argumento usado acima.

Já a desigualdade da direita é verdade pela proposição 2.2.1.

Afirmação 05: Para k ≥ 3 e j ≥ 1, existe pelo menos uma raiz de pQ′ entre os autova-lores k+ j−2 e 3k+ j−4+

√(k+ j)2−4(k+ j−2)

2 .

Com uma conta relativamente simples, vemos que

pQ′(k+ j−2) =−k2 j− k j2 +3k j+ j2 −2 j

Logo, pQ′(k+ j−2)< 0⇔ k2 + k j−3k− j+2 > 0 (multiplicamos por −1

j)

⇔ k(k−3)+ j(k−1)+2 > 0,

30

o que vale claramente para k ≥ 3 e j ≥ 1.

Por outro lado, encontramos que

pQ′

(

3k+ j−4+√

(k+ j)2 −4(k+ j−2)2

)

=

√

(k+ j)2 −4(k+ j−2)2

(2k2−3k)+ k3 − k2 j− 5k2

2+

5k j

2+2k

Observe que pQ′

(

3k+ j−4+√

(k+ j)2−4(k+ j−2)2

)

>

√[(k+ j)−2]2

2 (2k2−3k)+k3−k2 j− 5k22 +

5k j2 +2k = 2k(k−3)+ j+5 > 0, para todos k ≥ 2, j ≥ 1.

Afirmação 06: k+ j−2 < ϕ2 < 3k+ j−4+√

(k+ j)2−4(k+ j−2)2 para k ≥ 3, j ≥ 1.

De fato, basta observar que pQ′(−2) > 0 para k ≥ 3, j ≥ 1. Como pQ′(k+ j−2) < 0,temos que ter 0 ≤ ϕ3 < k+ j−2 e também ϕ2 como a raiz da afirmação 05.

Observe que, para todos k ≥ 3, j ≥ 1, já temos provado que:

ϕ3 < k+ j−2 < ϕ2 <3k+ j−4+

√

(k+ j)2 −4(k+ j−2)2

< ϕ1

e

3k+ j−4−√

(k+ j)2 −4(k+ j−2)2

< k+ j−2

⇔√

(k+ j)2−4(k+ j−2)2

(2k2−3k)− k3 + k2 j+ 5k2

2− 5k j

2−2k > 0

Dividindo tudo por k e usando novamente o fato que

√(k+ j)2−4(k+ j−2)

2 >

√[(k+ j)−2]2

2 =k+ j−2 , obtemos que:

√

(k+ j)2 −4(k+ j−2)2

(2k2 −3k)− k3 + k2 j+ 5k2

2− 5k j

2−2k > 2k j− k−4 j+1

Onde vemos que 2k j− k−4 j+1 > 0 sempre que k ≥ 3.OBSERVAÇ ÃO 3.1.4. Um estudo importante em Teoria Espectral de grafos é o que se re-

fere a quantidade de autovalores distintos de um grafo. Encontrar grafos com poucos

autovalores distintos tem sido o foco de muitos artigos, como se pode ver em [15], [16]

e [17]. Os resultados desta seção nos fornecem grafos na classe das aranhas, com ape-

nas quatro Q-autovalores distintos, para qualquer número de vértices (Proposições 3.1.1 e

3.1.4). Obtemos também grafos com exatamente seis Q-autovalores distintos (Proposições

3.1.2,3.1.3,3.1.5 e 3.1.6).

Notamos que o diâmetro de qualquer aranha magra é três, portanto o numéro mı́nimo de Q-

autovalores distintos é quatro [14]. Esta cota é atingida pelas aranha magra sem cabeça.

No caso das aranhas gordas, o diâmetro é sempre 2.

3.2 Propriedades Q-espectrais para qualquer aranha

Os resultados da seção anterior permitem algumas generalizações, apresentados a seguir.

Proposição 3.2.1. Seja Sm[k, j,G] uma aranha magra qualquer. Entãok+ j+

√(k+ j)2−4(k+ j−2)

2é um autovalor de Q(Sm[k, j,G]) com multiplicidade de, pelo menos, k-1. Além disso temos

que q2 = q3 = ...= qk =k+ j+

√(k+ j)2−4(k+ j−2)

2 , para qualquer aranha magra.

Demonstração. A primeira afirmação é direto da Observação 3.1.1.

Pelas Proposições 3.1.2 e 3.1.3 temos que

qi(Sm[k, j,K j]) = qi(Sm[k, j,K j]) =k+ j+

√

(k+ j)2 −4(k+ j−2)2

para i = 2,3, ...,k

Daı́ e pelo Teorema 2.3.1, que nos garante que

qi(Sm[k, j,K j])≤ qi(Sm[k, j,G])≤ qi(Sm[k, j,K j])

para qualquer grafo G com j vértices e ∀i = 1, ...,n = 2k + j, o que acarreta a segundaafirmação.

Proposição 3.2.2. Seja Sg[k, j,G] uma aranha gorda qualquer. Então3k+ j−4+

√(k+ j)2−4(k+ j−2)

2é um autovalor de Q(Sg[k, j,G]) com multiplicidade ao menos k-1. Além disso tempos que

q2 = q3 = ...= qk =3k+ j−4+

√(k+ j)2−4(k+ j−2)

2 , para qualquer aranha gorda.

32

Demonstração. Prova análoga a anterior, usando os resultados relativos à aranha gorda.

Proposição 3.2.3. Seja Sm[k, j,G] uma aranha magra qualquer. Entãok+ j−

√(k+ j)2−4(k+ j−2)

2é um autovalor de Q(Sm[k, j,G]) com multiplicidade de ao menos k-1. Além disso, se k ≥ 3,temos que q2k+ j−1 = q2k+ j−2 = ...= q2k+ j−(k−2) =

k+ j−√

(k+ j)2−4(k+ j−2)2

Demonstração. A primeira afirmação segue diretamente da Observação 3.1.1.

Pelas proposições 3.1.2 e 3.1.3 temos que

qi(Sm[k, j,K j]) = qi(Sm[k, j,K j]) =k+ j−

√

(k+ j)2 −4(k+ j−2)2

para i = 2k+ j− (k−2),2k+ j− (k−3), ...,2k+ j−1Daı́ e pelo Teorema 2.3.1 temos a segunda afirmação.

Proposição 3.2.4. Seja Sg[k, j,G] uma aranha gorda qualquer. Então3k+ j−4−

√(k+ j)2−4(k+ j−2)

2é um autovalor de Q(Sg[k, j,G]) com multiplicidade de, pelo menos, k-1. Além disso tempos

que q2k+ j−1 = q2k+ j−2 = ...= q2k+ j−(k−1) =3k+ j−4−

√(k+ j)2−4(k+ j−2)

2 , para k ≥ 3.

Demonstração. Prova é igual a anterior, usando os resultados análogos para Aranha gorda.

OBSERVAÇ ÃO 3.2.1. Destas proposições decorre que o número de autovalores distintos de

S[k, j,G], para qualquer grafo G, é no maximo igual a n− (2k+2)+2 = j+4. Portantoa quantidade máxima de autovalores distintos depende somente do número de vértices na

cabeça.

3.3 Propriedades do tipo Nordhaus-Gaddum para aranhas

Proposição 3.3.1. Seja S = S[k, j,G] uma aranha qualquer . Então qi(S)+ qi(S) = 2k+j−2+

√

(k+ j)2−4(k+ j−2) , para i=2,3,...,k.

Demonstração. Note que se S é uma aranha magra (gorda) então S é uma aranha gorda

(magra).

Logo, para i=2,3,...,k, temos pela Proposição 3.2.1 e Proposição 3.2.2 que

qi(S)+qi(S) =k+ j+

√(k+ j)2−4(k+ j−2)

2 +3k+ j−4+

√(k+ j)2−4(k+ j−2)

2 =

2k+ j−2+√

(k+ j)2−4(k+ j−2)

Como corolário desta proposição, obtemos um resultado do tipo Nordhaus-Gaddum

para aranhas.

Corolário 3.3.1. Seja S = S[k, j,G] uma aranha qualquer com k ≥ 3 e j ≥ 0 ou com k = 2e j ≥ 2. Então q2(S)+q2(S)< 2n−5

33

Demonstração. q2(S)+q2(S) = 2k+ j−2+√

(k+ j)2 −4(k+ j−2)

Daı́,

q2(S)+q2(S)< 2n−5⇔ q2(S)+q2(S)< 2(2k+ j)−5⇔ 2k+ j−2+

√

(k+ j)2 −4(k+ j−2)< 2(2k+ j)−5⇔√

(k+ j)2 −4(k+ j−2)< 2k+ j−3⇔ (k+ j)2 −4(k+ j−2)< (2k+ j−3)2⇔ 0 < 3k2 +2k j−8k−2 j+1⇔ 0 < k(3k−8)+ j(2k−2)+1

onde a última desigualdade é claramente verdade, para k ≥ 3 com j ≥ 0 e para k = 2com j ≥ 2.

Proposição 3.3.2. Seja S = S[k, j,G] uma aranha qualquer com k ≥ 3. Então qi(S) +qi(S) = 2k+ j−2−

√

(k+ j)2−4(k+ j−2) , para i=n-1,...,n-(k-2).

Demonstração. Temos pelas proposições 3.2.3 e 3.2.4 que

qi(S)+qi(S) =k+ j−

√(k+ j)2−4(k+ j−2)

2 +3k+ j−4−

√(k+ j)2−4(k+ j−2)

2 =

2k+ j−2−√

(k+ j)2−4(k+ j−2), para i=n-1,...,n-(k-2)

3.4 Propriedades do tipo Nordhaus-Gaddum para grafos

P4-esparsos

Através de buscas computacionais com o software SAGE, Lima [9] apresentou a seguinte

conjectura:

CONJECTURA 3.4.1. [9] Seja G um grafo com n vértices. Então q2(G)+q2(G)≤ 2n−5.

Ainda em [9], é provado que essa propriedade vale para grafos desconexos ou grafos

conexos cujo complementar é desconexo:

Teorema 3.4.1. [9] Seja G um grafo com n vértices tal que G é desconexo ou G é desco-

nexo. Então q2(G)+q2(G)≤ 2n−5.

Agora, vamos provar que esta propriedade é válida para todo grafo G P4-esparso.

Teorema 3.4.2. Seja G um grafo P4-esparso com n vértices. Então q2(G)+q2(G)≤ 2n−5.

Demonstração. Seja G um grafo P4-esparso. Pelo teorema 2.1.1 temos que:

(i) G é desconexo

(ii) G é desconexo

(iii) G é aranha

Os casos (i) e (ii) seguem do Teorema 3.4.1. O caso (iii) segue do corolário 3.3.1.

Note que este teorema garante a veracidade da conjectura para uma classe que engloba

todos os grafos threshold e, mais ainda, todos os cografos.

34

Capı́tulo 4

Matriz distância

Grafos com poucos autovalores distintos em relação a várias matrizes têm sido amplamente

estudados, como se pode ver em [15], [16] e [17].

Uma outra maneira de olhar para este problema é procurar por grafos cujos autovalores

têm multiplicidade grande.

As aranhas com certas cabeças especiais fornecem exemplos de grafos com estas carac-

terı́sticas para a matriz distância, assim como vimos para a matriz laplaciana sem sinal.

Para as matrizes de adjacência, laplaciana e laplaciana sem sinal é conhecida uma cota

inferior para o número de autovalores distintos, baseada no diâmetro do grafo (número de

autovalores distintos é pelo menos o diâmetro mais um). No entanto, isto não vale para

a matriz distância. Este fato torna mais relevante o estudo da quantidade de autovalores

distintos para esta matriz.

4.1 D-Espectro de algumas aranhas especiais

Assim como fizemos para a matriz Q, veremos o D-espectro de aranhas cuja cabeça induz

K j, K j e também aranha sem cabeça.

Proposição 4.1.1. Seja Sm[k] aranha magra sem cabeça (j=0) com k ≥ 2. Então o espectroda sua matriz distância está determinado da seguinte forma:

σD(Sm[k]) =

−2−√

2 2k−2−√

5k2 −6k+2 −2+√

2 2k−2+√

5k2 −6k+2

k−1 1 k−1 1

,

para 2 ≤ k ≤ 11

σD(Sm[k]) =

2k−2−√

5k2 −6k+2 −2−√

2 −2+√

2 2k−2+√

5k2 −6k+2

1 k−1 k−1 1

,

para k ≥ 12.

Demonstração. A matriz distância D(Sm[k]), que vamos denotar somente por D, é dadapor:

35

0 1 . . . 1 | 1 2 . . . 21 0 . . . 1 | 2 1 . . . 2...

.... . .

... | ... ... . . . ...1 1 . . . 0 | 2 2 . . . 1

−− −− −− −− −− −− −− −−1 2 . . . 2 | 0 3 . . . 32 1 . . . 2 | 3 0 . . . 3...

.... . .

... | ... ... . . . ...2 2 . . . 1 | 3 3 . . . 0


D =

[

−Ik +Jk −Ik +2Jk−Ik +2Jk −3Ik +3Jk

]

,

Observe que todas as matrizes blocos que compõem a matriz D somam, em suas linhas,

o mesmo valor para cada bloco. Assim consideremos a matriz D′2x2 cujas entradas são taissomas:

D′ =

(

k−1 2k−12k−1 3k−3

)

.

Temos que o polinômio caracterı́stico de D′ é dado por

pD′(x) = x2 +(−4k+4)x+ k2 −2k+2,

cujas raizes são 2k−2−√

5k2 −6k+2 e 2k−2+√

5k2 −6k+2, que também são au-tovalores de D pelo teorema 2.2.3.

Afirmação 01: Temos que −2−√

2 e −2+√

2 são autovalores de D com multiplici-

dade k-1.


seja, k ≥ 2) então podemos tomar u ∈ Rk perpendicular a ~1 e considerar o vetor w =[

u

(1+√

2)u

]

em R2k. Logo

D.w = D.

[

u

(1+√

2)u

]

=

[

−u− (1+√

2)u

−u−3(1+√

2)u

]

=

=

[

(−2−√

2)u

(−4−3√

2)u

]

= (−2−√

2)

[

u

(1+√

2)u

]

= (−2−√

2)w

Portanto −2−√

2 é autovalor do grafo com multiplicidade ao menos k−1 (pois existemk−1 vetores linearmente independentes do Rk perpendiculares a~1k).

Com procedimento semelhante podemos concluir que −2+√

2 é autovalor com multi-

plicidade ao menos k−1, referente ao autovetor w =[

u

(1−√

2)u

]

∈R2k.

36

Além disso, como já temos dois autovalores de S com multiplicidade ao menos k − 1mais outros dois com multiplicidade ao menos 1 e a soma das multiplicidades tem de ser

2k, então só podem valer as igualdades nas multiplicidades. Assim o D-espectro está deter-

minado, vamos agora ordenar os D-autovalores.

Afirmação 02: Para 2 ≤ k ≤ 11 temos que:

−2−√

2 < 2k−2−√

5k2 −6k+2

Proposição 4.1.2. Seja Sm[k, j,K j] com k ≥ 2 e j ≥ 2. Então o espectro da sua matrizdistância é formado por:

(−2−√

2)(k−1), (−2+√

2)(k−1), (−2)( j−1),ϕ3, ϕ2, ϕ1

onde os expoentes estão denotando a multiplicidade e ϕ3 ≤ ϕ2 ≤ ϕ1 são as raı́zes dopolinômio:

pD′(x) =−x3+(4k+2 j−6)x2+(k2−3k j+10k+8 j−10)x−k2 j+2k2−k j+4k+4 j−4.

Além disso, temos, em todos os casos, que:

−2−√

2

Denotamos novamente u perpendicular a~1, em R j ou Rk, temos por contas analogas asjá feitas que:

• −2 é autovalor de D, com multiplicidade j − 1, associado ao autovetor

~0k~0ku

∈

R2k+ j.

• −2−√

2 é autovalor de D, com multiplicidade k−1, associado ao autovetor

u

(1+√

2)u~0 j

∈R2k+ j.

• −2+√

2 é autovalor de D, com multiplicidade k−1, associado ao autovetor

u

(1−√

2)u~0 j

∈R2k+ j.

Agora vamos estudar os sinais de pD′(x) para x =−2−√

2, x =−2 e x =−2+√

2.

• Verificamos que pD′(−2−√

2) =√

2(−k2 +3k j+6k)− k2 j+5k j+8k, logo:(i) pD′(−2−

√2)> 0, se k ≤ 9 e j ≥ 2; e para k = 10 com j = 2, j = 3

(ii) pD′(−2−√

2)< 0, se k = 10 e j ≥ 4; e para k ≥ 11 e j ≥ 2

Onde para verificar (i) basta fixar os valores k = 2,k = 3, ..,k = 10 em pD′(−2−√

2)para achar os valores de j que satisfazem a desigualdade pD′(−2−

√2)> 0 em cada caso.

Em (ii) observamos que:√2(−k2 +3k j+6k)− k2 j+5k j+8k < 0 ⇔√2(−k+3 j+6)− k j+5 j+8 < 0 (lembre que k ≥ 2).

Definimos então f (k) =√

2(−k + 3 j + 6)− k j + 5 j + 8, onde f ′(k) = −√

2− j. Entãof ′(k)< 0 para k ≥ 2 e j ≥ 2.Logo f é decrescente em relação a variável k. Como f (11) < 0 para j ≥ 2, temos que issotambém vale para todo k ≥ 11.

• Verificamos que pD′(−2) =−k2 j+5k j−4 j, logo:pD′(−2)> 0 se k ≤ 3 e j ≥ 2pD′(−2) = 0 se k = 4 e j ≥ 2pD′(−2)< 0 se k ≥ 5 e j ≥ 2

Onde para verificar as três desigualdades basta estudar o sinal do polinômio g(k) =−k2 +5k−4.

• Verificamos que pD′(−2+√

2) =√

2(k2−3k j−6k)− k2 j+5k j+8k, logo:pD′(−2+

√2)< 0 para k ≥ 2 , j ≥ 2

Observamos que:√2(k2 −3k j−6k)− k2 j+5k j+8k < 0 ⇔√2(k−3 j−6)− k j+5 j+8 < 0

Definimos então f (k) =√

2(k−3 j−6)−k j+5 j+8, onde f ′(k) =√

2− j. Então f ′(k)< 0para k ≥ 2 e j ≥ 2.

39

Logo f é decrescente em relação a variável k. Como f (2) < 0 para j ≥ 2, temos que issotambém vale para todo k ≥ 2.

• Então, para k ≤ 3 e j ≥ 2 temos:ϕ3 está entre −2 e −2+

√2

Não existem raizes entre −2−√

2 e −2, pois caso exista alguma raiz entre esses valores,teria de existir duas raı́zes. O que não pode ocorrer, pois −2 < ϕ3 e ϕ1 é o maior autovalor.

ϕ2 é o segundo maior autovalor.

• Para k = 4 e j ≥ 2 temos:ϕ3 = −2 é a única raiz de pD′(x) entre −2−

√2 e −2+

√2 (Pois caso existisse outra,

teriamos pD′(−2+√

2)> 0 para k = 4, o que não ocorre).Portanto novamente ϕ2 é o segundo maior autovalor.

• Para 5 ≤ k ≤ 9 e j ≥ 2; ou k = 10 e j = 2, j = 3 temos:ϕ3 está entre −2−

√2 e −2

e ϕ2 é o segundo maior autovalor.

• Para k = 10 e j ≥ 4; ou k ≥ 11 e j ≥ 2; temos:Como

pD′(−k) = 4k3+4k2 j−14k2−9k j+14k+4 j−4 = k2(4k−14)+ j(4k2−9k)+14k+4 j−4

que é claramente maior que 0 para k ≥ 10Então ϕ3 vai estar entre −k e −2−

√2, para −k ≤ 10.

Logo não pode existir nenhuma raiz entre −2−√

2 e −2nem entre −2 e −2+

√2

Portanto ϕ2 é o segundo maior autovalor.

E assim concluı́mos que valem os espectros da proposição.

Proposição 4.1.3. Seja Sm[k, j,K j] com k ≥ 2 e j ≥ 1, então o espectro da sua matrizdistância está determinado da seguinte forma:

σD(Sm[k, j,K j]) =

−2−√

2 ϕ3 −1 ϕ2 −2+√

2 ϕ1

1 k−1 j−1 1 k−1 1

Se k = 2 e j < 10; ou k = 3 e j < 9; ou k = 4 e j < 8; ou k = 5 e j < 7; ou k = 6 e j < 6;ou k = 7 e j < 5; ou k = 8 e j < 4; ou k = 9 e j < 3; ou k = 10 e j = 1.

σD(Sm[k, j,K j]) =

ϕ3 −2−√

2 −1 ϕ2 −2+√

2 ϕ1

1 k−1 j−1 1 k−1 1

Em todos os outros casos,

Onde ϕ3 < ϕ2 < ϕ1 são as raizes do polinômio:

pD′(x) =−x3 +(4k+ j−5)x2 +(k2 + k j+6k+4 j−6)x+ k2 + k j+2k+2 j−2

40

Demonstração. A matriz distância D(Sm[k, j,K j]), que vamos denotar somente por D, podeser escrita como uma matriz em blocos dada por:

D =

−Ik +Jk −Ik +2Jk Jk, j−Ik +2Jk −3Ik +3Jk 2Jk, j

J j,k 2J j,k −I j +J j

,


o mesmo valor para cada bloco. Assim consideremos a matriz D′3x3 cujas entradas são taissomas, isto é:

D′ =

k−1 2k−1 j2k−1 3k−3 2 j

k 2k j−1

.

Então, pelo Teorema 2.2.3, garantimos que os autovalores de D′ também são autovaloresda matriz D. Denotamos por ϕ3 ≤ ϕ2 ≤ ϕ1 os três autovalores, que são raı́zes do polinômiocaracterı́stico pD′ , dado por:

pD′(x) =−x3 +(4k+ j−5)x2 +(k2 + k j+6k+4 j−6)x+ k2 + k j+2k+2 j−2

Por contas análogas as feitas no caso da matriz laplaciana sem sinal, verificamos que:

• −1 é autovalor de D associado ao autovetor

~0k~0ku

∈R2k+ j.

• −2−√

2 é autovalor de D associado ao autovetor

u

(1+√

2)u~0 j

∈R2k+ j.

• −2+√

2 é autovalor de D associado ao autovetor

u

(1−√

2)u~0 j

∈R2k+ j.

Agora vamos estudar os sinais de pD′(x) para x =−2−√

2, x =−1 e x =−2+√

2.

• Verificamos que pD′(−2−√

2) =√

2(−k2 − k j+10k)− k2 − k j+14k, logo:(i) pD′(−2−

√2)> 0

Se k = 2 e j < 10; k = 3 e j < 9; k = 4 e j < 8; k = 5 e j < 7; k = 6 e j < 6; k = 7 ej < 5; k = 8 e j < 4; k = 9 e j < 3; e para k = 10 com j = 1.

(ii) pD′(−2−√

2)< 0 para todos os outros casos.

Para verificar (i) basta fixar os valores k = 2,k = 3, ..,k = 10 em pD′(−2−√

2) paraachar os valores de j que satisfazem a desigualdade pD′(−2−

√2)> 0 em cada caso.

Em (ii) observamos que:

√2(−k2 − k j+10k)− k2 − k j+14k < 0 ⇔

41

√2(−k− j+10)− k− j+14 < 0

Definimos então f (k, j) =√

2(−k − j + 10)− k − j + 14, onde pelas derivadas parciaisvemos que f é decrescente em relação às variáveis k e j.

Fixando k = 3 e j = 9, temos que f (3,9) =−2√

2+2 < 0, logo f (k, j)< 0 para k = 3e j ≥ 9, pois f é descrescente na variável j.

Prosseguindo com valores de k e j que não sejam os do caso (i), mostramos (ii).

• Verificamos que pD′(−1) =− j−2, logo:pD′(−1)< 0 para todos k ≥ 2 e j ≥ 1

• Verificamos que pD′(−2+√

2) =√

2(k2+ k j−10k)− k2 − k j+14k, logo:pD′(−2+

√2)> 0 para k ≥ 2 , j ≥ 1

Note que pD′(−2+√

2) =√

2(k2 + k j−10k)− k2 − k j+14k =k2(

√2−1)+ k j(

√2−1)+ k(14−10

√2)> 0, para k ≥ 2 , j ≥ 1

• Então para k = 2 e j < 10; ou k = 3 e j < 9; k = 4 e j < 8; k = 5 e j < 7; k = 6 ej < 6; k = 7 e j < 5; k = 8 e j < 4; k = 9 e j < 3; k = 10 com j = 1, temos que:

ϕ3 está entre −2−√

2 e −1ϕ2 está entre −1 e −2+

√2

Concluindo assim a ordenação do espectro para esses valores de k e j.

• Para todos os outros valores de k e j, temos que:

Existe uma raiz entre −1 e −2+√

2.

Portanto não pode existir nenhuma raiz de pD′ entre −2−√

2 e −1 (pois caso contrárioteriamos que ter tanto ϕ3 quanto ϕ2 entre esses valores).

Afirmamos que ϕ3 é o menor autovalor do grafo e que ϕ2 está entre −1 e −2+√

2.

De fato: como o polinômio pD′ tem o termo de maior grau negativo (−x3) então existealgum x0 0.

Logo, existe raiz de pD′ entre x0 e −2−√

2. A qual só pode ser ϕ3, que, portanto, é omenor autovalor de D.

Consequentemente o autovalor buscado só pode ser ϕ2, valendo assim a afirmação.

OBSERVAÇ ÃO 4.1.2. Recordemos a observação 3.1.2, e sem perda de generalidade, vamos

considerar k ≥ 3 nos teoremas abaixo.

Proposição 4.1.4. Seja Sg[k] aranha gorda sem cabeça (j=0) com k ≥ 3. Então o espectroda sua matriz distância está determinado da seguinte forma:

σD(Sg[k]) =

−3−√

52

3k−3−√

5k2+6k+52

−3+√

52

3k−3+√

5k2+6k+52

k−1 1 k−1 1

,

42

para k = 3 e k = 4

σD(Sg[k]) =

−3−√

52

−3+√

52

3k−3−√

5k2+6k+52

3k−3+√

5k2+6k+52

k−1 k−1 1 1

,

para k ≥ 5.

Demonstração. A matriz distância D(Sg[k]), que vamos denotar somente por D, é dada por:

0 1 . . . 1 | 2 1 . . . 11 0 . . . 1 | 1 2 . . . 1...

.... . .

... | ... ... . . . ...1 1 . . . 0 | 1 1 . . . 2

−− −− −− −− −− −− −− −−2 1 . . . 1 | 0 2 . . . 21 2 . . . 1 | 2 0 . . . 2...

.... . .

... | ... ... . . . ...1 1 . . . 2 | 2 2 . . . 0


D =

[

−Ik +Jk Ik +JkIk +Jk −2Ik +2Jk

]

,


o mesmo valor para cada bloco. Assim consideremos a matriz D′2x2 cujas entradas são taissomas:

D′ =

(

k−1 k+1k+1 2k−2

)

.

Temos que o polinômio caracterı́stico de D′ é dado por

pD′(x) = x2 +(−3k+3)x+ k2 −6k+1,

cujas raizes são 3k−3−√

5k2+6k+52 e

3k−3+√

5k2+6k+52 , que também são autovalores de D

pelo teorema 2.2.3.

Afirmação 01: Temos que −3−√

52 e

−3+√

52 são autovalores de D com multiplicidade

k-1.

De fato, podemos tomar u∈Rk perpendicular à~1 e considerar o vetor w=[

u

(−1−√

52 )u

]

em R2k. Logo

D.w = D.

[

u

(−1−√

52 )u

]

=

[

−u+(−1−√

52 )u

u+(1+√

5)u

]

=

=

[

(−3−√

52 )u

(2+√

5)u

]

= (−3−

√5

2)

[

u

(−1−√

52 )u

]

= (−3−

√5

2)w

43

Portanto −3−√

52 é autovalor do grafo com multiplicidade ao menos k−1 (pois existem

k−1 vetores linearmente independentes do Rk perpendiculares a~1k).

Com procedimento semelhante podemos conclui

Documents

app.uff.br§ão... · 2020. 7. 27. · Lucas Lima Silva Portugal Q-ESPECTRO E D-ESPECTRO DOS GRAFOS ARANHA Dissertação apresentada por Lucas Lima Silva Portugal ao Curso de Mestrado