Graphs with prescribed local connectivities

A graph G is locally n-connected (locally n-edge connected) if the neighborhood of each vertex of G is n-connected (n-edge connected). The local connectivity (local edge-connectivity) of G is the maximum n for which G is locally n-connected (locally n-edge connected). It is shown that if k and m are integers with O k < m, then a graph exists which has connectivity m and local connectivity k. Furthermore, such a graph with smallest order is determined. Corresponding results are obtained involving the local connectivity and the local edge-conectivity.     

Eulerian detachments with local edge-connectivity

For a graph G, a detachment operation at a vertex transforms the graph into a new graph by splitting the vertex into several vertices in such a way that the original graph can be obtained by contracting all the split vertices into a single vertex. A graph obtained from a given graph G by applying detachment operations at several vertices is called a detachment of graph G. While detachment operations may decrease the connectivity of graphs, there are several works on conditions for preserving the connectivity. In this paper, we present necessary and sufficient conditions for a given graph/digraph to have an Eulerian detachment that satisfies a given local edge-connectivity requirement. We also discuss conditions for the detachment to be loopless.     

Cyclic and cliquewise connectedness of line graphs

The connectivity and the line connectivity numbers of a graph and of its line graph are dependent on each other. Another important related notion is the cyclic connectedness, and we establish here a strong relationship between the cyclic connectivity number and the cyclic line connectivity number of a graph and of its line graph. Moreover, we introduce a related new notion involving cliques instead of cycles and undertake a similar investigation.     

On the distance spectral radius of bipartite graphs

In this paper, we determine the unique graph with minimum distance spectral radius among all connected bipartite graphs of order $n$ with a given matching number. Moreover, we characterize the graphs with minimal distance spectral radius in the class of all connected bipartite graphs with a given vertex connectivity.     

Vertex downgrading to minimize connectivity

Mathematical Programming - We consider the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given...     

Lower bounds of the Laplacian spectrum of graphs based on diameter

Let G be a connected graph of order n. The diameter of G is the maximum distance between any two vertices of G. In the paper, we will give some lower bounds for the algebraic connectivity and the Laplacian spectral radius of G in terms of the diameter of G.     

Blocks in <Emphasis Type="Italic">k</Emphasis>-connected graphs

For a k-connected graph, we define the notion of a block by means of local vertex connectivity and prove some properties of blocks that generalize the properties of classical biconnected blocks of a connected graph. We investigate the structure of the decomposition of a k-connected graph by several cuts. Bibliography: 9 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 293, 2002, pp. 59–93.This revised version was published online in April 2005 with a corrected cover date and article title.     

二元图的最佳连通性

本文介绍二元图的最佳连通性问题，给出了有关最佳连通性的若干结果；并就一般情形，给出了二元图最佳连通性问题的解．     

On several sorts of connectivity

For a graph G, we can consider the minimum number of vertices (resp. edges) whose deletion disconnects the graph and such that two of the components created by teh removal of the vertices (resp. the edges, satisfy no additional condition (usual connectivities) or must contain: at least one edge (^#connectivities) or at least one cycle (cyclic connectivities). Thus, we can define six sorts of connectivity for a given graph. In this paper, we give upper bounds for the different types of connectivity and results about the graphs reaching these upper bounds or having connectivity 0 and we investigate relations between these six sorts of connectivity.     

Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian

In analogy to the absolute algebraic connectivity of Fiedler, we study the problem of minimizing the maximum eigenvalue of the Laplacian of a graph by redistributing the edge weights. Via semidefinite duality this leads to a graph realization problem in which nodes should be placed as close as possible to the origin while adjacent nodes must keep a distance of at least one. We prove three main results for a slightly generalized form of this embedding problem. First, given a set of vertices partitioning the graph into several or just one part, the barycenter of each part is embedded on the same side of the affine hull of the set as the origin. Second, there is an optimal realization of dimension at most the tree-width of the graph plus one and this bound is best possible in general. Finally, bipartite graphs possess a one dimensional optimal embedding.     

图的代数连通度的界(英文)

本文首先给出了简单图的度序列的平方和的上界,利用这些结果,求出了简单图的代数连通度的几个上下界并确定了它们的临界图。另外,文章也给出了加权图的代数连通度的一个下界。     

Characterization of graphs with infinite cyclic edge connectivity

In this paper, we characterize the graphs with infinite cyclic edge connectivity. Then we design an efficient algorithm to determine whether a graph has finite cyclic edge connectivity or infinite cyclic edge connectivity.     

A counterexample to the conjecture of Aksionov and Mel'nikov on non-3-colorable planar graphs

Aksinov and Mel'nikov conjectured that every edge-critical non-3-colorable planar graph with triangles at distance at least one has connectivity 2. By constructing 3-connected edge-critical non-3-colorable planar graphs in which the distance between triangles is 2 or more, this conjecture is refuted.     

Limits and Dynamics of Randomly Connected Neuronal Networks

Networks of the brain are composed of a very large number of neurons connected through a random graph and interacting after random delays that both depend on the anatomical distance between cells. In order to comprehend the role of these random architectures on the dynamics of such networks, we analyze the mesoscopic and macroscopic limits of networks with random correlated connectivity weights and delays. We address both averaged and quenched limits, and show propagation of chaos and convergence to a complex integral McKean-Vlasov equations with distributed delays. We then instantiate a completely solvable model illustrating the role of such random architectures in the emerging macroscopic activity. We particularly focus on the role of connectivity levels in the emergence of periodic solutions.     

Asymptotic connectivity of infinite graphs

We introduce the notion of the asymptotic connectivity of a graph by generalizing to infinite graphs average connectivity as defined by Beineke, Oellermann, and Pippert. Combinatorial and geometric properties of asymptotic connectivity are then explored. In particular, we compute the asymptotic connectivity of a number of planar graphs in order to determine the extent to which this measure correlates with the large-scale geometry of the graph.     

Distributed computation of virtual coordinates for greedy routing in sensor networks

Sensor networks are emerging as a paradigm for future computing, but pose a number of challenges in the fields of networking and distributed computation. One challenge is to devise a greedy routing protocol—one that routes messages through the network using only information available at a node or its neighbors. Modeling the connectivity graph of a sensor network as a 3-connected planar graph, we describe how to compute on the network in a distributed and local manner a special geometric embedding of the graph. This embedding supports a geometric routing protocol called “greedy routing” based on the “virtual” coordinates of the nodes derived from the embedding.     

Connectivity threshold and recovery time in rank-based models for complex networks

We study a generalized version of the protean graph (a probabilistic model of the World Wide Web) with a power law degree distribution, in which the degree of a vertex depends on its age as well as its rank. The main aim of this paper is to study the behaviour of the protean process near the connectivity threshold. Since even above the connectivity threshold it is still possible that the graph becomes disconnected, it is important to investigate the recovery time for connectivity, that is, how long we have to wait to regain the connectivity.     

The algebraic connectivity of graphs under perturbation

In this paper, we investigate how the algebraic connectivity of a connected graph behaves when the graph is perturbed by separating or grafting an edge.     

Maximum algebraic connectivity augmentation is NP-hard

The algebraic connectivity of a graph, which is the second-smallest eigenvalue of the Laplacian of the graph, is a measure of connectivity. We show that the problem of adding a specified number of edges to an input graph to maximize the algebraic connectivity of the augmented graph is NP-hard.     

Minimizing algebraic connectivity over graphs made with some given blocks

This article describes the structure of the graph minimizing the algebraic connectivity among all connected graphs made with some given blocks with fixed number of pendant blocks, the blocks that have exactly one point of articulation. As an application, we conclude that over all graphs made with given blocks, the algebraic connectivity is minimum for a graph whose block structure is a path.