Search

Given a pair of real symmetric matrices A , B ∈ R n × n with nonzero patterns determined by the edges of any pair of chosen graphs on n vertices, we consider an inverse eigenvalue problem for the structured matrix C = [ A B I O ] ∈ R 2 n × 2 n. We conjecture that C can attain any spectrum that is closed under conjugation. We use a structured Jacobian method to prove this conjecture for A and B of orders at most 4 or when the graph of A has a Hamilton path, and prove a weaker version of this conjecture for any pair of graphs with a restriction on the multiplicities of eigenvalues of C. [ABSTRACT FROM AUTHOR]

Schur decompositions and the corresponding Schur forms of a single matrix, a pair of matrices, or a collection of matrices associated with the periodic eigenvalue problem are frequently used and studied. These forms are upper-triangular complex matrices or quasi-upper-triangular real matrices that are equivalent to the original matrices via unitary or, respectively, orthogonal transformations. In general, for theoretical and numerical purposes we often need to reduce, by admissible transformations, a collection of matrices to the Schur form. Unfortunately, such a reduction is not always possible. In this paper we describe all collections of complex (real) matrices that can be reduced to the Schur form by the corresponding unitary (orthogonal) transformations and explain how such a reduction can be done. We prove that this class consists of the collections of matrices associated with pseudoforest graphs. In other words, we describe when the Schur form of a collection of matrices exists and how to find it. [ABSTRACT FROM AUTHOR]

In this paper, we take a modest first step towards a systematic study of chromatic numbers of Cayley graphs on abelian groups. We lose little when we consider these graphs only when they are connected and of finite degree. As in the work of Heuberger and others, in such cases the graph can be represented by an m × r integer matrix, where we call m the dimension and r the rank. Adding or subtracting rows produces a graph homomorphism to a graph with a matrix of smaller dimension, thereby giving an upper bound on the chromatic number of the original graph. In this article we develop the foundations of this method. As a demonstration of its utility, we provide an alternate proof of Payan's theorem, which states that a cubelike graph (i.e., a Cayley graph on the product Z 2 × ⋯ × Z 2 of the integers modulo 2 with itself finitely many times) cannot have chromatic number 3. In a series of follow-up articles using the method of Heuberger matrices, we completely determine the chromatic number in cases with small dimension and rank, as well as prove a generalization of Zhu's theorem on the chromatic number of 6-valent integer distance graphs. [ABSTRACT FROM AUTHOR]

The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U = c 1 A + c 2 D + c 3 I + c 4 J , with c i ∈ R and c 1 ≠ 0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues. [ABSTRACT FROM AUTHOR]

Gain graphs are graphs where the edges are given some orientation and labeled with the elements (called gains) from a group so that the gains are inverted when we reverse the direction of the edges. Generalizing the notion of gain graphs, skew gain graphs have the property that the gain of a reversed edge is the image of edge gain under an anti-involution. In this paper, we deal with the adjacency matrix of skew gain graphs with an involutive automorphism on a field of characteristic zero and their characteristic polynomials. Spectra of some particular skew gain graphs are also discussed. [ABSTRACT FROM AUTHOR]

Multiview clustering is a hot research topic in machine learning and computer vision, and many non-negative matrix factorization (NMF)-based multiview clustering approaches have been proposed. However, most existing NMF-based multiview clustering methods aim to only push the learned latent feature matrices of all views towards a common consensus representation or only consider the consistency among all multiview data, whereas the complementary information between different views is often ignored. In this work, we propose a novel multi-view clustering via consistent and specific nonnegative matrix factorization with graph regularization method (MCCS), where the consistency among all multiview data and view-specific information in each view data are simultaneously considered. Specifically, the NMF problem is first formulated using a shared consistent basis matrix, consistent coefficient matrix, a set of view-specific basis matrices, and view-specific coefficient matrices. Then, manifold regularization is embedded into the objective function to preserve the intrinsic geometrical structure of the original data space. Furthermore, a disagreement term is designed to push these view-specific coefficient matrices further towards a common consensus and to ensure that the multiple views have the same underlying cluster structure. Moreover, the multiplicative update algorithm is employed to optimize the objective function. Extensive experimental results on five multiview benchmark datasets, namely, BBC, BBCSport, 20NGs, Wikipedia, and Handwritten, demonstrate that the proposed MCCS outperforms state-of-the-art methods, achieving improvements of 2.29%, 6.63%, 16.15%, 6.51%, and 2.85%, respectively, over the MVCC method in terms of NMI. [ABSTRACT FROM AUTHOR]

For a connected graph G on n vertices, recall that the reciprocal distance signless Laplacian matrix of G is defined to be R Q (G) = R T (G) + R D (G) , where R D (G) is the reciprocal distance matrix, R T (G) = d i a g (R T 1 , R T 2 , ⋯ , R T n) and R T i is the reciprocal distance degree of vertex v i . In 2022, generalized reciprocal distance matrix, which is defined by R D α (G) = α R T (G) + (1 − α) R D (G) , α ∈ [ 0 , 1 ] , was introduced. In this paper, we give some bounds on the spectral radius of R D α (G) and characterize its extremal graph. In addition, we also give the generalized reciprocal distance spectral radius of line graph L (G) . [ABSTRACT FROM AUTHOR]

The line sum optimization problem asks for a (0 , 1) -matrix minimizing the sum of given functions evaluated at its row and column sums. We show that the uniform problem, with identical row functions and identical column functions, and the monotone problem, over matrices with nonincreasing row and column sums, are polynomial time solvable. [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n with m edges. Denote by D (G) the diagonal matrix of its vertex degrees and by A (G) its adjacency matrix. Then the signless Laplacian matrix of G is Q (G) = D (G) + A (G). Let q 1 ≥ q 2 ≥ ⋯ ≥ q n be the signless Laplacian eigenvalues of graph G and also let ν = ν (G) (1 ≤ ν ≤ n) be the largest positive integer such that q ν ≥ 2 m / n . Denote by G ¯ the complement graph of graph G. If G ≆ K n , K ¯ n , K n − 1 ∪ K 1 , K 1 , n − 1 , K n − e , K 2 ∪ (n − 2) K 1 , then we prove that q 2 (G) + q 2 (G ¯) ≥ n − 1. Moreover, if G ≆ K 1 , n − 1 , K n − 1 ∪ K 1 , K n − e , K 2 ∪ (n − 2) K 1 , then ν + ν ¯ ≥ 3. [ABSTRACT FROM AUTHOR]

The aim of this note is to provide an interpretation of two families of quasi anti-tridiagonal matrices in terms of graph theory. Understanding this junction allows us to recover a plethora of recent results on spectra, powers, inverse problems, and determinant, among others, of such matrices. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The spectral radius ρ (G) of a graph G is the largest eigenvalue of its adjacency matrix A (G). In this paper, we first give a sharp lower bound of the spectral radius of a graph G in terms of the degree and the average 2-degree which generalizes a result of Das and Kumar (2003), and then as an application, a sharp upper bound of the energy of G is given which generalizes a result of Liu et al. (2007). [ABSTRACT FROM AUTHOR]

A matrix A is said to be an integer matrix if all its entries are integers. In this article, we characterize the nonsingular integer matrices with integer eigenvalues in an expressible form of their corresponding inverse matrices. It is proved that a nonsingular integer matrix A has integer eigenvalues if and only if A − 1 can be written as the sum of n rank-one matrices that meet certain requirements. A method for constructing integer matrices with integer eigenvalues using the Hadamard product is also provided. Let S represent an n -tuple of nonnegative integers. If there is an n × n integer matrix A whose spectrum (the collection of eigenvalues) is S , we say that S is realisable by an integer matrix. In Fallat et al. (2005) [7] , the authors posed a conjecture that " there is no simple graph on n ≥ 2 vertices whose Laplacian spectrum is given by (0 , 1 , ... , n − 1)." We provide a characterization of threshold graphs using the spectra of quotient matrices of its G -join graphs. As a consequence, we prove that given any n − 1 positive integers λ 2 , ... , λ n such that λ 2 ≤ ⋯ ≤ λ n , the n -tuple (0 , λ 2 , ... , λ n) is realizable by the Laplacian matrix of a multidigraph. In particular, we show that (0 , 1 , ... , n − 1) can be realizable by the Laplacian matrix of a multidigraph. [ABSTRACT FROM AUTHOR]

Gain graphs are graphs where the edges are given some orientation and labeled with the elements (called gains) from a group so that gains are inverted when we reverse the direction of the edges. Generalizing the notion of gain graphs, skew gain graphs have the property that the gain of a reversed edge is the image of edge gain under an anti-involution. In this paper, we study two different types, Laplacian and g-Laplacian matrices for a skew gain graph where the skew gains are taken from the multiplicative group Fx of a field F of characteristic zero. Defining incidence matrix, we also prove the matrix tree theorem for skew gain graphs in the case of the g-Laplacian matrix. [ABSTRACT FROM AUTHOR]

It is well-known that the space of derivations of n-dimensional evolution algebras with non-singular matrices is zero. On the other hand, the space of derivations of evolution algebras with matrices of rank n−1 have also been completely described in the literature. In this work, we provide a complete description of the space of derivations of evolution algebras associated to graphs, depending on the twin partition of the graph. For graphs without twin classes with at least three elements, we prove that the space of derivations of the associated evolution algebra is zero. Moreover, we describe the spaces of derivations for evolution algebras associated to the remaining families of finite graphs. It is worth pointing out that our analysis includes examples of finite dimensional evolution algebras with matrices of any rank. [ABSTRACT FROM AUTHOR]

Let G be a graph on n vertices and λ 1 ≥ λ 2 ≥ ... ≥ λ n its eigenvalues. The Estrada index of G is defined as E E (G) = ∑ i = 1 n e λ i . In this work, we use an increasing sequence converging to the λ 1 to obtain an increasing sequence of lower bounds for E E (G). In addition, we generalize this succession for the Estrada index of an arbitrary symmetric nonnegative matrix. [ABSTRACT FROM AUTHOR]

Let M be a partitioned matrix and B be its equitable quotient matrix. In this paper, we prove the inclusion of their spectra σ (B) ⊆ σ (M) , and the equality of their spectral radii ρ (B) = ρ (M) if M is nonnegative. Moreover, σ (M) is shown to be completely determined by σ (B) if M is from a class of special matrices. Then we apply these results to obtain the spectra of some well-known matrices associated with graphs or digraphs, and then determine the extremal values of different spectral radii associated with connected graphs or strongly connected digraphs with given vertex connectivity. [ABSTRACT FROM AUTHOR]

The discrete Mumford–Shah formalism has been introduced for the image denoising problem, allowing to capture both smooth behavior inside an object and sharp transitions on the boundary. In this letter, we propose first to extend this formalism to graphs and to the problem of mixing matrix estimation. New algorithmic schemes with convergence guarantees relying on proximal alternating minimization strategies are derived, and their efficiency (good estimation and robustness to initialization) is evaluated on simulated data, in the context of vote transfer matrix estimation. [ABSTRACT FROM AUTHOR]

We are interested in the geometric multiplicity of an identified eigenvalue of a matrix A over a general field with a given graph G for its off-diagonal entries. By the classification of a vertex (edge) of G, we refer to the change in the geometric multiplicity of when this vertex (edge) is removed from G to leave a principal submatrix (modification) of A. Such classification in the case of Hermitian matrices and trees has been strategic in the problem of determining the possible lists of multiplicities for the eigenvalues among matrices with the given graph. Here, our view of, and qualification of, the classification in the general setting provides a tool that makes some past arguments more transparent and provides new insight in both the classical and general setting. Some applications are given to general downer mechanisms for the recognition of Parter vertices and to the stability of geometric multiplicity under perturbation of a diagonal entry. [ABSTRACT FROM AUTHOR]

For any prime p let Cp(G) be the p-ary code spanned by the rows of the incidence matrix G of a graph Γ. Let Γ be the incidence graph of a flag-transitive symmetric design D. We show that any flag-transitive automorphism group of D can be used as a PD-set for full error correction for the linear code Cp(G) (with any information set). It follows that such codes derived from flag-transitive symmetric designs can be decoded using permutation decoding. In that way to each flag-transitive symmetric (v,k,λ) design we associate a linear code of length vk that is permutation decodable. PD-sets obtained in the described way are usually of large cardinality. By studying codes arising from some flag-transitive symmetric designs we show that smaller PD-sets can be found for specific information sets. [ABSTRACT FROM AUTHOR]

In this paper, we give some new sharp upper and lower bounds for the spectral radius of a nonnegative irreducible matrix. Using these bounds, we obtain some new and improved bounds for the signless Laplacian spectral radius of a graph or a digraph. [ABSTRACT FROM AUTHOR]

Recently, it has been noticed that if the graph of an n-by-n complex matrix is a tree, then normality of the matrix is equivalent to three conditions, associated with the edges of the graph, that are much simpler than checking the standard definition of normality. Here, we characterize the precise class of graphs (much more general than trees), for which the three conditions are equivalent to normality, under a slight (and necessary) regularity condition. The graphs are those that are both triangle and 4-cycle free. For triangle-free graphs, normality implies absolute symmetry, under the same regularity condition. The results permit strong applications to real matrices, and to the notions of “principal normality”, and “essentially Hermitian”. [ABSTRACT FROM AUTHOR]

For given distinct numbers λ 1 ± μ 1 i , λ 2 ± μ 2 i , … , λ k ± μ k i ∈ C ∖ R and γ 1 , γ 2 , … , γ l ∈ R , and a given graph G with a matching of size at least k , we will show that there is a real matrix whose eigenvalues are the given numbers and its graph is G . In particular, this implies that any real matrix with distinct eigenvalues is similar to a real, irreducible, tridiagonal matrix. [ABSTRACT FROM AUTHOR]

Many types of pairwise interactions take the form of a fixed set of nodes with edges that appear and disappear over time. In the case of discrete-time evolution, the resulting evolving network may be represented by a time-ordered sequence of adjacency matrices. We consider here the issue of representing the system as a single, higher-dimensional block matrix, built from the individual time slices. We focus on the task of computing network centrality measures. From a modeling perspective, we show that there is a suitable block formulation that allows us to recover dynamic centrality measures respecting time's arrow. From a computational perspective, we show that the new block formulation leads to the design of more effective numerical algorithms. In particular, we describe matrix-vector product based algorithms that exploit sparsity. Results are given on realistic data sets. [ABSTRACT FROM AUTHOR]

If T is a labelled tree, a matrix A is totally positive relative to T , principal submatrices of A associated with deletion of pendent vertices of T are P-matrices, and A has positive determinant, then the smallest absolute eigenvalue of A is positive with multiplicity 1 and its eigenvector is signed according to T . This conclusion has been incorrectly conjectured under weaker hypotheses. [ABSTRACT FROM AUTHOR]

The distance matrix of a graph G is the matrix containing the pairwise distances between vertices. The distance eigenvalues of G are the eigenvalues of its distance matrix and they form the distance spectrum of G . We determine the distance spectra of double odd graphs and Doob graphs, completing the determination of distance spectra of distance regular graphs having exactly one positive distance eigenvalue. We characterize strongly regular graphs having more positive than negative distance eigenvalues. We give examples of graphs with few distinct distance eigenvalues but lacking regularity properties. We also determine the determinant and inertia of the distance matrices of lollipop and barbell graphs. [ABSTRACT FROM AUTHOR]

By resorting to a new matrix product, called semi-tensor product of matrices, this paper investigates the minimum stable set and core of graph, and also presents a number of results and algorithms. By defining a characteristic logical vector and using matrix expressions of logical functions, a new algebraic representation is derived for the externally stable set. Then, based on the algebraic representation, an algorithm is established to find all the externally stable sets. According to this algorithm, a new necessary and sufficient condition is obtained to determine whether a given vertex subset is an absolutely minimum externally stable set or not. Meanwhile, a new algorithm is also obtained to find all the absolutely minimum externally stable sets. Finally, the graph core, which is simultaneously externally stable set and internally stable set, is investigated. Here the internally stable set requires that internal nodes of this set are all disconnected with each other. Using semi-tensor product, some necessary and sufficient conditions are presented, and then an algorithm is established to find all the graph cores. The study of illustrative examples shows that the results/algorithms presented in this paper are effective. [ABSTRACT FROM AUTHOR]

For-matrices in general, and for-matrices with a constant numberof 1s in each row and column, we determine the possible sets of traces of such matrices as its rows are permuted. Except for some special matrices, which are identified, the set of such traces is a consecutive set of integers from. [ABSTRACT FROM AUTHOR]

A signed graph is a pair ( G , Σ ) , where G = ( V , E ) is a graph (in which parallel edges and loops are permitted) with V = { 1 , … , n } and Σ ⊆ E . The edges in Σ are called odd edges and the other edges of E even. By S ( G , Σ ) we denote the set of all symmetric n × n real matrices A = [ a i , j ] such that if a i , j < 0 , then among the edges connecting i and j , there must be at least one even edge; if a i , j > 0 , then among the edges connecting i and j , there must be at least one odd edge; and if a i , j = 0 , then either there must be at least one odd edge and at least one even edge connecting i and j , or there are no edges connecting i and j . (Here we allow i = j .) For a symmetric real matrix A , the partial inertia of A is the pair ( p , q ) , where p and q are the numbers of positive and negative eigenvalues of A , respectively. If ( G , Σ ) is a signed graph, we define the inertia set of ( G , Σ ) as the set of the partial inertias of all matrices A ∈ S ( G , Σ ) . In this paper, we present formulas that allows us to obtain the minimal elements of the inertia set of ( G , Σ ) in case ( G , Σ ) has a 1-separation using the inertia sets of certain signed graphs associated with the 1-separation. [ABSTRACT FROM AUTHOR]

For a graph G = ( V , E ) with V = { 1 , 2 , … , n } , let S ( G ) be the set of all symmetric real n × n matrices A = [ a i , j ] with a i , j ≠ 0 , i ≠ j if and only if i j ∈ E . The inertia set of a graph G is the set of all possible inertias of matrices in S ( G ) . In this paper we give a formula that expresses the inertia set of a graph with a 2-separation in terms of the inertia sets of subgraphs of G . This formula follows from an extension to arbitrary fields with characteristic not equal to two. [ABSTRACT FROM AUTHOR]

In 1971, Graham and Pollack established a relationship between the number of negative eigenvalues of the distance matrix and the addressing problem in data communication systems. They also proved that the determinant of the distance matrix of a tree is a function of the number of vertices only. Since then several mathematicians were interested in studying the spectral properties of the distance matrix of a connected graph. Computing the distance characteristic polynomial and its coefficients was the first research subject of interest. Thereafter, the eigenvalues attracted much more attention. In the present paper, we report on the results related to the distance matrix of a graph and its spectral properties. [ABSTRACT FROM AUTHOR]

Let G = G1 ∪ G2 be the sum of two simple graphs G1, G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant detA(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples [ABSTRACT FROM AUTHOR]

Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigation into the algorithmic properties of split decomposition. We do so in the context of graph-labelled trees (GLTs), a new combinatorial object designed to simplify its consideration. GLTs are used to derive an incremental characterization of split decomposition, with a simple combinatorial description, and to explore its properties with respect to Lexicographic Breadth-First Search (LBFS). Applying the incremental characterization to an LBFS ordering results in a split decomposition algorithm that runs in time O( n+ m) α( n+ m), where α is the inverse Ackermann function, whose value is smaller than 4 for any practical graph. Compared to Dahlhaus' linear time split decomposition algorithm (Dahlhaus in J. Algorithms 36(2):205-240, ), which does not rely on an incremental construction, our algorithm is just as fast in all but the asymptotic sense and full implementation details are given in this paper. Also, our algorithm extends to circle graph recognition, whereas no such extension is known for Dahlhaus' algorithm. The companion paper (Gioan et al. in , ) uses our algorithm to derive the first sub-quadratic circle graph recognition algorithm. [ABSTRACT FROM AUTHOR]

Abstract: We introduce a new type of graph called a Fibonomial graph, denoted . Entries of the adjacency matrix of depend on the well-known Fibonomial coefficients modulo 2. We investigate the connectivity properties, eigenvalues, and energy of . We lastly obtain the sum of the Laplacian eigenvalues of . [Copyright &y& Elsevier]

Abstract: Let be the set of matrices over a field . Consider a graph with as the vertex set such that two vertices are adjacent if . We study graph properties of G when is a finite field. In particular, G is a regular connected graph with diameter equal to ; it is always Hamiltonian. Furthermore, we determine the independence number, chromatic number and clique number of G. These results are used to characterize the graph endomorphisms of G, which extends Hua's fundamental theorem of geometry on . [Copyright &y& Elsevier]

Abstract: In this paper, we introduce the notion of reproducing kernel Hilbert spaces for graphs and the Gram matrices associated with them. Our aim is to investigate the Gram matrices of reproducing kernel Hilbert spaces. We provide several bounds on the entries of the Gram matrices of reproducing kernel Hilbert spaces and characterize the graphs which attain our bounds. [Copyright &y& Elsevier]

Abstract: In this paper a relation between graph distance matrices of the star graph and its generalizations and Euclidean distance matrices is considered. It is proven that distance matrices of certain families of graphs are circum Euclidean. Their spectrum and generating points are given in a closed form. [Copyright &y& Elsevier]

In 1966, Gallai conjectured that for any simple, connected graph G having n vertices, there is a path-decomposition of G having at most [ABSTRACT FROM AUTHOR]

The hulls of codes from the row span over $${\mathbb{F}_p}$$ , for any prime p, of incidence matrices of connected k-regular graphs are examined, and the dimension of the hull is given in terms of the dimension of the row span of A + kI over $${\mathbb{F}_p}$$ , where A is an adjacency matrix for the graph. If p = 2, for most classes of connected regular graphs with some further form of symmetry, it was shown by Dankelmann et al. (Des. Codes Cryptogr. ) that the hull is either {0} or has minimum weight at least 2 k−2. Here we show that if the graph is strongly regular with parameter set ( n, k, λ, μ), then, unless k is even and μ is odd, the binary hull is non-trivial, of minimum weight generally greater than 2 k − 2, and we construct words of low weight in the hull; if k is even and μ is odd, we show that the binary hull is zero. Further, if a graph is the line graph of a k-regular graph, k ≥ 3, that has an ℓ-cycle for some ℓ ≥ 3, the binary hull is shown to be non-trivial with minimum weight at most 2 ℓ( k−2). Properties of the p-ary hulls are also established. [ABSTRACT FROM AUTHOR]

Abstract: We give upper and lower bounds for the spectral radius of a nonnegative matrix using its row sums and characterize the equality cases if the matrix is irreducible. Then we apply these bounds to various matrices associated with a graph, including the adjacency matrix, the signless Laplacian matrix, the distance matrix, the distance signless Laplacian matrix, and the reciprocal distance matrix. Some known results in the literature are generalized and improved. [Copyright &y& Elsevier]

This paper considers *-graphs in which all vertices have degree 4 or 6, and studies the question of calculating the genus of orientable 2-surfaces into which such graphs may be embedded. A *-graph is a graph endowed with a formal adjacency structure on the half-edges around each vertex, and an embedding of a *-graph is an embedding under which the formal adjacency relation on half-edges corresponds to the adjacency relation induced by the embedding. *-graphs are a natural generalization of four-valent framed graphs, which are four-valent graphs with an opposite half-edge structure. In [Embeddings of four-valent framed graphs into 2-surfaces, Dokl. Akad. Nauk 424(3) (2009) 308-310], the question of whether a four-valent framed graph admits a ℤ2-homologically trivial embedding into a given surface was shown to be equivalent to a problem on matrices. We show that a similar result holds for *-graphs in which all vertices have degree 4 or 6. This gives an algorithm in quadratic time to determine whether a *-graph admits an embedding into the plane. [ABSTRACT FROM AUTHOR]

Approximations of matrix-valued functions of the form WT f(A)W, where A ∈ Rm×m is symmetric, W ∈ Rm×k, with m large and k ≪ m, has orthonormal columns, and f is a function, can be computed by applying a few steps of the symmetric block Lanczos method to A with initial block-vector W ∈ Rm×k. Golub and Meurant have shown that the approximants obtained in this manner may be considered block Gauss quadrature rules associated with a matrix-valued measure. This paper generalizes anti-Gauss quadrature rules, introduced by Laurie for real-valued measures, to matrix-valued measures, and shows that under suitable conditions pairs of block Gauss and block anti-Gauss rules provide upper and lower bounds for the entries of the desired matrix-valued function. Extensions to matrix-valued functions of the form WT f(A)V, where A ∈ Rm×m may be nonsymmetric, and the matrices V,W ∈ Rm×k satisfy VTW = Ik are also discussed. Approximations of the latter functions are computed by applying a few steps of the nonsymmetric block Lanczos method to A with initial block-vectors V and W. We describe applications to the evaluation of functions of a symmetric or nonsymmetric adjacency matrix for a network. Numerical examples illustrate that a combination of block Gauss and anti-Gauss quadrature rules typically provides upper and lower bounds for such problems. We introduce some new quantities that describe properties of nodes in directed or undirected networks, and demonstrate how these and other quantities can be computed inexpensively with the quadrature rules of the present paper. [ABSTRACT FROM AUTHOR]

Abstract: A result of Duarte [Linear Algebra Appl. 113 (1989) 173–182] asserts that for real , with and each tree T on n vertices there exists an n × n, real symmetric matrix A whose graph is T such that A has eigenvalues and the principal submatrix obtained from A by deleting its last row and column has eigenvalues . This result is extended to connected graphs through the use of the implicit function theorem. [Copyright &y& Elsevier]

Abstract: Let G be a simple connected graph of order n with degree sequence in non-increasing order. The spectral radius of G is the largest eigenvalue of its adjacency matrix. For each positive integer at most n, we give a sharp upper bound for by a function of which generalizes a series of previous results. [Copyright &y& Elsevier]

We classify the trees for which there is a nonsingular matrix where each vertex is a P-vertex. In particular, we show that such trees have an even number of vertices. Both results provide answers to questions proposed by Kim and Shader. In the end, related classifications on nonsingular trees with the size of a P-set bounded are addressed. [ABSTRACT FROM AUTHOR]

We look for the maximum order m( r) of the adjacency matrix A of a graph G with a fixed rank r, provided A has no repeated rows or all-zero row. Akbari, Cameron and Khosrovshahi conjecture that m( r) = 2 − 2 if r is even, and m( r) = 5 · 2 − 2 if r is odd. We prove the conjecture and characterize G in the case that G contains an induced subgraph $${\frac{r}{2}K_2}$$ or $${\frac{r-3}{2}K_2+K_3}$$. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we introduce a new parameter for a graph called the minimum universal rank. This parameter is similar to the minimum rank of a graph. For a graph G the minimum universal rank of G is the minimum rank over all matrices of the form where A is the adjacency matrix of G, J is the all ones matrix and D is the matrix with the degrees of the vertices in the main diagonal, and are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of A. The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. [Copyright &y& Elsevier]

Abstract: Using the semi-tensor product of matrices, this paper investigates the maximum (weight) stable set and vertex coloring problems of graphs with application to the group consensus of multi-agent systems, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for the internally stable set problem, based on which a new algorithm to find all the internally stable sets is established for any graph. Secondly, the maximum (weight) stable set problem is considered, and a necessary and sufficient condition is presented, by which an algorithm to find all the maximum (weight) stable sets is obtained. Thirdly, the vertex coloring problem is studied by using the semi-tensor product method, and two necessary and sufficient conditions are proposed for the colorability, based on which a new algorithm to find all the -coloring schemes and minimum coloring partitions is put forward. Finally, the obtained results are applied to multi-agent systems, and a new protocol design procedure is presented for the group consensus problem. The study of illustrative examples shows that the results/algorithms presented in this paper are very effective. [Copyright &y& Elsevier]

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut edges. [ABSTRACT FROM AUTHOR]

Abstract: The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: what is the structure of a connected graph G with rank 5? or equivalently, what is the structure of a connected n-vertex graph G whose adjacency matrix has nullity ? In this paper, we completely characterize connected graphs G whose adjacency matrix has rank 5. [Copyright &y& Elsevier]