Edge fault tolerance analysis of super k-restricted connected networks

An edge cut X of a connected graph G is a k-restricted edge cut if G-X is disconnected and every component of G-X has at least k vertices. Additionally, if the deletion of a minimum k-restricted edge cut isolates a connected component of k vertices, then the graph is said to be super-λ_k. In this paper, several sufficient conditions yielding super-λ_k graphs are given in terms of the girth and the diameter.     

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.     

On cyclic edge-connectivity of transitive graphs

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is said to be cyclically separable. For a cyclically separable graph G, the cyclic edge-connectivity cλ(G) is the cardinality of a minimum cyclic edge-cut of G. In this paper, we first prove that for any cyclically separable graph G, , where ω(X) is the number of edges with one end in X and the other end in V(G)?X. A cyclically separable graph G with cλ(G)=ζ(G) is said to be cyclically optimal. The main results in this paper are: any connected k-regular vertex-transitive graph with k≥4 and girth at least 5 is cyclically optimal; any connected edge-transitive graph with minimum degree at least 4 and order at least 6 is cyclically optimal.     

Super edge-connectivity of mixed Cayley graph

A graph X is max-λ if λ(X)=δ(X). A graph X is super-λ if X is max-λ and every minimum edge-cut set of X isolates one vertex. In this paper, we proved that for all but a few exceptions, the mixed Cayley graph which is defined as a new kind of semi-regular graph is max-λ and super-λ.     

3-restricted connectivity of graphs with given girth

Let G = （V, E） be a connected graph. X belong to V（G） is a vertex set. X is a 3-restricted cut of G, if G- X is not connected and every component of G- X has at least three vertices. The 3-restricted connectivity κ3（G） （in short κ3） of G is the cardinality of a minimum 3-restricted cut of G. X is called κ3-cut, if ｜X｜ = κ3. A graph G is κ3-connected, if a 3-restricted cut exists. Let G be a graph girth g ≥ 4, κ3（G） is min{d（x） ＋ d（y） ＋ d（z） - 4 ： xyz is a 2-path of G}. It will be shown that κ3（G） = ξ3（G） under the condition of girth.     

On (s,t)-supereulerian graphs in locally highly connected graphs

Given two nonnegative integers s and t, a graph G is (s,t)-supereulerian if for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y|≤t, there is a spanning eulerian subgraph H of G that contains X and avoids Y. We prove that if G is connected and locally k-edge-connected, then G is (s,t)-supereulerian, for any pair of nonnegative integers s and t with s+t≤k−1. We further show that if s+t≤k and G is a connected, locally k-edge-connected graph, then for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y≤t, there is a spanning eulerian subgraph H that contains X and avoids Y, if and only if G−Y is not contractible to K₂ or to K_2,l with l odd.     

Hamilton connectivity of line graphs and claw‐free graphs

Let G be a graph and let V₀ = {ν∈ V(G): d_G(ν) = 6}. We show in this paper that: (i) if G is a 6‐connected line graph and if |V₀| ≤ 29 or G[V₀] contains at most 5 vertex disjoint K₄'s, then G is Hamilton‐connected; (ii) every 8‐connected claw‐free graph is Hamilton‐connected. Several related results known before are generalized. © 2005 Wiley Periodicals, Inc. J Graph Theory     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

An extension of Tutte's 1-factor theorem

We prove the following theorem: Let G be a graph with vertex-set V and ?, g be two integer-valued functions defined on V such that $\text{0}\text{?g(x) ?1??(x)}$ for all x ∈ V. Then G contains a factor F such that $\text{g(x)?d}{}_{\mathrm{F}}\text{(x)??(x)}$ for all x ∈ V if and only if for every subset X of V, $\text{?(X)}$ is at least equal to the number of connected components C of G[V ? X] such that either C = {x} and g(x) = 1, or |C| is odd ?3 and $\text{g(x) = ?(x) =}\text{1}$ for all x ∈ C. Applications are given to certain combinatorial geometries associated with factors of graphs.     

Degree Sum Conditions for Cyclability in Bipartite Graphs

We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let d _G (v) be the degree of a vertex v in a graph G. For G[X, Y] and ${S \subseteq V(G),}$ we define ${\sigma_{1,1}(S):=\min\{d_G(x)+d_G(y) : (x,y) \in (X \cap S,Y) \cup (X, Y \cap S), xy \not\in E(G)\}}$ . Amar et al. (Opusc. Math. 29:345–364, 2009) obtained σ _1,1(S) condition for cyclability of balanced bipartite graphs. In this paper, we generalize the result as it includes the case of unbalanced bipartite graphs: if G[X, Y] is a 2-connected bipartite graph with |X| ≥ |Y| and ${S \subseteq V(G)}$ such that σ _1,1(S) ≥ |X| + 1, then either there exists a cycle containing S or ${|S \cap X| > |Y|}$ and there exists a cycle containing Y. This degree sum condition is sharp.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

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}.     

Expanders obtained from affine transformations

A bipartite graphG=(U, V, E) is an (n, k, δ, α) expander if |U|=|V|=n, |E|≦kn, and for anyX⊆U with |X|≦αn, |Γ _G (X)|≧(1+δ(1−|X|/n)) |X|, whereΓ _G (X) is the set of nodes inV connected to nodes inX with edges inE. We show, using relatively elementary analysis in linear algebra, that the problem of estimating the coefficientδ of a bipartite graph is reduced to that of estimating the second largest eigenvalue of a matrix related to the graph. In particular, we consider the case where the bipartite graphs are defined from affine transformations, and obtain some general results on estimating the eigenvalues of the matrix by using the discrete Fourier transform. These results are then used to estimate the expanding coefficients of bipartite graphs obtained from two-dimensional affine transformations and those obtained from one-dimensional ones.     

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.     

Bounds on a graph's security number

Let G=(V,E) be a graph. A set S⊆V is a defensive alliance if |N[x]∩S|?|N[x]-S| for every x∈S. Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attack by its neighbors outside of S. An entire set S is secure if any subset X⊆S, not just singletons, can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. The security number s(G) of G is the cardinality of a smallest secure set. Bounds on s(G) are presented.     

Super cyclically edge-connected vertex-transitive graphs of girth at least 5

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super-λc, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In [Zhang, Z., Wang, B.: Super cyclically edge-connected transitive graphs. J. Combin. Optim., 22, 549-562 (2011)], it is proved that a connected vertex-transitive graph is super-λc if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper-λc graphs which have degree 4 and girth 5. In this paper, a characterization of k (k≥4)-regular vertex-transitive nonsuper-λc graphs of girth 5 is given. Using this, we classify all k (k≥4)-regular nonsuper-λc Cayley graphs of girth 5, and construct the first infinite family of nonsuper-λc vertex-transitive non-Cayley graphs.     

A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees

Let G be a connected simple graph, let X?V (^G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyárfás, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d _T (x) for all x ∈ X, where d _T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d _T (x) ≥ f(x) for all x ∈ X if and only if for any nonempty subset S ? X, |N _G (S) ? S| ? f(S) + 2|S| ? ω _G (S) ≥, where ω _G (S) is the number of components of the subgraph induced by S.     

The chromatic polynomial of an unlabeled graph

We investigate the chromatic polynomial χ(G, λ) of an unlabeled graph G. It is shown that $\text{χ(G, λ) = (}\text{1}\text{|A(g)|}\text{) Σ}{}_{\mathrm{\pi \; \in \; A(g)}}\text{χ(g, π, λ)}$, where g is any labeled version of G, A(g) is the automorphism group of g and χ(g, π, λ) is the chromatic polynomial for colorings of g fixed by π. The above expression shows that χ(G, λ) is a rational polynomial of degree n = |V(G)| with leading coefficient $\text{1}\text{|A(g)|}$. Though χ(G, λ) does not satisfy chromatic reduction, each polynomial χ(g, π, λ) does, thus yielding a simple method for computing χ(G, λ). We also show that the number N(G) of acyclic orientations of G is related to the argument λ = ?1 by the formula $\text{N(G) = (}\text{1}\text{|A(g)|}\text{) Σ}{}_{\mathrm{\pi \; \in \; A(g)}}\text{(?1)}{}^{\mathrm{s(\pi )}}\text{χ(g, π, ?1)}$, where s(π) is the number of cycles of π. This information is used to derive Robinson's (“Combinatorial Mathematics V” (Proc. 5th Austral. Conf. 1976), Lecture Notes in Math. Vol. 622, pp. 28–43, Springer-Verlag, New York/Berlin, 1977) cycle index sum equations for counting unlabeled acyclic digraphs.     

The security number of lexicographic products

A subset S of vertices of a graph G is a secure set if |N [X] ∩ S| ≥ |N [X] ? S| holds for any subset X of S, where N [X] denotes the closed neighborhood of X. The minimum cardinality s(G) of a secure set in G is called the security number of G. We investigate the security number of lexicographic product graphs by defining a new concept of tightly-securable graphs. In particular we derive several exact results for different families of graphs which yield some general results.