Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLargest regular multigraphs with three distinct eigenvalues
54
0
0.0
(
0
)
Authors
Hiroshi Nozaki
Ask ChatGPT about the research
No Arabic abstract
We deal with connected $k$-regular multigraphs of order $n$ that has only three distinct eigenvalues. In this paper, we study the largest possible number of vertices of such a graph for given $k$. For $k=2,3,7$, the Moore graphs are largest. For $k e 2,3,7,57$, we show an upper bound $nleq k^2-k+1$, with equality if and only if there exists a finite projective plane of order $k-1$ that admits a polarity.
rate research
Read More
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.
In his survey Beyond graph energy: Norms of graphs and matrices (2016), Nikiforov proposed two problems concerning characterizing the graphs that attain equality in a lower bound and in a upper bound for the energy of a graph, respectively. We show that these graphs have at most two nonzero distinct absolute eigenvalues and investigate the proposed problems organizing our study according to the type of spectrum they can have. In most cases all graphs are characterized. Infinite families of graphs are given otherwise. We also show that all graphs satifying the properties required in the problems are integral, except for complete bipartite graphs $K_{p,q}$ and disconnected graphs with a connected component $K_{p,q}$, where $pq$ is not a perfect square.
Chung, Graham, and Wilson proved that a graph is quasirandom if and only if there is a large gap between its first and second largest eigenvalue. Recently, the authors extended this characterization to k-uniform hypergraphs, but only for the so-called coregular k-uniform hypergraphs. In this paper, we extend this characterization to all k-uniform hypergraphs, not just the coregular ones. Specifically, we prove that if a k-uniform hypergraph satisfies the correct count of a specially defined four-cycle, then there is a gap between its first and second largest eigenvalue.
Appearing in different format, Gupta,(1967), Goldberg,(1973), Andersen,(1977), and Seymour,(1979) conjectured that if $G$ is an edge-$k$-critical graph with $k ge Delta +1$, then $|V(G)|$ is odd and, for every edge $e$, $E(G-e)$ is a union of disjoint near-perfect matchings, where $Delta$ denotes the maximum degree of $G$. Tashkinov tree method shows that critical graphs contain a subgraph with two important properties named closed and elementary. Recently, efforts have been made in extending graphs beyond Tashkinov trees. However, these results can only keep one of the two essential properties. In this paper, we developed techniques to extend Tashkinov trees to larger subgraphs with both properties. Applying our result, we have improved almost all known results towards Goldbergs conjecture. In particular, we showed that Goldbergs conjecture holds for graph $G$ with $|V(G)| le 39$ and $|Delta(G)| le 39$ and Jacobsens equivalent conjecture holds for $m le 39$ while the previous known bound is $23$.
We study ErdH oss distinct distances problem under $ell_p$ metrics with integer $p$. We improve the current best bound for this problem from $Omega(n^{4/5})$ to $Omega(n^{6/7-epsilon})$, for any $epsilon>0$. We also characterize the sets that span an asymptotically minimal number of distinct distances under the $ell_1$ and $ell_infty$ metrics.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
