Incremental and Decremental Maintenance of Planar Width

We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(kn^ε) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and ε > 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(n^ε).     

On Eccentric Connectivity Index and Connectivity

Let G be a finite connected graph. The eccentric connectivity index ξ^c(G) of G is defined as ξ^c(G)= _{v∈V (G)} ec(v)deg(v), where ec(v) and deg(v) denote the eccentricity and degree of a vertex v in G, respectively. In this paper, we give an asymptotically sharp upper bound on the eccentric connectivity index in terms of order and vertex-connectivity and in terms of order and edge-connectivity. We also improve the bounds for triangle-free graphs.     

Bubble-sort网络的连通度和超连通度

Bubble-sort网络Bn是(n-1)-正则,点传递的二部图.在这篇文章中,我们确定了当n≥2时,Bn的(边)-连通度为n-1;当n≥3时,Bn的超(边)-连通度为2n-4.     

Connectivity interdiction

We consider the problem of maximally decreasing the edge-connectivity of an edge-weighted graph by removing a limited set of edges. This problem, which we term connectivity interdiction, falls into a large family of so-called interdiction problems, which have been considered in a variety of contexts. Whereas little is known about the approximability of most interdiction problems, we show that connectivity interdiction admits a PTAS, and a natural special case of it can even be solved efficiently.     

Connectivity calculus

Given a finite hypergraph H = (V, E) and, for each e ϵ E, a collection of nonempty subsets π_e of e, Möbius inversion is used to establish a recursive formula for the number of connected components of the hypergraph H = (V, ∪_eϵEπ_e). As shown elsewhere, this formula is an essential ingredient in the context of a certain divide-and-conquer strategy that allows us to define a dynamical programming scheme solving Steiner's problem for graphs in linear time (however, with a constant depending hyperexponentially on their tree width).     

On Vertex Connectivity and Absolute Algebraic Connectivity for Graphs

Let G be a graph on n vertices with vertex connectivity v with 1 ≤ v ≤ n -2. We produce an attainable upper bound on the absolute algebraic connectivity of G in terms of n and v .     

On Vertex Connectivity and Absolute Algebraic Connectivity for Graphs

Let G be a graph on n vertices with vertex connectivity v with 1 h v h n m 2. We produce an attainable upper bound on the absolute algebraic connectivity of G in terms of n and v .     

Connectivity of cages

A (k; g)-graph is a k-regular graph with girth g. Let f(k; g) be the smallest integer v such there exists a (k; g)-graph with v vertices. A (k; g)-cage is a (k; g)-graph with f(k; g) vertices. In this paper we prove that the cages are monotonic in that f(k; g₁) < f(k; g₂) for all k ≥ 3 and 3 ≥ g₁ < g₂. We use this to prove that (k; g)-cages are 2-connected, and if k = 3 then their connectivity is k. © 1997 John Wiley & Sons, Inc.     

Connectivity in digraphs

Let c(x,y) denote the maximum number of edge-disjoint directed paths joining x to y in the digraph G. It is shown that, for a given point a of G, c(a,x) ≤ c(x,a) for any x implies that the outdegree of a is ≤ its indegree. An immediate consequence is Kotzig's conjecture: Given a digraph G, c(x,y) = c(y,x) for every x, y if and only if the graph is pseudo-symmetric, i.e., each point has the same indegree and outdegree (the “if” part having been proved by Kotzig). The same method is applied to prove a weakened form of a conjecture of N. Robertson, while the original conjecture is disproved.     

Flexible Graph Connectivity

Mathematical Programming - We introduce and study the problem Flexible Graph Connectivity, which in contrast to many classical connectivity problems features a non-uniform failure model. We...     

����fMRI���ݵ�ȫ�Զ�̬�������������������Ե��о�

There're about 10^{11} neurons in the human brain.Through the synaptic junction, neurons have formed a highly complex network.And it is really important to figure out the information expressed in the network, which will contribute to the resolution of the prevention and diagnosis of cognitive disorder of human beings. This paper uses the schizophrenia and healthy controlled subjects' fMRI data to construct the brain network model, in order to explores abnormal topological properties of schizophrenics' brain network based on graph theory. When studying the human brain network information traditionally by the basement of graph theory, it's all assure that the human brain network model has invariance, so it takes the whole period of time series data in constructing human network model, which is a kind static network. However, it's hard to ensure this because of the nonstationarity of fMRI functional time series data. Thus, when constructing human brain network model, we should take its time-variation into consideration, then construct a dynamic brain network. We can explore the brain network information better. In this research, we segment the time series data, using time windows, to constructing dynamic brain network model, then analyze it combined with the knowledge of graph theory, thereby reducing effects that the nonstationarity of fMRI functional time series data will have. Comparing dynamic brain network of the schizophrenic patients with normal controls subjects' in different level, the results show that there are difference in single node property, group network property of schizophrenic patients and normal control subjects' whole brain dynamic functional connectivity network. The discovery of these difference in network topological properties has provide new clues for the further study on the pathological mechanism of schizophrenia.     

Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph

Mycielski introduced a new graph transformation μ(G) for graph G, which is called the Mycielskian of G. A graph G is super connected or simply super-κ (resp. super edge connected or super-λ), if every minimum vertex cut (resp. minimum edge cut) isolates a vertex of G. In this paper, we show that for a connected graph G with |V(G)| ≥ 2, μ(G) is super-κ if and only if δ(G) < 2κ(G), and μ(G) is super-λ if and only if G\ncong K₂{G\ncong K_2}.     

Connectivity in Lattice-Ordered Spaces

The classical order-theoretical characterizations of compact and connected chains, respectively, are extended to wider classes of lattices, using the fact that compactness and (path-) connectedness of maximal chains are closely related to the corresponding properties of the whole lattice (as was already pointed out in an earlier paper due to the second author). Here we replace maximal chains by “links” and study several new types of connectedness in ordered convergence spaces, such as path-connectedness, link-connectedness and 1-connectedness. As a useful framework for these studies, we introduce the concept of “connectivity systems”.     

循环圈的连通度

设G＝C_n（i₁,i₂,…,i_r）是连通循环圈,且k（G）＜δ（G）．本文得到了其连通度的明确表达式κ(G)=min{m|M(n/m,K)|:m是n的真因子,且|M(n/m,K)|相似文献   

n-double图的连通性

设Gl=(V1,E1),G2=(V2,E2)是两个连通图,直积(direct product)(也称为Kronecker product,tensor product和cross product) G1(×)G2的点集为V(G1(×)G2)=V(G1)(×)V(G2),边集为E(G1(×)G2)={(u1,v1)(u2,v2)∶ulu2∈E(G1),vlv2∈E(G2)}.简单图G的n-double图Dn[G]=G(×)Tn,其中n个点的全关系图Tn是完全图Kn在每个点加上一个自环得到的图.在本文中,我们研究了Dn[G]的(边)连通性,超(边)连通性.     

Connectivity in frame matroids

We discuss the relationship between the vertical connectivity of a biased graph Ω and the Tutte connectivity of the frame matroid of Ω (also known as the bias matroid of Ω).     

Connectivity in fractal percolation

We investigate the limiting set in two-dimensional fractal percolation. A new definition of percolation—more natural than the classical one—is studied and compared to the classical one. In the course of these investigations we obtain results about the structure of the limiting set, which may be of interest themselves.