The theory of graph spectra can, in a way, be considered as an attempt to utilize linear algebra including, in particular, the well-developed theory of matrices for the purposes of graph theory and its applications. However, that does not mean that the theory of graph spectra can be reduced to the theory of matrices; on the contrary, it has its own characteristic features and specific ways of reasoning that fully justifying it to be treated as a theory in its own right.
It has the curious feature that some of the main results, although purely combinatorial in character, seem in the present state of knowledge to be unobtainable without resorting to algebraic methods involving a consideration of eigenvalues of adjacency matrices of graphs. There are unexplored and semi-explored territories in graph theory. It will be apparent that the results achieved so far barely scratch the surface of what appears to be a rich area of investigation.
a split nonthreshold
Laplacian integral graph.
ORIGINS OF THE THEORY OF GRAPH SPECTRA
The first paper was in quantum chemistry:
* E. Hückel, Quantentheoretische Beitrage zum Benzolproblem, Z. Phys. 70(1931), 204-286
The first mathematical paper:
* L. Collatz, U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Sem. Univ. Hamburg, 21(1957), 63--77
Many years later was recognized that the two theories are essentially the same.
>> See all events
Suggest a researcher
Suggest an article
Suggest an event
Suggest a link
House of Graphs: a database of interesting graphs -- an update
Already in 2012 we announced the website "House of Graphs" -- http://hog.grinvin.org/ -- through this mailing list. In the meantime several new lists of graphs, "interesting graphs", and invariants have been added to the website.
"House of Graphs" hosts lists of graphs (like Snarks, Fullerenes, etc.) and links to other pages with lists of combinatorial structures (like vertex transitive graphs, Ramsey graphs, etc.). But its main feature is a searchable database of graphs that already occurred as counterexamples to conjectures, as extremal graphs or in other contexts. In short we call this the database of "interesting graphs".
The key idea is that although already for small vertex numbers extremely many graphs exist, there are some that serve again and again as counterexamples and that a database of these graphs should be established. In this database one can e.g. search for graphs with certain invariant values, graphs with a certain name (e.g. Petersen, Heawood, Balaban, etc.) or graphs that are marked as being interesting for a certain invariant (e.g. marked as being interesting for the girth). These searches can of course also be combined and the results downloaded so that one gets good candidates for testing new conjectures one is working on.
Users can also add graphs to the database. If the graphs are not yet in the database, the system computes invariant values for the graphs. So the database can also be used as a repository. If you discover new interesting graphs, you can make them available to other users by submitting them to the database together with a text identifier (e.g. counterexample_this_conjecture). Then other scientists can find and download the graph from "House of Graphs".
More information on "House of Graphs" and its functionalities is given in:
Discrete Applied Mathematics, Volume 161, Issues 1-2, Jan. 2013, pages 311-314
Available online: http://dx.doi.org/10.1016/j.dam.2012.07.018
while "House of Graphs" can be accessed at: http://hog.grinvin.org/
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot
[DMANET] Rudolf Halin 1934-2014
Many of you will be saddened to hear that Rudolf Halin has died. He passed away on 7 November 2014, having turned 80 only a few months before, on 3 February.
Halin was one of Wagners three most eminent students. He is best known for his early papers on connectivity, and particularly for his seminal work on infinite graphs and their ends. Throughout his work, Halin was driven by a desire to get to the bottom of things, to find the essence of the phenomena that had caught his attention. One of his last papers was a collection of open problems, published in the Journal of Graph Theory, of which most are still unresolved.
About eBook "Graph Theory", by Reinhard Diestel
We received this note from Reinhard Diestel
"On March 12, 2013, the inexpensive eBook edition of my book, Graph Theory, will have to move to another outlet, due to e-publisher Lulu's
policy decision to discontinue Adobe-DRM support. I hope to have alternative channels in place by that time, but cannot say at this stage whether they'll be as cheap as currently at Lulu.
Until March 11, the eBook should continue to be available from Lulu, through the book's website,
It runs on PCs, Macs, iOS and Android devices.
The (printable) "professional edition" will change from the current certificate-based DRM to password-based DRM, which will be easier to use on all platforms that can display PDF.
The free preview edition will be unaffected by these changes and remain available from the book's website.
RD, 19 Feb 2013
The Fourth Edition of Matrix Computations by Golub and Van Loan is now available. For additional information, see
LIA-SGT Workshop, Rio de Janeiro, 2012 September 27-28
The House of Graphs
House of Graphs (http://hog.grinvin.org) is a new database of graphs.
The key principle is to have a searchable database and offer–next to complete lists of some graph classes–also a list of special graphs that have already turned out to be interesting and relevant in the study of graph theoretic problems or as counterexamples to conjectures. This list can be extended by users of the database.
MATCH Journal now is free pay in
Applications of Combinatorial Matrix Theory to Laplacian Matrices of Graphs, J.J. Molitierno
This book is a compilation of many of the results concerning Laplacian matrices that have been developed since the mid 1970's.
The Latin Ibero-American Spectral Graph Theory Workshop has been organized as a forum for the many researchers around the Latino-ibero-american. However, every researcher in Graph Spectra will be welcome. The conference will take place in Rio de Janeiro, from September 27 to 28, 2012. Please, for more information visit http://sobrapo.org.br/lia-sgt/
The Mutually Beneficial Relationship of Graphs and Matrices, Richard A. Brualdi
Graphs and matrices enjoy a fascinating and mutually beneficial relationship. This book is not a comprehensive study of graphs and matrices. The particular content of the lectures was chosen for its accessibility, beauty, and current relevance, and for the possibility of enticing the audience to want to learn more.
A new book by Anthony Bonato and Richard Nowakowski
The Game of Cops and Robbers on Graphs, Published by the American Mathematical Society
Graph Theory section of the journal DMTCS
Discrete Mathematics and Theoretical Computer Science (DMTCS) is a electronic journal devoted to publication in the fields of Discrete
Mathematics and Theoretical Computer Science and the
intersection of the two. It is listed by ISI.
The Graph Theory section covers research in all aspects of finite graphs
but with a slight preference to papers with results showing some
connection to computer science.
Graph Theory section of the journal DMTS (cont.)
* Joergen Bang-Jensen, University of Southern Denmark, Denmark
* Maria Chudnovsky, Columbia University, USA
* Frederic Havet, CNRS, Sophia Antipolis, France
* Michael Henning, University of Johannesburg, South Africa
* Jing Huang, Un. of Victoria, Canada
* Tomas Kaiser, University of West Bohemia, Czech Republic
* Ken-ichi Kawarabayashi, NII, Tokyo, Japan
Graph Theory section of the journal DMTS (cont.)
* Peter Keevash, Queen Mary University of London, England
* Jan Kratochvil, Charles University, Praha, Czech Republic
* Matthias Kriesell, University of Southern Denmark, Denmark
* Zsolt Tuza, Hungarian Academiy of Sciences, Hungary
* Anders Yeo, Royal Holloway, University of London, England
The Editor-in-Chief of DMTCS is Jens Gustedt, INRIA Nancy - Grand Est.
Professor Dragos Cevetkovic for his 70 years
The group of researchers in Spectral Graph Theory of Rio de Janeiro would like to congratulate Professor Dragos Cevetkovic on his 70th birthday. Also, the group would like to express its thanks to Professor for his pioneering and significant contribution to the graph spectra area.