Maximum order of triangle-free graphs with a given rank

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle-free graphs with a given rank and characterize all such graphs achieving the maximum order.

Integral trees with given nullity

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. We prove that for a given nullity more than 1, there are only finitely many integral trees. It is also shown that integral trees with nullity 2 and 3 are unique.

On optimality of designs with three distinct eigenvalues

Let $D_{v,b,k}$ denote the family of all connected block designs with $v$ treatments and $b$ blocks of size $k$. Let $dinD_{v,b,k}$. The replication of a treatment is the number of times it appears in the blocks of $d$. The matrix $C(d)=R(d)-frac{1}{k}N(d)N(d)^top$ is called the information matrix of $d$ where $N(d)$ is the incidence matrix of $d$ and $R(d)$ is a diagonal matrix of the replications. Since $d$ is connected, $C(d)$ has $v-1$ nonzero eigenvalues $mu_1(d),...,mu_{v-1}(d)$. Let $D$ be the class of all binary designs of $D_{v,b,k}$. We prove that if there is a design $d^*inD$ such that (i) $C(d^*)$ has three distinct eigenvalues, (ii) $d^*$ minimizes trace of $C(d)^2$ over $dinD$, (iii) $d^*$ maximizes the smallest nonzero eigenvalue and the product of the nonzero eigenvalues of $C(d)$ over $dinD$, then for all $p>0$, $d^*$ minimizes $(sum_{i=1}^{v-1}mu_i(d)^{-p})^{1/p}$ over $dinD$. In the context of optimal design theory, this means that if there is a design $d^*inD$ such that its information matrix has three distinct eigenvalues satisfying the condition (ii) above and that $d^*$ is E- and D-optimal in $D$, then $d^*$ is $Phi_p$-optimal in $D$ for all $p>0$. As an application, we demonstrate the $Phi_p$-optimality of certain group divisible designs. Our proof is based on the method of KKT conditions in nonlinear programming.

On Order and Rank of Graphs

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. Akbari, Cameron, and Khosrovshahi conjectured that the number of vertices of every reduced graph of rank r is at most $m(r)=2^{(r+2)/2}-2$ if r is even and $m(r) = 5cdot2^{(r-3)/2}-2$ if r is odd. In this article, we prove that if the conjecture is not true, then there would be a counterexample of rank at most $46$. We also show that every reduced graph of rank r has at most $8m(r)+14$ vertices.

Simple signed Steiner triple systems

Let $X$ be a $v$-set, $B$ a set of 3-subsets (triples) of $X$, and $B^+cupB^-$ a partition of $B$ with $|B^-|=s$. The pair $(X,B)$ is called a simple signed Steiner triple system, denoted by ST$(v,s)$, if the number of occurrences of every 2-subset of $X$ in triples $BinB^+$ is one more than the number of occurrences in triples $BinB^-$. In this paper we prove that $st(v,s)$ exists if and only if $vequiv1,3pmod6$, $v e7$, and $sin{0,1,...,s_v-6,s_v-4,s_v}$, where $s_v=v(v-1)(v-3)/12$ and for $v=7$, $sin{0,2,3,5,6,8,14}$.