Algebraic connectivity of directed graphs

We consider a generalization of Fiedler's notion of algebraic connectivity to directed graphs. We show that several properties of Fiedler's definition remain valid for directed graphs and present properties peculiar to directed graphs. We prove inequalities relating the algebraic connectivity to quantities such as the bisection width, maximum directed cut and the isoperimetric number. Finally, we illustrate an application to the synchronization in networks of coupled chaotic systems.     

Old and new results on algebraic connectivity of graphs

This paper is a survey of the second smallest eigenvalue of the Laplacian of a graph G, best-known as the algebraic connectivity of G, denoted a(G). Emphasis is given on classifications of bounds to algebraic connectivity as a function of other graph invariants, as well as the applications of Fiedler vectors (eigenvectors related to a(G)) on trees, on hard problems in graphs and also on the combinatorial optimization problems. Besides, limit points to a(G) and characterizations of extremal graphs to a(G) are described, especially those for which the algebraic connectivity is equal to the vertex connectivity.     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

A sharp upper bound on algebraic connectivity using domination number

Let G be a connected graph of order n. The algebraic connectivity of G is the second smallest eigenvalue of the Laplacian matrix of G. A dominating set in G is a vertex subset S such that each vertex of G that is not in S is adjacent to a vertex in S. The least cardinality of a dominating set is the domination number. In this paper, we prove a sharp upper bound on the algebraic connectivity of a connected graph in terms of the domination number and characterize the associated extremal graphs.     

A lower bound for algebraic connectivity based on the connection-graph-stability method

This paper introduces the connection-graph-stability method and uses it to establish a new lower bound on the algebraic connectivity of graphs (the second smallest eigenvalue of the Laplacian matrix of the graph) that is sharper than the previously published bounds. The connection-graph-stability score for each edge is defined as the sum of the lengths of the shortest paths making use of that edge. We prove that the algebraic connectivity of the graph is bounded below by the size of the graph divided by the maximum connection-graph-stability score assigned to the edges.     

Basic Structures of Some Interconnection Networks

Beginning in the late 1980's attractive alternatives to the n-cubes were proposed as the topologies for larger interconnection networks. These graphs tend to have many vertices as well as good connectivity and routing properties. We will look at recent developments on some newer topologies such as star graphs, alternating group graphs, split-stars, arrangement graphs and generalized (n,k) star graphs. We will present results on routing algorithms, various connectivity measures, structural theorems, augmentation, and open problems. Some applications suggest directed graphs, so the directed versions of above graphs will also be considered.     

Graph congruences and what they connote

Abstract

The algebraic notion of a “congruence” seems to be foreign to contemporary graph theory. We propound that it need not be so by developing a theory of congruences of graphs: a congruence on a graph G = (V, E) being a pair (～, ) of which ～ is an equivalence relation on V and is a set of unordered pairs of vertices of G with a special relationship to ～ and E. Kernels and quotient structures are used in this theory to develop homomorphism and isomorphism theorems which remind one of similar results in an algebraic context. We show that this theory can be applied to deliver structural decompositions of graphs into “factor” graphs having very special properties, such as the result that each graph, except one, is a subdirect product of graphs with universal vertices. In a final section, we discuss corresponding concepts and briefly describe a corresponding theory for graphs which have a loop at every vertex and which we call loopy graphs. They are in a sense more “algebraic” than simple graphs, with their meet-semilattices of all congruences becoming complete algebraic lattices.     

Additivity of the crossing number of graphs with connectivity 2

We prove that the crossing number of graphs with connectivity 2 has in certain cases an additive property analogous to that of crossing number of graphs with connectivity ≤1.     

On the connectivity of randomm-orientable graphs and digraphs

We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex. We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning trees and arborescences. We also examine the relationship between our results and certain results of Erdős and Rényi.     

On random mapping patterns

Random mapping patterns may be represented by unlabelled directed graphs in which each point has out-degree one. We determine the asymptotic behaviour of various parameters associated with such graphs, such as the expected number of points belonging to cycles and the expected number of components. Dedicated to Paul Erdős on his seventieth birthday     

Maximizing signless Laplacian or adjacency spectral radius of graphs subject to fixed connectivity

In this paper, we characterize the graphs with maximum signless Laplacian or adjacency spectral radius among all graphs with fixed order and given vertex or edge connectivity. We also discuss the minimum signless Laplacian or adjacency spectral radius of graphs subject to fixed connectivity. Consequently we give an upper bound of signless Laplacian or adjacency spectral radius of graphs in terms of connectivity. In addition we confirm a conjecture of Aouchiche and Hansen involving adjacency spectral radius and connectivity.     

Ihara zeta functions of digraphs

After defining and exploring some of the properties of Ihara zeta functions of digraphs, we improve upon Kotani and Sunada’s bounds on the poles of Ihara zeta functions of undirected graphs by considering digraphs whose adjacency matrices are directed edge matrices.     

On multiplicative graphs and the product conjecture

We study the following problem: which graphsG have the property that the class of all graphs not admitting a homomorphism intoG is closed under taking the product (conjunction)? Whether all undirected complete graphs have the property is a longstanding open problem due to S. Hedetniemi. We prove that all odd undirected cycles and all prime-power directed cycles have the property. The former result provides the first non-trivial infinite family of undirected graphs known to have the property, and the latter result verifies a conjecture of Ne?et?il and Pultr These results allow us (in conjunction with earlier results of Ne?et?il and Pultr [17], cf also [7]) to completely characterize all (finite and infinite, directed and undirected) paths and cycles having the property. We also derive the property for a wide class of 3-chromatic graphs studied by Gerards, [5].     

Finite-type invariants for graphs and graph reconstructions

Many of the fundamental open problems in graph theory have the following general form: How much information does one need to know about a graph G in order to determine G uniquely. In this article we investigate a new approach to this sort of problem motivated by the notion of a finite-type invariant, recently introduced in the study of knots. We introduce the concepts of vertex-finite-type invariants of graphs, and edge-finite-type invariants of graphs, and show that these sets of functions have surprising algebraic properties. The study of these invariants is intimately related with the classical vertex- and edge-reconstruction conjectures, and we demonstrate that the algebraic properties of the finite-type invariants lead immediately to some of the fundamental results in graph reconstruction theory.     

Laplacians and the Cheeger Inequality for Directed Graphs

We consider Laplacians for directed graphs and examine their eigenvalues. We introduce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then define a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems.Received September 8, 2004     

Extreme values of the stationary distribution of random walks on directed graphs

We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on n vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions.     

Extremal regular graphs for the eccentric connectivity index

Abstract

Topological indices are useful tools for identifying properties of chemicals directly from their molecular structure, and are used extensively in pharmaceutical drug design. One such graph-invariant index is the eccentric connectivity index. If G is a connected graph with vertex set V, then the eccentric connectivity index of G, ξ^C (G), is defined as Σ_vεV deg(v) ec(v) where deg(v) is the degree of vertex v and ec(v) is its eccentricity. Current research investigates mathematical properties of this index, and in particular, considers bounds in terms of other parameters. Recently, both Do?li?, Saheli and Vuki?evi? [7] and Ili? [12] have stated that it would be interesting to determine extremal graphs with respect to the eccentric connectivity index, for regular (and more specifically, cubic) graphs. When considering such regular graphs, results could equivalently be reformulated in terms of the average eccentricity of the graph. In this note we address this open problem.     

Minimally 3-connected isotropic systems

Isotropic systems are structures which unify some properties of 4-regular graphs and selfdual properties of binary matroids, such as connectivity and minors. In this paper, we find the minimally 3-connected isotropic systems. This result implies the binary part Tutte's wheels and whirls theorem.     

The least eigenvalue of graphs with given connectivity

Let G be a simple graph and A(G) be the adjacency matrix of G. The eigenvalues of G are those of A(G). In this paper, we characterize the graphs with the minimal least eigenvalue among all graphs of fixed order with given vertex connectivity or edge connectivity.