اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدHadamard diagonalizable graphs of order at most 36
118
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
If the Laplacian matrix of a graph has a full set of orthogonal eigenvectors with entries $pm1$, then the matrix formed by taking the columns as the eigenvectors is a Hadamard matrix and the graph is said to be Hadamard diagonalizable. In this article, we prove that if $n=8k+4$ the only possible Hadamard diagonalizable graphs are $K_n$, $K_{n/2,n/2}$, $2K_{n/2}$, and $nK_1$, and we develop an efficient computation for determining all graphs diagonalized by a given Hadamard matrix of any order. Using these two tools, we determine and present all Hadamard diagonalizable graphs up to order 36. Note that it is not even known how many Hadamard matrices there are of order 36.
قيم البحث
اقرأ أيضاً
In light of recent interest in Hadamard diagonalisable graphs (graphs whose Laplacian matrix is diagonalisable by a Hadamard matrix), we generalise this notion from real to complex Hadamard matrices. We give some basic properties and methods of const
ructing such graphs. We show that a large class of complex Hadamard diagonalisable graphs have vertex sets forming an equitable partition, and that the Laplacian eigenvalues must be even integers. We provide a number of examples and constructions of complex Hadamard diagonalisable graphs, including two special classes of graphs: the Cayley graphs over $mathbb{Z}_r^d$, and the non--complete extended $p$--sum (NEPS). We discuss necessary and sufficient conditions for $(alpha, beta)$--Laplacian fractional revival and perfect state transfer on continuous--time quantum walks described by complex Hadamard diagonalisable graphs and provide examples of such quantum state transfer.
The minimum rank of a simple graph $G$ is defined to be the smallest possible rank over all symmetric real matrices whose $ij$th entry (for $i eq j$) is nonzero whenever ${i,j}$ is an edge in $G$ and is zero otherwise. Minimum rank is a difficult par
ameter to compute. However, there are now a number of known reduction techniques and bounds that can be programmed on a computer; we have developed a program using the open-source mathematics software Sage to implement several techniques. We have also established several additional strategies for computation of minimum rank. These techniques have been used to determine the minimum ranks of all graphs of order 7. This paper contains a list of minimum ranks for all graphs of order at most 7. We also present selected optimal matrices.
The maximum matching width is a width-parameter that is defined on a branch-decomposition over the vertex set of a graph. The size of a maximum matching in the bipartite graph is used as a cut-function. In this paper, we characterize the graphs of ma
ximum matching width at most 2 using the minor obstruction set. Also, we compute the exact value of the maximum matching width of a grid.
Let $G$ be an $n$-vertex graph with adjacency matrix $A$, and $W=[e,Ae,ldots,A^{n-1}e]$ be the walk matrix of $G$, where $e$ is the all-one vector. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the author showed that any graph $G$ is uniq
uely determined by its generalized spectrum (DGS) whenever $2^{-lfloor n/2 rfloor}det W$ is odd and square-free. In this paper, we introduce a large family of graphs $mathcal{F}_n={$ $n$-vertex graphs $Gcolon, 2^{-lfloor n/2 rfloor}det W =p^2b$ and rank$W=n-1$ over $mathbb{Z}/pmathbb{Z}},$ where $b$ is odd and square-free, $p$ is an odd prime and $p mid b$. We prove that any graph in $mathcal{F}_n$ either is DGS or has exactly one generalized cospectral mate up to isomorphism. Moreover, we show that the problem of finding the generalized cospectral mate for a graph in $mathcal{F}_n$ is equivalent to that of generating an appropriate rational orthogonal matrix from a given integral vector. This equivalence essentially depends on an amazing property of graphs in terms of generalized spectra, which states that any symmetric integral matrix generalized cospectral with the adjacency matrix of some graph must be an adjacency matrix. Based on this equivalence, we develop an efficient algorithm to decide whether a given graph in $mathcal{F}_n$ is DGS and further to find the unique generalized cospectral mate when it is not. We give some experimental results on graphs with at most 20 vertices, which suggest that $mathcal{F}_n$ may have a positive density (nearly $3%$) and possibly almost all graphs in $mathcal{F}_n$ are DGS as $nrightarrow infty$. This gives a supporting evidence for Haemers conjecture that almost all graphs are determined by their spectra.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
