Search

Minimal codewords have applications in decoding linear codes and in cryptography. We study the number of minimal codewords in binary linear codes that arise by appending a unit matrix to the adjacency matrix of a graph., Comment: 11 pages

The characteristic polynomial of the adjacency matrix of the subdivision graph G is related to the characteristic polynomials of the adjacency matrices of g and its line graph.

Perfect state transfer in graphs is a concept arising from quantum physics and quantum computing. Given a graph G with adjacency matrix A G , the transition matrix of G with respect to A G is defined as H A G ( t ) = exp ( − i t A G ) , t ∈ R , i = − 1 . We say that perfect state transfer from vertex u to vertex v occurs in G at time τ if u ≠ v and the modulus of the ( u , v ) -entry of H A G ( τ ) is equal to 1. If the moduli of all diagonal entries of H A G ( τ ) are equal to 1 for some τ , then G is called periodic with period τ . In this paper we give a few sufficient conditions for NEPS of complete graphs to be periodic or exhibit perfect state transfer.

We find a basis for the null space of the adjacency matrix of unicyclic graphs. Based on the support of such a basis, we determine a null decomposition of these graphs. As an application, we obtain closed formulas for the independence and matching numbers of unicyclic graphs that solely rely on the support of the graph.

The net Laplacian matrix of a signed graph G is defined to be N G = D G ± − A G , where D G ± and A G are the diagonal matrix of net-degrees and the adjacency matrix of G , respectively. For a binary vector b , the pair ( N G , b ) is controllable if N G has no eigenvector orthogonal to b ; we also say that G is net Laplacian controllable for b . In this study we consider the net Laplacian controllability of joins of signed graphs. In particular, we establish all controllable pairs ( N G , b ) , where G is a signed threshold graph determined by a ( 0 , 1 , − 1 ) -generating sequence. This result contains all controllable pairs ( L G , b ) , where L G is the Laplacian matrix of a graph G .

The graph energy, as a graph invariant, contains very important structural information about the graph, its subgraphs, and ingredient segments. Estrada and Benzi (2017) have shown that the graph energy can be extracted from the weighted sum of the traces of the even powers of its adjacency matrix. Based on this kind of representation, they have reported newer and more precise bounds of the energy as the sum of fragments’ contributions such as C n (cycles of length n), P n (path graph), S n (star graph), D n (diamond graph), F (a subgraph containing a square with a pendant vertex), and H (a subgraph containing two triangles with a shared vertex). In this paper, inspired by the work of Estrada and Benzi, we first introduce a general formula for calculating the contribution of subgraphs to the total energy of the graph. We also compute the boundaries of the contributions of the above subgraphs and some of the subgraphs that appear for the first time in the higher traces of the adjacency matrix of the graph. Further, we calculate the upper bound of the graph energy for cyclic and fullerene graphs with higher accuracy.

A Hamiltonian graph G is said to be hyper-Hamiltonian when G − v is Hamiltonian for any vertex v of G . In this paper, sufficient conditions for a graph to be hyper-Hamiltonian based on different parameters, such as degree and number of edges, are presented. Furthermore, other sufficient conditions for hyper-Hamiltonicity are obtained from spectral parameters, such as the spectral radii of the adjacency matrix, the signless Laplacian matrix and the distance matrix. Results on hyper-Hamiltonicity of a threshold graph through the eigenvalues of its Laplacian matrix are also presented.

Let G be a simple graph with n ( G ) vertices and e ( G ) edges. The elementary cyclic number c ( G ) of G is defined as c ( G ) = e ( G ) − n ( G ) + ω ( G ) , where ω ( G ) is the number of connected components of G . The nullity of G , denoted by η ( G ) , is the multiplicity of the eigenvalue zero of the adjacency matrix of G . A graph is leaf-free if it has no pendent vertices. In Ma et al. (2016) proved that if G is leaf-free and each component of G contains at least two vertices, then η ( G ) ≤ 2 c ( G ) , the equality is attained if and only if G is the union of disjoint cycles, where each cycle has length a multiple of 4. In this paper, we completely characterize all leaf-free graphs with nullity one less than the above upper bound, i.e., η ( G ) = 2 c ( G ) − 1 .

We give an O ( n ) time and space algorithm for constructing a diagonal matrix congruent to A + x I , where A is the adjacency matrix of a cograph and x ∈ R . Applications include determining the number of eigenvalues of a cograph’s adjacency matrix that lie in any interval, obtaining a formula for the inertia of a cograph, and exhibiting infinitely many pairs of equienergetic cographs with integer energy.

We report our experiments in identifying large bipartite subgraphs of simple connected graphs which are based on the sign pattern of eigenvectors belonging to the extremal eigenvalues of different graph matrices: adjacency, signless Laplacian, Laplacian, and normalized Laplacian matrix. We compare the performance of these methods to a local switching algorithm based on the Erdos bound that each graph contains a bipartite subgraph with at least half of its edges. Experiments with one scale-free and three random graph models, which cover a wide range of real-world networks, show that the methods based on the eigenvectors of the normalized Laplacian and the adjacency matrix yield slightly better, but comparable results to the local switching algorithm. We also formulate two edge bipartivity indices based on the former eigenvectors, and observe that the method of iterative removal of edges with maximum bipartivity index until one obtains a bipartite subgraph, yields comparable results to the local switching algorithm, and significantly better results than an analogous method that employs the edge bipartivity index of Estrada and Gomez-Gardenes., 20 pages, 8 figures

Let G be a simple connected graph with n vertices and m edges. Let W ( G ) = ( G , w ) be the weighted graph corresponding to G . Let λ 1 , λ 2 , … , λ n be the eigenvalues of the adjacency matrix A ( W ( G ) ) of the weighted graph W ( G ) . The energy E ( W ( G ) ) of a weighted graph W ( G ) is defined as the sum of absolute value of the eigenvalues of W ( G ) . In this paper, we obtain upper bounds for the energy E ( W ( G ) ) , in terms of the sum of the squares of weights of the edges, the maximum weight, the maximum degree d 1 , the second maximum degree d 2 and the vertex covering number τ of the underlying graph G . As applications to these upper bounds we obtain some upper bounds for the energy (adjacency energy), the extended graph energy, the Randic energy and the signed energy of the connected graph G . We also obtain some new families of weighted graphs where the energy increases with increase in weights of the edges.

The pineapple graph K p q is obtained by appending q pendant edges to a vertex of a complete graph K p ( p ≥ 3 , q ≥ 1 ). We prove that among connected graphs, the pineapple graph is determined by its adjacency spectrum. Moreover, we determine all disconnected graphs which are cospectral with a pineapple graph. Thus we find for which values of p and q the pineapple graph K p q is determined by its adjacency spectrum. The main tool is a recent classification of all graphs with all but three eigenvalues equal to 0 or − 1 by the third author.

A graph is called a chain graph if it is bipartite and the neighbourhoods of the vertices in each colour class form a chain with respect to inclusion. A threshold graph can be obtained from a chain graph by making adjacent all pairs of vertices in one colour class. Given a graph G , let λ be an eigenvalue (of the adjacency matrix) of G with multiplicity k ≥ 1 . A vertex v of G is a downer, or neutral, or Parter depending whether the multiplicity of λ in G − v is k − 1 , or k , or k + 1 , respectively. We consider vertex types in the above sense in threshold and chain graphs. In particular, we show that chain graphs can have neutral vertices, disproving a conjecture by Alazemi et al.

A nonsingular graph with a singular deck, or NSSD, is a graph with weighted edges and no loops whose adjacency matrix is nonsingular and whose vertex-deleted subgraphs have singular adjacency matrices. When all the weights of the edges of a NSSD are equal to one, we obtain a molecular NSSD, which is an ipso omni-insulator molecular graph. We present necessary and sufficient conditions for a NSSD G to remain a NSSD after increasing the weight of one of its edges by w ∈ R ∖ { 0 } ; this weight change may result in the addition or removal of that edge to or from G . Using this result, we construct molecular NSSDs of a fixed even order. This is accomplished by systematically introducing edges to, or removing edges from, a nonsingular tree.

Eigenvalues of graph-theoretical matrices often reflect structure properties of networks (graphs) meaningfully. In this paper, we explore inequalities for graph distance measures which are based on topological indices. Some of these indices are based on eigenvalues of graph-theoretical matrices. We here consider the adjacency matrix, the Laplacian matrix and signless Laplacian matrix. Besides proving the inequalities, we discuss the usefulness of these measures and state some conjectures.

Let G be a graph of order n . The energy E ( G ) of a simple graph G is the sum of absolute values of the eigenvalues of its adjacency matrix. The Laplacian energy, the signless Laplacian energy and the distance energy of graph G are denoted by L E ( G ) , S L E ( G ) and D E ( G ) , respectively. In this paper we introduce a distance Laplacian energy D L E and distance signless Laplacian energy D S L E of a connected graph. We present Nordhaus–Gaddum type bounds on Laplacian energy L E ( G ) and signless Laplacian energy S L E ( G ) in terms of order n of graph G and characterize graphs for which these bounds are best possible. The complete graph and the star give the smallest distance signless Laplacian energy D S L E among all the graphs and trees of order n , respectively. We give lower bounds on distance Laplacian energy D L E in terms of n for graphs and trees, and characterize the extremal graphs. Also we obtain some relations between D E , D S L E and D L E of graph G . Moreover, we give several open problems in this paper.

Let G σ be an oriented graph with skew adjacency matrix S ( G σ ) . The skew energy E S ( G σ ) of G σ is the sum of the norms of all eigenvalues of S ( G σ ) and the skew rank s r ( G σ ) of G σ is the rank of S ( G σ ) . In this paper, it is proved that E S ( G σ ) ≥ 2 μ ( G ) for an arbitrary connected oriented graph G σ of order n , where μ ( G ) is the matching number of G , and the equality holds if and only if G is a complete bipartite graph K n 2 , n 2 with partition ( X , Y ) of equal size and σ is switching-equivalent to the elementary orientation of G which assigns all edges the same direction from vertices of X to vertices of Y . As an application, we prove that E S ( G σ ) ≥ s r ( G σ ) for an oriented graph G σ and the equality holds if and only if G is the disjoint union of some copies of K 2 and some isolated vertices.

The minimum k -way discrepancy md k ( C ) of a rectangular matrix C of nonnegative entries is the minimum of the maxima of the within- and between-cluster discrepancies that can be obtained by simultaneous k -clusterings (proper partitions) of its rows and columns. In Theorem?2, irrespective of the size of C , we give the following estimate for the k th largest nontrivial singular value of the normalized matrix: s k ? 9 md k ( C ) ( k + 2 - 9 k ln md k ( C ) ) , provided 0 < md k ( C ) < 1 and k < rank ( C ) . This statement is a certain converse of Theorem 7 of Bolla (2014), and the proof uses some lemmas and ideas of Butler (2006), where the k = 1 case is treated. The result naturally extends to the singular values of the normalized adjacency matrix of a weighted undirected or directed graph.

The n -vertex graph G ( = ? ( G ) ) with a non-singular real symmetric adjacency matrix G , having a zero diagonal and singular ( n - 1 ) × ( n - 1 ) principal submatrices is termed a NSSD, a Non-Singular graph with a Singular Deck. NSSDs arose in the study of the polynomial reconstruction problem and were later found to characterise non-singular molecular graphs that are distinct omni-conductors and ipso omni-insulators. Since both matrices G and G - 1 represent NSSDs ? ( G ) and ? ( G - 1 ) , the value of the nullity of a one-, two- and three-vertex deleted subgraph of G is shown to be determined by the corresponding subgraph in ? ( G - 1 ) . Constructions of infinite subfamilies of non-NSSDs are presented. NSSDs with all two-vertex deleted subgraphs having a common value of the nullity are referred to as G -nutful graphs. We show that their minimum vertex degree is at least 4.

Let G be a simple connected graph with n nodes and let f"@a"""k(A) be a communicability function of the adjacency matrix A, which is expressible by the following Taylor series expansion: @?"k"="0^[email protected]"kA^k. We prove here that if f"@a"""k(A) is positive semidefinite then the function @h"p","q=(f"@a"""k(A)"p"p+f"@a"""k(A)"q"q-2f"@a"""k(A)"p"q)^1^2 is a Euclidean distance between the corresponding nodes of the graph. Then, we prove that if f"@a"""k(A) is positive definite, the communicability distance induces an embedding of the graph into a hyperdimensional sphere (hypersphere) such as the distances between the nodes are given by @h"p","q. In addition we give analytic results for the communicability distances for the nodes in paths, cycles, stars and complete graphs, and we find functions of the adjacency matrix for which the main results obtained here are applicable. Finally, we study the ratio of the surface area to volume of the hyperspheres in which a few real-world networks are embedded. We give clear indications about the usefulness of this embedding in analyzing the efficacy of geometrical embeddings of real-world networks like brain networks, airport transportation networks and the Internet.

In this paper we obtain several characterizations of the adjacency matrix of a probe interval graph. In course of this study we describe an easy method of obtaining interval representation of an interval bigraph from its adjacency matrix. Finally, we note that if we add a loop at every probe vertex of a probe interval graph, then the Ferrers dimension of the corresponding symmetric bipartite graph is at most 3.

The importance of the Pfaffian property of a graph stems from the fact that if the graph is Pfaffian, then the number of its perfect matchings can be computed in polynomial time. A graph G is Pfaffian if there exists an orientation of G , denoted by G ? , such that the determinant of the skew adjacency matrix of G ? equals the square of the number of perfect matchings of G . An undirected graph G = ( V , E ) with n vertices is a circulant graph, denoted by C n ( a 1 , a 2 , ? , a m ) , if there exists a labeling of the vertices of G , v 1 , v 2 , ? , v n , and m integers, a 1 , a 2 , ? , a m , such that the edge set E = { v i v j : i - j ? ? a k ( mod n ) for? 1 ? k ? m } . In this paper, the Pfaffian property of circulant graphs is completely characterized, that is, a simple connected circulant graph C n ( a 1 , a 2 , ? , a m ) of even order is Pfaffian if and only if m = 1 or, m = 2 and a 1 + a 2 is odd.

Let G be a graph with adjacency matrix A, and let H(t)=exp(itA). For an eigenvalue @m of A with multiplicity k, a star set for @m in G is a vertex set X of G such that |X|=k and the induced subgraph G-X does not have @m as an eigenvalue. G is said to have perfect state transfer from the vertex u to the vertex v if there is a time @t such that |H(@t)"u","v|=1. The unitary operator H(t) has important applications in the transfer of quantum information. In this paper, we give an expression of H(t). For a star set X of graph G, perfect state transfer does not occur between any two vertices in X. We also give some results for the existence of perfect state transfer in a graph.

We introduce a new type of graph called a Fibonomial graph, denoted G"n. Entries of the adjacency matrix of G"n depend on the well-known Fibonomial coefficients modulo 2. We investigate the connectivity properties, eigenvalues, and energy of G"n. We lastly obtain the sum of the Laplacian eigenvalues of G"n.

Let G = ( V , E ) be a simple graph with vertex set V and edge set E . The rank of G , written as r , is defined to be the rank of its adjacency matrix. Let c denote e - v + ? , where e = | E | , v = | V | and ? means the number of connected components of G , and let m , α , ? ' respectively be the matching number, the independence number, and the chromatic index of G . In this paper, it is proved that ? r - c 2 ? ? m ? ? r + 2 c 2 ? , ? 2 e r + 2 c ? ? ? ' , and v - ? r 2 ? - c ? α ? v - ? r 2 ? . Examples are given to show that all the bounds can be attained.

Let G be a simple connected graph on n vertices and λ 1 , λ 2 , ? , λ n be the eigenvalues of the adjacency matrix of G . The Estrada index of G is defined as E E ( G ) = ? i = 1 n e λ i . Let T n be the class of tricyclic graphs G on n vertices. In this paper, the graphs in T n with the maximal Estrada index is characterized.

We present some applications of a new matrix approach for studying the properties of the lift of a voltage digraph, which has arcs weighted by the elements of a group. As a main result, when the involved group is Abelian, we completely determine the spectrum of . As some examples of our technique, we study some basic properties of the Alegre digraph, and completely characterize the spectrum of a new family of digraphs, which contains the generalized Petersen graphs, and the Hoffman-Singleton graph The research of the first two authors have been partially supported by the Agency for Management of University and Research Grants of Catalonia (AGAUR) under project 2017SGR1087. The fifth author acknowledges support from the research grants APVV 0136/12, APVV-15-0220, VEGA 1/0026/16, and VEGA 1/0142/17. The first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.

The Estrada index of a graph G is defined as EE(G)[email protected]?"i"="1^ne^@l^"^i, where @l"1,@l"2,...,@l"n are the eigenvalues of the adjacency matrix of G. It can be used as an efficient measuring tool in a variety of fields. An edge grafting operation on a graph moves a pendent edge between two pendent paths. In this paper, we give an edge grafting theorem on the Estrada index of graphs. We also give some applications of this theorem.

The distance spectral radius @r(G) of a graph G is the largest eigenvalue of the distance matrix D(G). Recently, many researches proposed the use of @r(G) as a molecular structure descriptor of alkanes. In this paper, we introduce general transformations that decrease distance spectral radius and characterize n-vertex trees with given matching number m which minimize the distance spectral radius. The extremal tree A(n,m) is a spur, obtained from the star graph S"n"-"m"+"1 with n-m+1 vertices by attaching a pendent edge to each of certain m-1 non-central vertices of S"n"-"m"+"1. The resulting trees also minimize the spectral radius of adjacency matrix, Hosoya index, Wiener index and graph energy in the same class of trees. In conclusion, we pose a conjecture for the maximal case based on the computer search among trees on n@?24 vertices. In addition, we found the extremal tree that uniquely maximizes the distance spectral radius among n-vertex trees with perfect matching and fixed maximum degree @D.

We unify and generalize several inequalities for the number w"k of walks of length k in graphs, and for the entry sum of matrix powers. First, we present a weighted sandwich theorem for Hermitian matrices which generalizes a matrix theorem by Marcus and Newman and which further generalizes our former unification of inequalities for the number of walks in undirected graphs by Lagarias et al. and by Dress and Gutman. The new inequality uses an arbitrary nonnegative weighting of the indices (vertices) which allows to apply the theorem to index (vertex) subsets (i.e., inequalities considering the number w"k(S,S) of walks of length k that start at a vertex of a given vertex subset S and that end within the same subset). We also deduce a stronger variation of the sandwich theorem for the case of positive-semidefinite Hermitian matrices which generalizes another inequality of Marcus and Newman. Further, we show a similar theorem for nonnegative symmetric matrices which is another unification and generalization of inequalities for walk numbers by Erdos and Simonovits, by Dress and Gutman, and by Ilic and Stevanovic. In the last part, we generalize lower bounds for the spectral radius of adjacency matrices and upper bounds for the energy of graphs.

The energy of a graph is defined as the sum of the absolute values of all eigenvalues of the adjacency matrix of the graph. Zhang and Li [F. Zhang, H. Li, On acyclic conjugated molecules with minimal energies, Discrete Appl. Math. 92 (1999) 71–84] determined the first two smallest-energy trees of a fixed size with a perfect matching and showed that the third minimal energy is between two trees. This paper characterizes trees of a fixed size with a perfect matching with third minimal, fourth minimal and fifth minimal energies for n≥86 and third minimal, fourth minimal energies for 14≤n≤84.

The index of a graph is the largest eigenvalue (or spectral radius) of its adjacency matrix. We consider the problem of ordering graphs by the index in the class of connected graphs with a fixed order n and index belonging to the interval (2,2+5). For any fixed n (provided that n is not too small), we order a significant portion of graphs whose indices are close to the end points of the above interval.

We show that the Hamiltonicity of a regular graph G can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A+I, where A is the adjacency matrix of G, I is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G with girth g(G)⩾5 has a Hamiltonian circuit if and only if the matrix A+I can be permuted on rows such that each column has at most (or exactly) k-1 circular blocks of consecutive ones; and if the graph G is k-regular except for two (k-1)-degree vertices a and b, then there is a Hamiltonian path from a to b if and only if the matrix A+I can be permuted on rows to have at most (or exactly) k-1 linear blocks per column.Then we turn to the problem of determining whether a given matrix can have at most k blocks of consecutive ones per column by some row permutation. For this problem, Booth and Lueker gave a linear algorithm for k=1 [Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 255–265]; Flammini et al. showed its NP-completeness for general k [Algorithmica 16 (1996) 549–568]; and Goldberg et al. proved the same for every fixed k⩾2 [J. Comput. Biol. 2 (1) (1995) 139–152]. In this paper, we strengthen their result by proving that the problem remains NP-complete for every constant k⩾2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row.

Consider the problem of testing for existence of an n-node graph G satisfying some condition P, expressed as a Boolean constraint among the nxn Boolean entries of the adjacency matrix M. This problem reduces to satisfiability of P(M). If P is preserved by isomorphism, P(M) is satisfiable iff P(M)@?SB(M) is satisfiable, where SB(M) is a symmetry-breaking predicate-a predicate satisfied by at least one matrix M in each isomorphism class. P(M)@?SB(M) is more constrained than P(M), so it is solved faster by backtracking than P(M)-especially if SB(M) rules out most matrices in each isomorphism class. This method, proposed by Crawford et al., applies not just to graphs but to testing existence of a combinatorial object satisfying any property that respects isomorphism, as long as the property can be compactly specified as a Boolean constraint on the object's binary representation. We present methods for generating symmetry-breaking predicates for several classes of combinatorial objects: acyclic digraphs, permutations, functions, and arbitrary-arity relations (direct products). We define a uniform optimality measure for symmetry-breaking predicates, and evaluate our constraints according to this measure. Results indicate that these constraints are either optimal or near-optimal for their respective classes of objects.

Large-scale combinatorial scientific computing problems arising in sparse or otherwise structured matrix computation are often expressed using an appropriate graph model, and sometimes the same problem can be given in more than one graph model with similar asymptotic computational complexity. The relative merits of different graph models for the same problem can then be expressed in terms of factors such as generality of the model or ease of computer implementation. We review contemporary graph formulations for large-scale sparse Jacobian matrix determination problem (JMDP) and suggest the pattern graph as a unifying framework for methods that exploit sparsity by matrix compression: row compression, column compression, or a combination of the two. We argue that with the pattern graph, which is structurally close to the underlying matrix, exploitable sparsity and structures in the matrix are unlikely to be lost in ''translation'' from a matrix problem to a graph problem. From an algorithmic view point the structural correspondence between the matrix and its graph, as we demonstrate in this paper, leads to a better exposition of the compression heuristics and their efficient computer realization. Array-based data structures are suggested as the basic building-blocks for the efficient implementation of relevant graph algorithms. Results from the numerical testing of a subset of implemented algorithms on a suite of test instances drawn from the standard test matrix collection are presented.

From the theory ofHo0man polynomial, it is known that the adjacency matrix A ofa strongly connected regular digraph oforder n satis3es certain polynomial equation A l P(A)=Jn, where l is a nonnegative integer, P(x) is a polynomial with rational coe5cients, and Jn is the n×n matrix of all ones. In this paper we present some su5cient conditions, in terms ofthe coe5cients of P(x), to ensure that all (0; 1)-matrices satisfying such an equation with l? 0 have an underlying line digraph structure, that is to say, for any solution A there exists a (0; 1)-matrix C satisfying P(C)= Jn=dl and the associated (d-regular) digraph of A, � (A), is the lth iterated line digraph of � (C). As a result, we simplify the study of some digraph classes with order functions asymptotically attaining the Moore bound. ? 2002 Elsevier Science B.V. All rights reserved.

We present the spectrum of the (normalized) graph Laplacian as a systematic tool for the investigation of networks, and we describe basic properties of eigenvalues and eigenfunctions. Processes of graph formation like motif joining or duplication leave characteristic traces in the spectrum. This can suggest hypotheses about the evolution of a graph representing biological data. To this data, we analyze several biological networks in terms of rough qualitative data of their spectra., Comment: 12 pages, 3 figures, Discrete Applied Mathematics, to appear