Torsten Sander

We present a method which in principal allows to characterise all integral circulant graphs with multiplicative divisor set having a spectrum, i.e. the set of distinct eigenvalues, of any given size. We shall exemplify the method for spectra of up to four eigenvalues, also reproving some known results for three eigenvalues along the way. In particular we show that given any integral circulant graph of arbitrary order n with multiplicative divisor set and precisely four distinct eigenvalues, n necessarily is either a prime power or the product of two prime powers with explicitly given simply structured divisor set and set of eigenvalues in both cases.

In the theory of line graphs of undirected graphs, there exists an important theorem linking the incidence matrix of the root graph to the adjacency matrix of its line graph. For directed or mixed graphs, however, there exists no analogous result. The goal of this article is to present aligned definitions of the adjacency matrix, the incidence matrix, and line graph of a mixed graph such that the mentioned theorem is valid for mixed graphs.

The traditional adjacency matrix of a mixed graph is not symmetric in general, hence its eigenvalues may be not real. To overcome this obstacle, several authors have recently defined and studied various Hermitian adjacency matrices of digraphs or mixed graphs. In this work we unify previous work and offer a new perspective on the subject by introducing the concept of monographs. Moreover, we consider questions of cospectrality.

The traditional adjacency matrix of a mixed graph is not symmetric in general, hence its eigenvalues may be not real. To overcome this obstacle, several authors have recently defined and studied various Hermitian adjacency matrices of digraphs or mixed graphs. In this work we unify previous work and offer a new perspective on the subject by introducing the concept of monographs. Moreover, we consider questions of cospectrality.

Given any digraph D, its non-negative spectrum (or N-spectrum, shortly) consists of the eigenvalues of the matrix AA^T, where A is the adjacency matrix of D. In this study, we relate the classical spectrum of undirected graphs to the N-spectrum of their oriented counterparts, permitting us to derive spectral bounds. Moreover, we study the spectral effects caused by certain modifications of a given digraph.

Given the adjacency matrix A of a digraph, the eigenvalues of the matrix AA^T constitute the so-called non-negative spectrum of this digraph. We investigate the relation between the structure of digraphs and their non-negative spectra and associated eigenvectors. In particular, it turns out that the non-negative spectrum of a digraph can be derived from the traditional (adjacency) spectrum of certain undirected bipartite graphs.

A free-form Sudoku puzzle is a square arrangement of m times m cells such that the cells are partitioned into m subsets (called blocks) of equal cardinality. The goal of the puzzle is to place integers 1,...,m in the cells such that the numbers in every row, column and block are distinct. Represent each cell by a vertex and add edges between two vertices exactly when the corresponding cells, according to the rules, must contain different numbers. This yields the associated free-form Sudoku graph. This article studies the eigenvalues of free-form Sudoku graphs, most notably integrality. Further, we analyze the evolution of eigenvalues and eigenspaces of such graphs when the associated puzzle is subjected to a "blow up" operation, scaling the cell grid including its block partition.

Each integral circulant graph ICG(n,D) is characterised by its order n and a set D of positive divisors of n in such a way that it has vertex set Z=nZ and edge set {(a,b) : a, b ? Z=nZ, gcd(a - b,n) ? D}. According to a conjecture of So two integral circulant graphs are isomorphic if and only if they are isospectral, i.e. they have the same eigenvalues (counted with multiplicities). We prove a weaker form of this conjecture, namely, that two integral circulant graphs with multiplicative divisor sets are isomorphic if and only if their spectral vectors coincide.