Семинар за примењену и индустријску математику, 12. октобар 2011.

• 12. Октобар, 2011
• Коментари (0)

Наредно предавање на Семинару је у измењеном термину: среда, 12.10.2011. у 14:15 у сали 301ф, МИ САНУ.

Предаач: Willem Haemers, Tilburg University, Холандија

Биће одржана два предавања:

1. UNIVERSAL ADJACENCY MATRICES WITH TWO EIGENVALUES

Abstract: Consider a graph $G$ on $n$ vertices with adjacency matrix $A$ and degree sequence $( d_1, \dots ,d_n )$. A universal adjacency matrix of $G$ is any matrix in Span$\{ A,D,I,J \}$ with a nonzero coefficient for $A$, where $D = \mbox{diag}(d_1, \ldots ,d_n)$ and $I$ and $J$ are the identity and all-ones matrix, respectively. Thus a universal adjacency matrix is a common generalization of the adjacency, the Laplacian, the signless Laplacian and the Seidel matrix. We investigate graphs for which some universal adjacency matrix has just two eigenvalues. The regular ones are strongly regular, complete or empty, but several other interesting classes occur. (Joint work with Reza Omidi).

2. THE MAXIMUM ORDER OF ADJACENCY MATRICES WITH A GIVEN RANK

Abstract: We look for the maximum order $m(r)$ of the adjacency matrix $A$ of a graph $G$ with a fixed rank $r$, provided $A$ has no repeated rows or all-zero row. Akbari, Cameron and Khosrovshahi conjecture that $m(r)=2^{(r+2)/2}-2$ if $r$ is even, and $m(r)=5\cdot 2^{(r-3)/2}-2$ if $r$ is odd. We prove the conjecture and characterize $G$ in the case that $G$ contains an induced subgraph $\frac{r}{2}K_2$, or $\frac{r-3}{2}K_2+K_3$. (Joint work with Rene Peeters).