On the restricted connectivity and superconnectivity in graphs with given girth

The restricted connectivity κ^′(G) of a connected graph G is defined as the minimum cardinality of a vertex-cut over all vertex-cuts X such that no vertex u has all its neighbors in X; the superconnectivity κ₁(G) is defined similarly, this time considering only vertices u in G-X, hence κ₁(G)?κ^′(G). The minimum edge-degree of G is ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, d(u) standing for the degree of a vertex u. In this paper, several sufficient conditions yielding κ₁(G)?ξ(G) are given, improving a previous related result by Fiol et al. [Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17-31] and guaranteeing κ₁(G)=κ^′(G)=ξ(G) under some additional constraints.     

On 3-restricted edge connectivity of undirected binary Kautz graphs

An edge cut of a connected graph is m-restricted if its removal leaves every component having order at least m. The size of minimum m-restricted edge cuts of a graph G is called its m-restricted edge connectivity. It is known that when m≤4, networks with maximal m-restricted edge connectivity are most locally reliable. The undirected binary Kautz graph UK(2,n) is proved to be maximal 2- and 3-restricted edge connected when n≥3 in this work. Furthermore, every minimum 2-restricted edge cut disconnects this graph into two components, one of which being an isolated edge.     

极大3限制边连通二部图的充分条件

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λ_k(G).定义ξ_k(G)=min{[X,■]:|X|=k,G[X]连通,■=V(G)\X}.称图G是极大k限制边连通的,如果λ_k(G)=ξ_k(G).本文给出了围长为g>6的极大3限制边连通二部图的充分条件.     

A conjecture on the algebraic connectivity of connected graphs with fixed girth

In this paper, we completely solve a conjecture on the minimum algebraic connectivity of connected graphs with fixed girth (see [S. Fallat, S. Kirkland, Extremizing algebraic connectivity subject to graph theoretic constraints, Electron. J. Linear Algebra 3 (1998) 48-74]).     

Minimally 3-restricted edge connected graphs

For a connected graph G=(V,E), an edge set S⊂E is a 3-restricted edge cut if G−S is disconnected and every component of G−S has order at least three. The cardinality of a minimum 3-restricted edge cut of G is the 3-restricted edge connectivity of G, denoted by λ₃(G). A graph G is called minimally 3-restricted edge connected if λ₃(G−e)<λ₃(G) for each edge e∈E. A graph G is λ₃-optimal if λ₃(G)=ξ₃(G), where , ω(U) is the number of edges between U and V?U, and G[U] is the subgraph of G induced by vertex set U. We show in this paper that a minimally 3-restricted edge connected graph is always λ₃-optimal except the 3-cube.     

Regular graphs with given girth pair

The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair is proved and simple bounds for their smallest order are developed. Several infinite classes of such graphs are constructed and it is proved that two of these families consist of smallest graphs.     

On the 3-restricted edge connectivity of permutation graphs

An edge cut W of a connected graph G is a k-restricted edge cut if G−W is disconnected, and every component of G−W has at least k vertices. The k-restricted edge connectivity is defined as the minimum cardinality over all k-restricted edge cuts. A permutation graph is obtained by taking two disjoint copies of a graph and adding a perfect matching between the two copies. The k-restricted edge connectivity of a permutation graph is upper bounded by the so-called minimum k-edge degree. In this paper some sufficient conditions guaranteeing optimal k-restricted edge connectivity and super k-restricted edge connectivity for permutation graphs are presented for k=2,3.     

Note on robust critical graphs with large odd girth

A graph G is (k+1)-critical if it is not k-colourable but G−e is k-colourable for any edge e∈E(G). In this paper we show that for any integers k≥3 and l≥5 there exists a constant c=c(k,l)>0, such that for all , there exists a (k+1)-critical graph G on n vertices with and odd girth at least ?, which can be made (k−1)-colourable only by the omission of at least cn² edges.     

Connectivity of graphs with given girth pair

Girth pairs were introduced by Harary and Kovács [Regular graphs with given girth pair, J. Graph Theory 7 (1983) 209-218]. The odd girth (even girth) of a graph is the length of a shortest odd (even) cycle. Let g denote the smaller of the odd and even girths, and let h denote the larger. Then (g,h) is called the girth pair of the graph. In this paper we prove that a graph with girth pair (g,h) such that g is odd and h?g+3 is even has high (vertex-)connectivity if its diameter is at most h-3. The edge version of all results is also studied.     

Small vertex‐transitive and Cayley graphs of girth six and given degree: an algebraic approach

We examine the existing constructions of the smallest known vertex‐transitive graphs of a given degree and girth 6. It turns out that most of these graphs can be described in terms of regular lifts of suitable quotient graphs. A further outcome of our analysis is a precise identification of which of these graphs are Cayley. We also investigate higher level of transitivity of the smallest known vertex‐transitive graphs of a given degree and girth 6 and relate their constructions to near‐difference sets. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:265‐284, 2011     

Matchings in graphs of odd regularity and girth

We establish lower bounds on the matching number of graphs of given odd regularity d$d$ and odd girth g$g$, which are sharp for many values of d$d$ and g$g$. For d=g=5$d=g=5$, we characterize all extremal graphs.     

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 note on minimal directed graphs with given girth

Caccetta and Häggkvist conjectured that the minimum order of a directed graph with girth g and outdegree not less than r is r(g − 1) + 1. They proved this conjecture for r = 2. We prove it for r = 3.     

Essential edge connectivity of line graphs

Let $G$ be a graph and $L\left(G\right)$ be its line graph. In 1969, Chartrand and Stewart proved that ${\kappa }^{\prime }\left(L\left(G\right)\right)\ge 2{\kappa }^{\prime }\left(G\right)?2$, where ${\kappa }^{\prime }\left(G\right)$ and ${\kappa }^{\prime }\left(L\left(G\right)\right)$ denote the edge connectivity of $G$ and $L\left(G\right)$ respectively. We show a similar relationship holds for the essential edge connectivity of $G$ and $L\left(G\right)$, written ${\kappa }_e^{\prime }\left(G\right)$ and ${\kappa }_e^{\prime }\left(L\left(G\right)\right)$, respectively. In this note, it is proved that if $L\left(G\right)$ is not a complete graph and $G$ does not have a vertex of degree two, then ${\kappa }_e^{\prime }\left(L\left(G\right)\right)\ge 2{\kappa }_e^{\prime }\left(G\right)?2$. An immediate corollary is that $\kappa \left(L^2\left(G\right)\right)\ge 2\kappa \left(L\left(G\right)\right)?2$ for such graphs $G$, where the vertex connectivity of the line graph $L\left(G\right)$ and the second iterated line graph $L^2\left(G\right)$ are written as $\kappa \left(L\left(G\right)\right)$ and $\kappa \left(L^2\left(G\right)\right)$ respectively.     

On maximal 3-restricted edge connectivity and reliability analysis of hypercube networks

It is shown in this work that all n-dimensional hypercube networks for n ? 4 are maximally 3-restricted edge connected. Employing this observation, we analyze the reliability of hypercube networks and determine the first 3n − 5 coefficients of the reliability polynomial of n-cube networks.     

On the spectral spread of bicyclic graphs with given girth

The spectral spread of a graph is defined to be the difference between the largest and the least eigenvalue of the adjacency matrix of the graph. A graph G is said to be bicyclic, if G is connected and |E(G)| = |V(G)|+ 1. Let B(n, g) be the set of bicyclic graphs on n vertices with girth g. In this paper some properties about the least eigenvalues of graphs are given, by which the unique graph with maximal spectral spread in B(n, g) is determined.     

图的3限制性边割

3限制性边割将连通图分离成不连通图，使其各连通分支含有至少3个顶点．含3限制性边割的图在本文中得到刻划．     

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.