Equienergetic self-complementary graphs

In this paper equienergetic self-complementary graphs on p vertices for every p = 4k, k ⩾ 2 and p = 24t + 1, t ⩾ 3 are constructed.     

Bicyclic graphs with exactly two main eigenvalues

An eigenvalue of a graph G is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero, and it is well known that a graph has exactly one main eigenvalue if and only if it is regular. In this work, all connected bicyclic graphs with exactly two main eigenvalues are determined.     

Random walks on random simple graphs

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)^a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc.     

Random walks on highly symmetric graphs

We consider uniform random walks on finite graphs withn nodes. When the hitting times are symmetric, the expected covering time is at least 1/2n logn-O(n log logn) uniformly over all such graphs. We also obtain bounds for the covering times in terms of the eigenvalues of the transition matrix of the Markov chain. For distance-regular graphs, a general lower bound of (n-1) logn is obtained. For hypercubes and binomial coefficient graphs, the limit law of the covering time is obtained as well.     

Random walks systems on complete graphs

We study two versions of random walks systems on complete graphs. In the first one, the random walks have geometrically distributed lifetimes so we define and identify a non-trivial critical parameter related to the proportion of visited vertices before the process dies out. In the second version, the lifetimes depend on the past of the process in a non-Markovian setup. For that version, we present results obtained from computational analysis, simulations and a mean field approximation. These three approaches match.     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

Cover time and mixing time of random walks on dynamic graphs

The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.     

On the multiplicity of the eigenvalues of a graph

Given a graph G with characteristic polynomial ϕ(t), we consider the ML-decomposition ϕ(t) = q ₁(t)q ₂(t)² ... q _m (t)^m, where each q _i (t) is an integral polynomial and the roots of ϕ(t) with multiplicity j are exactly the roots of q _j (t). We give an algorithm to construct the polynomials q _i (t) and describe some relations of their coefficients with other combinatorial invariants of G. In particular, we get new bounds for the energy E(G) = |λ_i| of G, where λ₁, λ₂, ..., λ_n are the eigenvalues of G (with multiplicity). Most of the results are proved for the more general situation of a Hermitian matrix whose characteristic polynomial has integral coefficients. This work was done during a visit of the second named author to UNAM.     

Covering times of random walks on bounded degree trees and other graphs

The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)⁽¹⁾ andO(|V| |E|/d _min)⁽²⁾ imply an upper bound ofO(n ²). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log² n). The previous lower bound was (|V| log |V|) for trees.⁽²⁾ In our main result, we show a lower bound of (|V| (log _{d max} |V|)²) for trees, which yields a lower bound of (n log² n). We also extend our techniques to show an upper bound for general graphs ofO(max{E T_i} log |V|).     

The number of edges of radius-invariant graphs

The eccentricity e(υ) of vertex υ is defined as a distance to a farthest vertex from υ. The radius of a graph G is defined as r(G) = {e(u)}. We consider properties of unchanging the radius of a graph under two different situations: deleting an arbitrary edge and deleting an arbitrary vertex. This paper gives the upper bounds for the number of edges in such graphs. Supported by VEGA grant No. 1/0084/08.     

Closed walks and eigenvalues of Abelian Cayley graphs

We show that Abelian Cayley graphs contain many closed walks of even length. This implies that given $k?3$, for each $\mathrm{?}>0$, there exists $C=C(\mathrm{?},k)>0$ such that for each Abelian group G and each symmetric subset S of G with $1?S$, the number of eigenvalues ${\lambda }_i$ of the Cayley graph $X=X(G,S)$ such that ${\lambda }_i?k?\mathrm{?}$ is at least $C?|G|$. This can be regarded as an analogue for Abelian Cayley graphs of a theorem of Serre for regular graphs. To cite this article: S.M. Cioab?, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

On the power of a perturbation for testing non-isomorphism of graphs

In this paper we prove an inverted version of A. J. Schwenk's result, which in turn is related to Ulam's reconstruction conjecture. Instead of deleting vertices from an undirected graphG, we add a new vertexv and join it to all other vertices ofG to get a perturbed graphG+v. We derive an expression for the characteristic polynomial of the perturbed graphG+v in terms of the characteristic polynomial of the original graphG. We then show the extent to which the characteristic polynomials of the perturbed graphs can be used in determining whether two graphs are non-isomorphic.This work was supported by the U.S. Army Research Office under Grant DAAG29-82-K-0107.     

On bipartite graphs with small number of laplacian eigenvalues greater than two and three

All connected bipartite graphs with exactly two Laplacian eigenvalues greater than two are determined. Besides, all connected bipartite graphs with exactly one Laplacian eigenvalue greater than three are determined.     

On bipartite graphs with small number of laplacian eigenvalues greater than two and three

All connected bipartite graphs with exactly two Laplacian eigenvalues greater than two are determined. Besides, all connected bipartite graphs with exactly one Laplacian eigenvalue greater than three are determined.     

The independence polynomial of rooted products of graphs

A stable (or independent) set in a graph is a set of pairwise nonadjacent vertices thereof. The stability numberα(G) is the maximum size of stable sets in a graph G. The independence polynomial of G is