Do you want to publish a course? Click here

The inverse inertia problem for the complements of partial $k$-trees

143   0   0.0 ( 0 )
 Added by Hein van der Holst
 Publication date 2012
  fields
and research's language is English




Ask ChatGPT about the research

Let $mathbb{F}$ be an infinite field with characteristic different from two. For a graph $G=(V,E)$ with $V={1,...,n}$, let $S(G;mathbb{F})$ be the set of all symmetric $ntimes n$ matrices $A=[a_{i,j}]$ over $mathbb{F}$ with $a_{i,j} ot=0$, $i ot=j$ if and only if $ijin E$. We show that if $G$ is the complement of a partial $k$-tree and $mgeq k+2$, then for all nonsingular symmetric $mtimes m$ matrices $K$ over $mathbb{F}$, there exists an $mtimes n$ matrix $U$ such that $U^T K Uin S(G;mathbb{F})$. As a corollary we obtain that, if $k+2leq mleq n$ and $G$ is the complement of a partial $k$-tree, then for any two nonnegative integers $p$ and $q$ with $p+q=m$, there exists a matrix in $S(G;reals)$ with $p$ positive and $q$ negative eigenvalues.



rate research

Read More

Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n x n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G). We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, and investigate restrictions on the inertia set of any graph.
The inverse eigenvalue problem of a graph $G$ aims to find all possible spectra for matrices whose $(i,j)$-entry, for $i eq j$, is nonzero precisely when $i$ is adjacent to $j$. In this work, the inverse eigenvalue problem is completely solved for a subfamily of clique-path graphs, in particular for lollipop graphs and generalized barbell graphs. For a matrix $A$ with associated graph $G$, a new technique utilizing the strong spectral property is introduced, allowing us to construct a matrix $A$ whose graph is obtained from $G$ by appending a clique while arbitrary list of eigenvalues is added to the spectrum. Consequently, many spectra are shown realizable for block graphs.
132 - Minjie Zhang , Shuchao Li 2015
In this paper, we use a new and correct method to determine the $n$-vertex $k$-trees with the first three largest signless Laplacian indices.
68 - Ricky X. F. Chen 2019
In this paper, we present an involution on some kind of colored $k$-ary trees which provides a combinatorial proof of a combinatorial sum involving the generalized Catalan numbers $C_{k,gamma}(n)=frac{gamma}{k n+gamma}{k n+gammachoose n}$. From the combinatorial sum, we refine the formula for $k$-ary trees and obtain an implicit formula for the generating function of the generalized Catalan numbers which obviously implies a Vandermonde type convolution generalized by Gould. Furthermore, we also obtain a combinatorial sum involving a vector generalization of the Catalan numbers by an extension of our involution.
The inverse eigenvalue problem of a given graph $G$ is to determine all possible spectra of real symmetric matrices whose off-diagonal entries are governed by the adjacencies in $G$. Barrett et al. introduced the Strong Spectral Property (SSP) and the Strong Multiplicity Property (SMP) in [8]. In that paper it was shown that if a graph has a matrix with the SSP (or the SMP) then a supergraph has a matrix with the same spectrum (or ordered multiplicity list) augmented with simple eigenvalues if necessary, that is, subgraph monotonicity. In this paper we extend this to a form of minor monotonicity, with restrictions on where the new eigenvalues appear. These ideas are applied to solve the inverse eigenvalue problem for all graphs of order five, and to characterize forbidden minors of graphs having at most one multiple eigenvalue.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا