Upper bounds on the independence and the clique covering number

New upper bounds for the independence number and for the clique covering number of a graph are given in terms of the rank, respectively the eigenvalues, of the adjacency matrix. We formulate a conjecture concerning an upper bound of the clique covering number. This upper bound is related to an old conjecture of Alan J. Hoffman which is shown to be false. Key words: adjacency matrix, eigenvalues, independence number, clique covering number. AMS classification: 05C.     

Unit gain graphs with two distinct eigenvalues and systems of lines in complex space

Since the introduction of the Hermitian adjacency matrix for digraphs, interest in so-called complex unit gain graphs has surged. In this work, we consider gain graphs whose spectra contain the minimum number of two distinct eigenvalues. Analogously to graphs with few distinct eigenvalues, a great deal of structural symmetry is required for a gain graph to attain this minimum. This allows us to draw a surprising parallel to well-studied systems of lines in complex space, through a natural correspondence to unit-norm tight frames. We offer a full classification of two-eigenvalue gain graphs with degree at most 4, or with multiplicity at most 3. Intermediate results include an extensive review of various relevant concepts related to lines in complex space, including SIC-POVMs, MUBs and geometries such as the Coxeter-Todd lattice, and many examples obtained as induced subgraphs by employing a technique parallel to the dismantling of association schemes. Finally, we touch on an innovative application of simulated annealing to find examples by computer.     

On graphs with exactly one anti-adjacency eigenvalue and beyond

The anti-adjacency matrix of a graph is constructed from the distance matrix of a graph by keeping each row and each column only the largest distances. This matrix can be interpreted as the opposite of the adjacency matrix, which is instead constructed from the distance matrix of a graph by keeping in each row and each column only the distances equal to 1. The (anti-)adjacency eigenvalues of a graph are those of its (anti-)adjacency matrix. Employing a novel technique introduced by Haemers (2019) [9], we characterize all connected graphs with exactly one positive anti-adjacency eigenvalue, which is an analog of Smith's classical result that a connected graph has exactly one positive adjacency eigenvalue iff it is a complete multipartite graph. On this basis, we identify the connected graphs with all but at most two anti-adjacency eigenvalues equal to ?2 and 0. Moreover, for the anti-adjacency matrix we determine the HL-index of graphs with exactly one positive anti-adjacency eigenvalue, where the HL-index measures how large in absolute value may be the median eigenvalues of a graph. We finally propose some problems for further study.     

A sharp upper bound on the spectral radius of weighted graphs

We consider weighted graphs, where the edge weights are positive definite matrices. The eigenvalues of a graph are the eigenvalues of its adjacency matrix. We obtain an upper bound on the spectral radius of the adjacency matrix and characterize graphs for which the bound is attained.     

Extremal graph characterization from the bounds of the spectral radius of weighted graphs

We consider weighted graphs, where the edge weights are positive definite matrices. The eigenvalues of a graph are the eigenvalues of its adjacency matrix. We obtain a lower bound and an upper bound on the spectral radius of the adjacency matrix of weighted graphs and characterize graphs for which the bounds are attained.     

Restricted random walks on a graph

The problem of a restricted random walk on graphs, which keeps track of the number of immediate reversal steps, is considered by using a transfer matrix formulation. A closed-form expression is obtained for the generating function of the number ofn-step walks withr reversal steps for walks on any graph. In the case of graphs of a uniform valence, we show that our result has a probabilistic meaning, and deduce explicit expressions for the generating function in terms of the eigenvalues of the adjacency matrix. Applications to periodic lattices and the complete graph are given.Supported in part by National Science Foundation Grant DMR-9614170.     

The new upper bounds on the spectral radius of weighted graphs

Let us consider weighted graphs, where the weights of the edges are positive definite matrices. The eigenvalues of a weighted graph are the eigenvalues of its adjacency matrix and the spectral radius of a weighted graph is also the spectral radius of its adjacency matrix. In this paper, we obtain two upper bounds for the spectral radius of weighted graphs and compare with a known upper bound. We also characterize graphs for which the upper bounds are attained.     

Arc transitive covering digraphs and their eigenvalues

We prove that every finite regular digraph has an arc-transitive covering digraph (whose arcs are equivalent under automorphisms) and every finite regular graph has a 2-arc-transitive covering graph. As a corollary, we sharpen C. D. Godsil's results on eigenvalues and minimum polynomials of vertex-transitive graphs and digraphs. Using Godsil's results, we prove, that given an integral matrix A there exists an arc-transitive digraph X such that the minimum polynomial of A divides that of X. It follows that there exist arc-transitive digraphs with nondiagonalizable adjacency matrices, answering a problem by P. J. Cameron. For symmetric matrices A, we construct a 2-arc-transitive graphs X.     

Optimal embeddings of odd ladders into a hypercube

An embedding of a graph G into a hypercube of dimension k is called optimal if the number of vertices of G is greater than 2^k−1. A ladder is a special graph in which two paths of the same length are connected in such a way that each vertex of the first one is connected by a path – called a rung – to its corresponding vertex in the second one. We construct an optimal embedding for every ladder with rungs of odd sizes greater than 6 into a dense set of a hypercube.     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 2010     

On the adjacency matrix of a threshold graph

A threshold graph on n   vertices is coded by a binary string of length n−1$n-1$. We obtain a formula for the inertia of (the adjacency matrix of) a threshold graph in terms of the code of the graph. It is shown that the number of negative eigenvalues of the adjacency matrix of a threshold graph is the number of ones in the code, whereas the nullity is given by the number of zeros in the code that are preceded by either a zero or a blank. A formula for the determinant of the adjacency matrix of a generalized threshold graph and the inverse, when it exists, of the adjacency matrix of a threshold graph are obtained. Results for antiregular graphs follow as special cases.     

Applications of a theorem by Ky Fan in the theory of graph energy

The energy of a graph G is equal to the sum of the absolute values of the eigenvalues of G, which in turn is equal to the sum of the singular values of the adjacency matrix of G. Let X, Y, and Z be matrices, such that X+Y=Z. The Ky Fan theorem establishes an inequality between the sum of the singular values of Z and the sum of the sum of the singular values of X and Y. This theorem is applied in the theory of graph energy, resulting in several new inequalities, as well as new proofs of some earlier known inequalities.     

The energy change of weighted graphs

The energy of an (edge)-weighted graph is the sum of the absolute values of the eigenvalues of its (weighted) adjacency matrix. We study how the energy of a weighted graph changes when the weights change. We give some sufficient conditions so that the energy of a weighted graph increases when the positive weight increases. We also characterize some classes of weighted graphs satisfying these sufficient conditions.     

Edge-distance-regular graphs

Edge-distance-regularity is a concept recently introduced by the authors which is similar to that of distance-regularity, but now the graph is seen from each of its edges instead of from its vertices. More precisely, a graph Γ with adjacency matrix A is edge-distance-regular when it is distance-regular around each of its edges and with the same intersection numbers for any edge taken as a root. In this paper we study this concept, give some of its properties, such as the regularity of Γ, and derive some characterizations. In particular, it is shown that a graph is edge-distance-regular if and only if its k-incidence matrix is a polynomial of degree k in A multiplied by the (standard) incidence matrix. Also, the analogue of the spectral excess theorem for distance-regular graphs is proved, so giving a quasi-spectral characterization of edge-distance-regularity. Finally, it is shown that every nonbipartite graph which is both distance-regular and edge-distance-regular is a generalized odd graph.     

Quantum walks and the size of the graph

A continuous-time quantum walk is modelled using a graph. In this short paper, we provide lower bounds on the size of a graph that would allow for some quantum phenomena to occur. Among other things, we show that, in the adjacency matrix quantum walk model, the number of edges is bounded below by a cubic function on the eccentricity of a periodic vertex. This gives some idea on the shape of a graph that would admit periodicity or perfect state transfer. We also raise some extremal type of questions in the end that could lead to future research.     

整循环图的秩（英文）

A graph is called an integral graph if it has an integral spectrum i.e.,all eigenvalues are integers.A graph is called circulant graph if it is Cayley graph on the circulant group,i.e.,its adjacency matrix is circulant.The rank of a graph is defined to be the rank of its adjacency matrix.This importance of the rank,due to applications in physics,chemistry and combinatorics.In this paper,using Ramanujan sums,we study the rank of integral circulant graphs and gave some simple computational formulas for the rank and provide an example which shows the formula is sharp.     

Algebraic Characterizations of Graph Regularity Conditions

It is well-known that a connected finite simple graph is regular if and only if the all-ones matrix spans an ideal of its adjacency algebra. We show that several other graph regularity conditions involving pairs and triples of vertices also have ideal theoretic characterizations in some appropriate algebras.     

Multiple cover time

Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within a constant factor of the number of times predicted by the stationary distribution. Thus the blanket time is, essentially, the number of steps required of a random walk in order that the observed distribution reflect the stationary distribution. We provide substantial evidence for the following conjecture: that the blanket time of a graph never exceeds the cover time by more than a constant factor. In other words, at the cost of a multiplicative constant one can hit every vertex often instead of merely once. We prove the conjecture in the case where the cover time and maximum hitting time differ by a logarithmic factor. This case includes almost all graphs, as well as most “natural” graphs: the hypercube, k-dimensional lattices for k ≥ 2, balanced k-ary trees, and expanders. We further prove the conjecture for perhaps the most natural graphs not falling in the above case: paths and cycles. Finally, we prove the conjecture in the case of independent stochastic processes. © 1996 John Wiley & Sons, Inc. Random Struct. Alg., 9 , 403–411 (1996)     

The integral graphs with index 3 and exactly two main eigenvalues

A graph is called integral if the spectrum of its adjacency matrix has only integral eigenvalues. An eigenvalue of a graph is called main eigenvalue if it has an eigenvector such that the sum of whose entries is not equal to zero. In this paper, we show that there are exactly 25 connected integral graphs with exactly two main eigenvalues and index 3.