Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

16.07.2016 | Ausgabe 1-2/2017

Designs, Codes and Cryptography 1-2/2017

On eigenvalues of Seidel matrices and Haemers’ conjecture

Zeitschrift:
Designs, Codes and Cryptography > Ausgabe 1-2/2017
Autor:
Ebrahim Ghorbani
Wichtige Hinweise
This is one of several papers published in Designs, Codes and Cryptography comprising the special issue in honor of Andries Brouwer’s 65th birthday.
Dedicated to Andries E. Brouwer on the occasion of his 65th birthday.

Abstract

For a graph G, let S(G) be the Seidel matrix of G and \({\theta }_1(G),\ldots ,{\theta }_n(G)\) be the eigenvalues of S(G). The Seidel energy of G is defined as \(|{\theta }_1(G)|+\cdots +|{\theta }_n(G)|\). Willem Haemers conjectured that the Seidel energy of any graph with n vertices is at least \(2n-2\), the Seidel energy of the complete graph with n vertices. Motivated by this conjecture, we prove that for any \(\alpha \) with \(0<\alpha <2,|{\theta }_1(G)|^\alpha +\cdots +|{\theta }_n(G)|^\alpha \geqslant (n-1)^\alpha +n-1\) if and only if \(|\hbox {det}\,S(G)|\geqslant n-1\). This, in particular, implies the Haemers’ conjecture for all graphs G with \(|\hbox {det}\,S(G)|\geqslant n-1\). A computation on the fraction of graphs with \(|\hbox {det}\,S(G)|<n-1\) is reported. Motivated by that, we conjecture that almost all graphs G of order n satisfy \(|\hbox {det}\,S(G)|\geqslant n-1\). In connection with this conjecture, we note that almost all graphs of order n have a Seidel energy of order \(\Theta (n^{3/2})\). Finally, we prove that self-complementary graphs G of order \(n\equiv 1\pmod 4\) have \(\det S(G)=0\).

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1-2/2017

Designs, Codes and Cryptography 1-2/2017 Zur Ausgabe

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise