Search

A complex unit gain graph ($\mathbb{T}$-gain graph), $\Phi = (G, \varphi)$ is a graph where the function $\varphi$ assigns a unit complex number to each orientation of an edge of $G$, and its inverse is assigned to the opposite orientation. A $ \mathbb{T} $-gain graph $\Phi$ is balanced if the product of the edge gains of each cycle (with a fixed orientation) is $1$. Signed graphs are special cases of $\mathbb{T}$-gain graphs. The adjacency matrix of $\Phi$, denoted by $ \mathbf{A}(\Phi)$ is defined canonically. The gain Laplacian for $\Phi$ is defined as $\mathbf{L}(\Phi) = \mathbf{D}(\Phi) - \mathbf{A}(\Phi)$, where $\mathbf{D}(\Phi)$ is the diagonal matrix with diagonal entries are the degrees of the vertices of $G$. The minimum number of vertices (resp., edges) to be deleted from $\Phi$ in order to get a balanced gain graph the frustration number (resp, frustration index). We show that frustration number and frustration index are bounded below by the smallest eigenvalue of $\mathbf{L}(\Phi)$. We provide several lower and upper bounds for extremal eigenvalues of $\mathbf{L}(\Phi)$ in terms of different graph parameters such as the number of edges, vertex degrees, and average $2$-degrees. The signed graphs are particular cases of the $\mathbb{T}$-gain graphs, all the bounds established in paper hold for signed graphs. Most of the bounds established here are new for signed graphs. Finally, we perform comparative analysis for all the obtained bounds in the paper with the state-of-the-art bounds available in the literature for randomly generated Erd\H{o}s-Re\'yni graphs. Some of the major highlights of our paper are the gain-dependent bounds, limit convergence of the bounds to the extremal eigenvalues, and optimal extremal bounds obtained by posing optimization problems to achieve the best possible bounds., Comment: Preliminary version. 32 pages

Given a d-dimensional tensor T:A ×…×A →F (where F is a field), the i-flattening rank of T is the rank of the matrix whose rows are indexed by A , columns are indexed by B =A ×…×A ×A ×…×A and whose entries are given by the corresponding values of T. The max-flattening rank of T is defined as mfrank(T)=max frank (T). A tensor T:A →F is called semi-diagonal, if T(a,…,a)≠0 for every a∈A, and T(a ,…,a )=0 for every a ,…,a ∈A that are all distinct. In this paper we prove that if T:A →F is semi-diagonal, then mfrank(T)≥[Formula presented], and this bound is the best possible. We give several applications of this result, including a generalization of the celebrated Frankl-Wilson theorem on forbidden intersections. Also, addressing a conjecture of Aharoni and Berger, we show that if the edges of an r-uniform multi-hypergraph H are colored with z colors such that each color class is a matching of size t, then H contains a rainbow matching of size t provided z>(t−1)(rtr). This improves previous results of Alon and Glebov, Sudakov, and Szabó., Linear Algebra and its Applications, 625, ISSN:0024-3795, ISSN:1873-1856

Let $V$ be a finite-dimensional vector space over the finite field ${\mathbb F}_q$ and suppose $W$ and $\widetilde{W}$ are subspaces of $V$. Two linear transformations $T:W\to V$ and $\widetilde{T}:\widetilde{W}\to V$ are said to be similar if there exists a linear isomorphism $S:V\to V$ with $SW=\widetilde{W}$ such that $S\circ T=\widetilde{T}\circ S $. Given a linear map $T$ defined on a subspace $W$ of $V$, we give an explicit formula for the number of linear maps that are similar to $T$. Our results extend a theorem of Philip Hall that settles the case $W=V$ where the above problem is equivalent to counting the number of square matrices over ${\mathbb F}_q$ in a conjugacy class., 15 pages, 3 figures

Identifying graphs with extremal properties is an extensively studied topic in spectral graph theory. In this paper, we study the log-concavity of a type of iteration sequence related to the $\alpha$-normal weighted incidence matrices which is presented by Lu and Man for computing the spectral radius of hypergraphs. By using results obtained about the sequence and the method of some edge operations, we will characterize completely extremal k-graphs with the smallest spectral radius among bicyclic hypergraphs with given size., Comment: 22 pages, 3 figures

Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations.

In this paper, structural properties of chordal graphs are analysed, in order to establish a relationship between these structures and integer Laplacian eigenvalues. We present the characterization of chordal graphs with equal vertex and algebraic connectivities, by means of the vertices that compose the minimal vertex separators of the graph; we stablish a sufficient condition for the cardinality of a maximal clique to appear as an integer Laplacian eigenvalue. Finally, we review two subclasses of chordal graphs, showing for them some new properties., 15 pages, 5 figures

The distance energy of a simple connected graph $G$ is defined as the sum of absolute values of its distance eigenvalues. In this paper, we mainly give a positive answer to a conjecture of distance energy of clique trees proposed by Lin, Liu and Lu [H.~Q.~ Lin, R.~F.~Liu, X.~W.~Lu, The inertia and energy of the distance matrix of a connected graph, {\it Linear Algebra Appl.,} 467 (2015), 29-39.], Comment: 10 pages, 1 figure

Let $A$ be an $n \times n$ positive definite Hermitian matrix with all eigenvalues between 1 and 2. We represent the permanent of $A$ as the integral of some explicit log-concave function on ${\Bbb R}^{2n}$. Consequently, there is a fully polynomial randomized approximation scheme (FPRAS) for the permanent of $A$., 5 pages

In quantum information theory there is a construction for quantum channels, appropriately called a quantum graph, that generalizes the confusability graph construction for classical channels in classical information theory. In this paper, we provide a definition of connectedness for quantum graphs that generalizes the classical definition. This is used to prove a quantum version of a particular case of the classical tree-packing theorem from graph theory. Generalizations for the related notions of $k$-connectedness and of orthogonal representation are also proposed for quantum graphs, and it is shown that orthogonal representations have the same implications for connectedness as they do in the classical case., Comment: 15 pages

Let $\kappa'(G)$, $\kappa(G)$, $\mu_{n-1}(G)$ and $\mu_1(G)$ denote the edge-connectivity, vertex-connectivity, the algebraic connectivity and the Laplacian spectral radius of $G$, respectively. In this paper, we prove that for integers $k\geq 2$ and $r\geq 2$, and any simple graph $G$ of order $n$ with minimum degree $\delta\geq k$, girth $g\geq 3$ and clique number $\omega(G)\leq r$, the edge-connectivity $\kappa'(G)\geq k$ if $\mu_{n-1}(G) \geq \frac{(k-1)n}{N(\delta,g)(n-N(\delta,g))}$ or if $\mu_{n-1}(G) \geq \frac{(k-1)n}{\varphi(\delta,r)(n-\varphi(\delta,r))}$, where $N(\delta,g)$ is the Moore bound on the smallest possible number of vertices such that there exists a $\delta$-regular simple graph with girth $g$, and $\varphi(\delta,r) = \max\{\delta+1,\lfloor\frac{r\delta}{r-1}\rfloor\}$. Analogue results involving $\mu_{n-1}(G)$ and $\frac{\mu_1(G)}{\mu_{n-1}(G)}$ to characterize vertex-connectivity of graphs with fixed girth and clique number are also presented. Former results in [Linear Algebra Appl. 439 (2013) 3777--3784], [Linear Algebra Appl. 578 (2019) 411--424], [Linear Algebra Appl. 579 (2019) 72--88], [Appl. Math. Comput. 344-345 (2019) 141--149] and [Electronic J. Linear Algebra 34 (2018) 428--443] are improved or extended., Comment: 14 pages

A universal adjacency matrix of a graph G with adjacency matrix A is any matrix of the form U = α A + β I + γ J + δ D with α ≠ 0 , where I is the identity matrix, J is the all-ones matrix and D is the diagonal matrix with the vertex degrees. In the case that G is the disjoint union of regular graphs, we present an expression for the characteristic polynomials of the various universal adjacency matrices in terms of the characteristic polynomials of the adjacency matrices of the components. As a consequence we obtain a formula for the characteristic polynomial of the Seidel matrix of G, and the signless Laplacian of the complement of G (i.e. the join of regular graphs). The main tool is a simple but useful lemma on equitable matrix partitions. With this note we also want to propagate this technique.

The almost-principal rank characteristic sequence (apr-sequence) of an n × n symmetric matrix is introduced, which is defined to be the string a 1 a 2 ⋯ a n − 1 , where a k is either A , S , or N , according as all, some but not all, or none of its almost-principal minors of order k are nonzero. In contrast to the other principal rank characteristic sequences in the literature, the apr-sequence of a matrix does not depend on principal minors. The almost-principal rank of a symmetric matrix B, denoted by ap-rank ( B ) , is defined as the size of a largest nonsingular almost-principal submatrix of B. A complete characterization of the sequences not containing an A that can be realized as the apr-sequence of a symmetric matrix over a field F is provided. A necessary condition for a sequence to be the apr-sequence of a symmetric matrix over a field F is presented. It is shown that if B ∈ F n × n is symmetric and non-diagonal, then rank ( B ) − 1 ≤ ap-rank ( B ) ≤ rank ( B ) , with both bounds being sharp. Moreover, it is shown that if B is symmetric, non-diagonal and singular, and does not contain a zero row, then rank ( B ) = ap-rank ( B ) .

We characterize the spectrum of the Laplacian of graphs composed of one or two finite or infinite chains connected to a complete graph. We show the existence of localized eigenvectors of two types, eigenvectors that vanish exactly outside the complete graph and eigenvectors that decrease exponentially outside the complete graph. Our results also imply gaps between the eigenvalues corresponding to localized and extended eigenvectors.

Quantum walks on undirected graphs have been studied using symmetric matrices, such as the adjacency or Laplacian matrix, and many results about perfect state transfer are known. We extend some of those results to oriented graphs. We also study the phenomena, unique to oriented graphs, of multiple state transfer, where there is a set of vertices such that perfect state transfer occurs between every pair in that set. We give a characterization of multiple state transfer, and a new example of a graph where it occurs., Comment: 17 pages, 3 figures

For a graph $G=(V, E)$ and $i, j\in V$, denote the distance between $i$ and $j$ in $G$ by $D(i, j)$ and the degrees of $i$, $j$ by $d_i$, $d_j$, respectively. Let $f(D(i, j), d_{i}, d_{j})$ be a function symmetric in $i$ and $j$. Define a matrix $W_f(G)$, called the weighted distance matrix, of $G$, with the $ij$-entry $W_f(G)(i, j)=f(D(i, j), d_{i}, d_{j})$ if $i\neq j$ and $W_f(G)(i, j)=0$ if $i=j$. In this paper, we prove that if the symmetric function $f$ satisfies that $f(D(i, j), (1+o(1))np, (1+o(1))np)=(1+o(1))f(D(i, j), np, np)$, then for almost all graphs $G_p$ in the $Erd\ddot{o}s$-$R\acute{e}nyi$ random graph model $\mathcal{G}_{n, p}$, the energy of $W_f(G_p)$ is $\{(\frac{8}{3\pi}\sqrt{p(1-p)}+o(1))\cdot|f(1, np, np)-f(2, np, np)|+o(|f(2, np, np)|)\}\cdot n^{3/2}$. As a consequence, we give the asymptotic values of energies of a variety of weighted distance matrices with function $f$ from distance-based only and mixed with degree-distance-based topological indices of chemical use. This generalizes our former result with only degree-based weights., Comment: 15 pages

We consider elements of finite order in the Riordan group $\cal R$ over a field of characteristic $0$. Viewing $\cal R$ as a semi-direct product of groups of formal power series, we solve, for all $n \geq 2$, two foundational questions posed by L. Shapiro for the case $n = 2$ (`involutions'): Given a formal power series $F(x)$ of finite compositional order and an integer $n\geq 2$, Theorem 1 states, exactly which $g(x)$ make $\big(g(x), F(x)\big)$ a Riordan element of order $n$. Theorem 2 classifies finite-order Riordan group elements up to conjugation in $\cal R$. Viewing $\cal R$ as a group of infinite lower triangular matrices, we interpret Theorem 1 in terms of existence of eigenvectors and Theorem 2 as a normal form for finite order Riordan arrays under similarity. These lead to Theorem 3, a formula for all eigenvectors of finite order Riordan arrays; and we show how this can lead to interesting combinatorial identities. We then relate our work to papers of Cheon and Kim which motivated this paper and we solve the Open question which they posed. Finally, this circle of ideas gives a new proof of C. Marshall's theorem, which finds the unique $F(x)$, given bi-invertible $g(x)$, such that $\big(g(x), F(x))$ is an involution., Comment: 25 pages. Version 4 corrects the statement of Example 5.6 in the case when $n$ is odd, and adjusts the last four lines of the proof accordingly

In this paper we study the adjacency spectrum of families of finite rooted trees with regular branching properties. In particular, we show that in the case of constant branching, the eigenvalues are realized as the roots of a family of generalized Fibonacci polynomials and produce a limiting distribution for the eigenvalues as the tree depth goes to infinity. We indicate how these results can be extended to periodic branching patterns and also provide a generalization to higher order simplicial complexes., 18 pages, 3 figures. Updated version contains additional results and expanded references. Accepted for publication in Linear Algebra and its Applications

Distance ideals generalize the Smith normal form of the distance matrix of a graph. The family of graphs with 2 trivial distance ideals contains the family of graphs whose distance matrix has at most 2 invariant factors equal to 1. Here we give an infinite family of forbidden induced subgraphs for the graphs with 2 trivial distance ideals. These are also related with other well known graph classes., Some typos were corrected

We consider the exact recovery problem in the hypergraph stochastic block model (HSBM) with k blocks of equal size. More precisely, we consider a random d-uniform hypergraph H with n vertices partitioned into k clusters of size s = n / k . Hyperedges e are added independently with probability p if e is contained within a single cluster and q otherwise, where 0 ≤ q p ≤ 1 . We present a spectral algorithm which recovers the clusters exactly with high probability, given mild conditions on n , k , p , q , and d. Our algorithm is based on the adjacency matrix of H, which is a symmetric n × n matrix whose ( u , v ) -th entry is the number of hyperedges containing both u and v. To the best of our knowledge, our algorithm is the first to guarantee exact recovery when the number of clusters k = Θ ( n ) .

Recently, Anderson et al. (2019) proposed the concept of rankability, which refers to a dataset's inherent ability to produce a meaningful ranking of its items. In the same paper, they proposed a rankability measure that is based on an integer program for computing the minimum number of edge changes made to a directed graph in order to obtain a complete dominance graph, i.e., an acyclic tournament graph. In this article, we prove a spectral-degree characterization of complete dominance graphs and apply this characterization to produce a new measure of rankability that is cost-effective and more widely applicable. We support the details of our algorithm with several results regarding the conditioning of the Laplacian spectrum of complete dominance graphs and the Hausdorff distance between their Laplacian spectrum and that of an arbitrary directed graph with weights between zero and one. Finally, we analyze the rankability of datasets from the world of chess and college football.

The purpose of this paper is to highlight the role played by the anti-regular graph within the class of threshold graphs. Using the fact that every threshold graph contains a maximal anti-regular graph, we show that some known results, and new ones, on the spectral properties of threshold graphs can be deduced from (i) the known results on the eigenvalues of anti-regular graphs, (ii) the subgraph structure of threshold graphs, and (iii) eigenvalue interlacing. In particular, we prove a strengthened version of the recently proved fact that no threshold graph contains an eigenvalue in the interval Ω = [ − 1 − 2 2 , − 1 + 2 2 ] , except possibly the trivial eigenvalues −1 and/or 0, determine the inertia of a threshold graph, and give partial results on a conjecture regarding the optimality of the non-trivial eigenvalues of an anti-regular graph within the class of threshold graphs.

We discuss the Grassmann graph $J_q(N,D)$ with $N \geq 2D$, having as vertices the $D$-dimensional subspaces of an $N$-dimensional vector space over the finite field $\mathbb{F}_q$. This graph is distance-regular with diameter $D$; to avoid trivialities we assume $D\geq 3$. Fix a pair of a Delsarte clique $C$ of $J_q(N,D)$ and a vertex $x$ in $C$. We construct a $2D$-dimensional irreducible module $\mathbf{W}$ for the Terwilliger algebra $\mathbf{T}$ of $J_q(N,D)$ associated with the pair $x$, $C$. We show that $\mathbf{W}$ is an irreducible module for the confluent Cherednik algebra $\mathcal{H}_\mathrm{V}$ and describe how the $\mathbf{T}$-action on $\mathbf{W}$ is related to the $\mathcal{H}_\mathrm{V}$-action on $\mathbf{W}$. Using the $\mathcal{H}_\mathrm{V}$-module $\mathbf{W}$, we define non-symmetric dual $q$-Hahn polynomials and prove their recurrence and orthogonality relations from a combinatorial viewpoint., Comment: 31 pages, 3 figures

Let $\pi=\{V_1,\dots,V_r\}$ be an equitable partition of the vertex set of a directed graph (digraph) $X$. It is well known that the characteristic polynomial $\phi(X/\pi,x)$ of a quotient graph $X/\pi$ divides that of $X$, but the remainder part is not well investigated. In this paper, we define a deletion graph $X\backslash\pi$ over an equitable partition $\pi$, which is a signed directed graph defined for a fixed set of deleting vertices $\{\bar{v}_i\in V_i, i=1,\cdots,r\}$, and give a similarity transformation exchanging the adjacency matrix $A(X)$ which is compatible with the equitable partition for a block triangular matrix whose diagonal blocks are the adjacency matrix of the quotient graph and the deletion graph. In fact, we show the result for more general matrices including adjacency matrix of graphs, and as corollaries, we show the followings: (i) a decomposition formula of the reciprocal of the Ihara-Bartholdi zeta function over an equitably partitioned undirected graph into the quotient graph part and the deletion graph part, and (ii) Chen and Chen's result ([CC17, Theorem 3.1]) on the Ihara-Bartholdi zeta functions on generalized join graphs, and (iii) Teranishi's result [Ter03, Theorem 3.3]., Comment: 18 pages

We consider the symmetric group Sym n , n ⩾ 2 , generated by the set S of transpositions ( 1 i ) , 2 ⩽ i ⩽ n , and the Cayley graph S n = C a y ( Sym n , S ) called the Star graph. For any positive integers n ⩾ 3 and m with n > 2 m , we present a family of eigenfunctions of S n with eigenvalue n − m − 1 and call them PI-eigenfunctions. We then establish a connection of these functions with the standard basis of a Specht module. Finally, in the case of the largest non-principal eigenvalue n − 2 we prove that any eigenfunction of S n can be reconstructed by its values on the second neighbourhood of a vertex.

A d-dimensional matrix is called 1-polystochastic if it is non-negative and the sum over each line equals 1. Such a matrix that has a single 1 in each line and zeros elsewhere is called a 1-permutation matrix. A diagonal of a d-dimensional matrix of order n is a choice of n elements, no two in the same hyperplane. The permanent of a d-dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal. For a given order n and dimension d, the set of 1-polystochastic matrices forms a convex polytope that includes the 1-permutation matrices within its set of vertices. For even n and odd d, we give a construction for a class of 1-permutation matrices with zero permanent. Consequently, we show that the set of 1-polystochastic matrices with zero permanent contains at least n n 3 / 2 ( 1 / 2 − o ( 1 ) ) 1-permutation matrices and contains a polytope of dimension at least c n 3 / 2 for fixed c , d and even n → ∞ . We also provide counterexamples to a conjecture by Taranenko [11] about the location of local extrema of the permanent. For odd d, we give a construction of 1-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko [11] to provide counterexamples to a conjecture by Dow and Gibson [4] generalising van der Waerden's conjecture to higher dimensions.

In an earlier work, the author together with Guo [Hermitian adjacency matrix of digraphs and mixed graphs, J. Graph Theory 85 (2017) 217-248] introduced the Hermitian adjacency matrix of directed (and partially directed) graphs. However, it appears that a more natural Hermitian matrix exists, and it is the purpose of this note to bring this new Hermitian matrix to the attention of researchers in algebraic graph theory., Comment: Linear Algebra Appl. (2019), in press. arXiv admin note: text overlap with arXiv:1505.01321

A signed graph $\Gamma(G)$ is a graph with a sign attached to each of its edges, where $G$ is the underlying graph of $\Gamma(G)$. The energy of a signed graph $\Gamma(G)$ is the sum of the absolute values of the eigenvalues of the adjacency matrix $A(\Gamma(G))$ of $\Gamma(G)$. The random signed graph model $\mathcal{G}_n(p, q)$ is defined as follows: Let $p, q \ge 0$ be fixed, $0 \le p+q \le 1$. Given a set of $n$ vertices, between each pair of distinct vertices there is either a positive edge with probability $p$ or a negative edge with probability $q$, or else there is no edge with probability $1-(p+ q)$. The edges between different pairs of vertices are chosen independently. In this paper, we obtain an exact estimate of energy for almost all signed graphs. Furthermore, we establish lower and upper bounds to the energy of random multipartite signed graphs., Comment: 11 page, 0 figures. arXiv admin note: text overlap with arXiv:0909.4923 by other authors

Every Riordan array has what we call a horizontal half and a vertical half. These halves of a Riordan array have been studied separately before. Here, we place them in a common context, showing that one may be obtained from the other. We also ask and answer the question: given a Riordan array, when is it the half (either horizontal of vertical) of a Riordan array?, 19 pages, extended from first version

In this note we prove that the vertex energy of a graph, as defined in Arizmendi and Juarez (2018), can be calculated in terms of a Coulson integral formula. We present examples of how this formula can be used, and we show some applications to bipartite graphs., 14 pages, 5 figures

Let $G$ be a weakly connected directed graph with asymmetric graph Laplacian ${\cal L}$. Consensus and diffusion are dual dynamical processes defined on $G$ by $\dot x=-{\cal L}x$ for consensus and $\dot p=-p{\cal L}$ for diffusion. We consider both these processes as well their discrete time analogues. We define a basis of row vectors $\{\bar \gamma_i\}_{i=1}^k$ of the left null-space of ${\cal L}$ and a basis of column vectors $\{\gamma_i\}_{i=1}^k$ of the right null-space of ${\cal L}$ in terms of the partition of $G$ into strongly connected components. This allows for complete characterization of the asymptotic behavior of both diffusion and consensus --- discrete and continuous --- in terms of these eigenvectors. As an application of these ideas, we present a treatment of the pagerank algorithm that is dual to the usual one. We further show that the teleporting feature usually included in the algorithm is not strictly necessary. This is a complete and self-contained treatment of the asymptotics of consensus and diffusion on digraphs. Many of the ideas presented here can be found scattered in the literature, though mostly outside mainstream mathematics and not always with complete proofs. This paper seeks to remedy this by providing a compact and accessible survey., Comment: 19 pages, Survey Article, 1 figure

Let G be a connected m-uniform hypergraph. In this paper we mainly consider the eigenvectors of the Laplacian or signless Laplacian tensor of G associated with zero eigenvalue, called the first Laplacian or signless Laplacian eigenvectors of G. By means of the incidence matrix of G, the number of first Laplacian or signless Laplacian (or H-)eigenvectors can be obtained explicitly by solving the Smith normal form of the incidence matrix over Z m (or Z 2 ). Consequently, we prove that the number of first Laplacian (H-)eigenvectors is equal to the number of first signless Laplacian (H-)eigenvectors when zero is an (H-)eigenvalue of the signless Laplacian tensor. We establish a connection between first Laplacian (signless Laplacian) H-eigenvectors and the even (odd) bipartitions of G.

We give a counterexample to a conjecture of Wang and Hou related with the sum of the $k$ largest Laplacian eigenvalues of signed graphs., 3 pages, 2 figures

Let G be a finite graph, and let G_n be the n-th iterated cone over G. We study the structure of the critical group of G_n arising in divisor and sandpile theory., 4 pages; to appear in Linear Algebra and its Applications; an example is added in version 2

Submitted by Enide Martins (enide@ua.pt) on 2018-12-29T19:16:02Z No. of bitstreams: 1 Trabajo sometidoEnideGeirLauraREV.pdf: 287985 bytes, checksum: b42325a10a306059a51293a6acc9b31f (MD5) Approved for entry into archive by Diana Silva (dianasilva@ua.pt) on 2019-01-10T17:22:19Z (GMT) No. of bitstreams: 1 Trabajo sometidoEnideGeirLauraREV.pdf: 287985 bytes, checksum: b42325a10a306059a51293a6acc9b31f (MD5) Made available in DSpace on 2019-01-10T17:22:19Z (GMT). No. of bitstreams: 1 Trabajo sometidoEnideGeirLauraREV.pdf: 287985 bytes, checksum: b42325a10a306059a51293a6acc9b31f (MD5) Previous issue date: 2019-04 published

It is known that complete multipartite graphs are determined by their distance spectrum but not by their adjacency spectrum. The Seidel spectrum of a graph $G$ on more than one vertex does not determine the graph, since any graph obtained from $G$ by Seidel switching has the same Seidel spectrum. We consider $G$ to be determined by its Seidel spectrum, up to switching, if any graph with the same spectrum is switching equivalent to a graph isomorphic to $G$. It is shown that any graph which has the same spectrum as a complete $k$-partite graph is switching equivalent to a complete $k$-partite graph, and if the different partition sets sizes are $p_1,\ldots, p_l$, and there are at least three partition sets of each size $p_i$, $i=1,\ldots, l$, then $G$ is determined, up to switching, by its Seidel spectrum. Sufficient conditions for a complete tripartite graph to be determined by its Seidel spectrum are discussed, and a conjecture is made on complete tripartite graphs on more than 18 vertices., 12 page 2 figures

It is proved that for any finite connected graph G, there exists an orientation of G such that the spectral radius of the corresponding Hermitian adjacency matrix is smaller or equal to the spectral radius of the universal cover of G (with equality if and only if G is a tree). This provides a suitable answer to a problem proposed by Mohar. The proof uses the method of interlacing families of polynomials that was developed by Marcus, Spielman, and Srivastava in their seminal work on the existence of infinite families of Ramanujan graphs.

In this paper, we determine the maximum number of nonzero entries in 0-1 matrices of order $n$ with zero trace whose squares are 0-1 matrices when $n\ge 8$. The extremal matrices attaining this maximum number are also characterized., Comment: 20 pages, 11 figures

A partial matrix over a field $\mathbb{F}$ is a matrix whose entries are either an element of $\mathbb{F}$ or an indeterminate and with each indeterminate only appearing once. A completion is an assignment of values in $\mathbb{F}$ to all indeterminates. Given a partial matrix, through elementary row operations and column permutation it can be decomposed into a block matrix of the form $\left[\begin{smallmatrix}{\bf W} & * & * \\ 0 & {\bf S} & * \\ 0 & 0 & {\bf T} \end{smallmatrix}\right]$ where ${\bf W}$ is wide (has more columns than rows), ${\bf S}$ is square, ${\bf T}$ is tall (has more rows than columns), and these three blocks have at least one completion with full rank. And importantly, each one of the blocks ${\bf W}$, ${\bf S}$ and ${\bf T}$ is unique up to elementary row operations and column permutation whenever ${\bf S}$ is required to be as large as possible. When this is the case $\left[\begin{smallmatrix}{\bf W} & * & * \\ 0 & {\bf S} & * \\ 0 & 0 & {\bf T} \end{smallmatrix}\right]$ will be called a WST-decomposition. With this decomposition it is trivial to compute maximum rank of a completion of the original partial matrix: $\#\mbox{rows}({\bf W})+\#\mbox{rows}({\bf S})+\#\mbox{cols}({\bf T})$. In fact we introduce the WST-decomposition for a broader class of matrices: the ACI-matrices.

Finding a diagonal matrix congruent to $A - cI$ for constants $c$, where $A$ is the adjacency matrix of a graph $G$ allows us to quickly tell the number of eigenvalues in a given interval. If $G$ has clique-width $k$ and a corresponding $k$-expression is known, then diagonalization can be done in time $O(\text{poly}(k) n)$ where $n$ is the order of $G$., Comment: 25 pages

We study the eigenvalues of the unique connected anti-regular graph $A_n$. Using Chebyshev polynomials of the second kind, we obtain a trigonometric equation whose roots are the eigenvalues and perform elementary analysis to obtain an almost complete characterization of the eigenvalues. In particular, we show that the interval $\Omega=[\tfrac{-1-\sqrt{2}}{2}, \tfrac{-1+\sqrt{2}}{2}]$ contains only the trivial eigenvalues $\lambda = -1$ or $\lambda=0$, and any closed interval strictly larger than $\Omega$ will contain eigenvalues of $A_n$ for all $n$ sufficiently large. We also obtain bounds for the maximum and minimum eigenvalues, and for all other eigenvalues we obtain interval bounds that improve as $n$ increases. Moreover, our approach reveals a more complete picture of the bipartite character of the eigenvalues of $A_n$, namely, as $n$ increases the eigenvalues are (approximately) symmetric about the number $-\tfrac{1}{2}$. We also obtain an asymptotic distribution of the eigenvalues as $n\rightarrow\infty$. Finally, the relationship between the eigenvalues of $A_n$ and the eigenvalues of a general threshold graph is discussed., Comment: 20 pages, 6 figures, 1 table

We show that there is no (75,32,10,16) strongly regular graph. The result is obtained by a mix of algebraic and computational approaches. The main idea is to build large enough induced structure and apply the star complement technique. Our result implies that there is no regular two-graph on 76 vertices and no partial geometry with parameters pg(4,7,2). In particular, it implies that there is no (76,35,18,14) strongly-regular graph. In order to solve this classification problem we also develop an efficient algorithm for the problem of finding a maximal clique in a graph., 28 pages

For a graph G, let λ 2 ( G ) denote its second smallest Laplacian eigenvalue. It was conjectured that λ 2 ( G ) + λ 2 ( G ‾ ) ≥ 1 , where G ‾ is the complement of G. In this paper, it is shown that max ⁡ { λ 2 ( G ) , λ 2 ( G ‾ ) } ≥ 2 5 .

We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1 ≤ h ≤ k ≤ n 2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G). We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph Kn and the star Sn = K1,n−1, respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G. This generalizes to tokens graphs a wellknown property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of G. Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph. This research of C. Dalfó and M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalfó has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by MICINN from the Spanish Government under project PID2019-104129GB-I00/AEI/10.13039/501100011033 and AGAUR from the Catalan Government under project 017SGR1336. F.J. Zaragoza Martínez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922

A signed graph Γ is said to be determined by its spectrum if every signed graph with the same spectrum as Γ is switching isomorphic with Γ. Here it is proved that the path P n , interpreted as a signed graph, is determined by its spectrum if and only if n ≡ 0 , 1 , or 2 (mod 4), unless n ∈ { 8 , 13 , 14 , 17 , 29 } , or n = 3 .

For $r\geq 3$, let $f_r\colon [0,\infty)\to [1,\infty)$ be the unique analytic function such that $f_r({k\choose r})={k-1\choose r-1}$ for any $k\geq r-1$. We prove that the spectral radius of an $r$-uniform hypergraph $H$ with $e$ edges is at most $f_r(e)$. The equality holds if and only if $e={k\choose r}$ for some positive integer $k$ and $H$ is the union of a complete $r$-uniform hypergraph $K_k^r$ and some possible isolated vertices. This result generalizes the classical Stanley's theorem on graphs., 16 pages

We show that the tensor rank of tensor product of two three-qubit W states is not less than eight. Combining this result with the recent result of M. Christandl, A. K. Jensen, and J. Zuiddam that the tensor rank of tensor product of two three-qubit W states is at most eight, we deduce that the tensor rank of tensor product of two three-qubit W states is eight. We also construct the upper bound of the tensor rank of tensor product of many three-qubit W states., Comment: 10 pages, accepted by Linear Algebra and Applications

A rose graph is a graph consisting of cycles that all meet in one vertex. We show that except for two specific examples, these rose graphs are determined by the Laplacian spectrum, thus proving a conjecture posed by Lui and Huang [F.J. Liu and Q.X. Huang, Laplacian spectral characterization of 3-rose graphs, Linear Algebra Appl. 439 (2013), 2914--2920]. We also show that if two rose graphs have a so-called universal Laplacian matrix with the same spectrum, then they must be isomorphic. In memory of Horst Sachs (1927-2016), we show the specific case of the latter result for the adjacency matrix by using Sachs' theorem and a new result on the number of matchings in the disjoint union of paths.

The distance matrix of a connected graph is the symmetric matrix with columns and rows indexed by the vertices and entries that are the pairwise distances between the corresponding vertices. We give a construction for graphs which differ in their edge counts yet are cospectral with respect to the distance matrix. Further, we identify a subgraph switching behavior which constructs additional distance cospectral graphs. The proofs for both constructions rely on a perturbation of (most of) the distance eigenvectors of one graph to yield the distance eigenvectors of the other., Comment: 17 pages, 4 figures

The notions of weakly bipartitive and bipartitive families were introduced by Montgolfier (2003) as a general tool for studying some decomposition of graphs and other combinatorial structures. In this paper, we give a matrix description of these notions., 10 pages, 2 figures

We extend the theory of equitable decompositions introduced in [2] , where it was shown that if a graph has a particular type of symmetry, i.e. a uniform or basic automorphism ϕ, it is possible to use ϕ to decompose a matrix M appropriately associated with the graph. The result is a number of strictly smaller matrices whose collective eigenvalues are the same as the eigenvalues of the original matrix M. We show here that a large class of automorphisms, which we refer to as separable, can be realized as a sequence of basic automorphisms, allowing us to equitably decompose M over any such automorphism. We also show that not only can a matrix M be decomposed but that the eigenvectors of M can also be equitably decomposed. Additionally, we prove under mild conditions that if a matrix M is equitably decomposed the resulting divisor matrix, which is the divisor matrix of the associated equitable partition, will have the same spectral radius as the original matrix M. Last, we describe how an equitable decomposition effects the Gershgorin region Γ ( M ) of a matrix M, which can be used to localize the eigenvalues of M. We show that the Gershgorin region of an equitable decomposition of M is contained in the Gershgorin region Γ ( M ) of the original matrix. We demonstrate on a real-world network that by a sequence of equitable decompositions it is possible to significantly reduce the size of a matrix Gershgorin region.