اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLargest regular multigraphs with three distinct eigenvalues
54
0
0.0
(
0
)
تأليف
Hiroshi Nozaki
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 t
hat 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-calle
d 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 disjoin
t 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
