Restricted edge connectivity of graphs on degree

Abstract

Let G = (V, E) be a connected graph. An edge set S ⊂ E is a 3-restricted edge cut, if G - S is disconnected and every component of G - S has at least three vertices. The 3-restricted edge connectivity λ₃ (G) of G is the cardinality of a minimum restricted edge cut of G. A graph G is λ₃-connected, if 3-restricted edge cuts exist. A graph G is called λ′-optimal, if λ₃ (G) = ξ₃ (G), where $ξ_{3} (G) = min {| [X, \bar{X}] | : X \subset V, | X | = 3, G [X]$ is connected}. Furthermore, if every minimum 3-restricted edge cut is a set of edges incident to a set of three vertices, then G is said to be super 3-restricted edge connected or super-λ₃ for simplicity. Inverse degree of G is $R (G) = \sum_{v \in V} \frac{1}{d (v)}$ , where d (v) denotes the degree of the vertex v. In this paper, we study the relation of inverse degree and super 3-restricted edge connected graphs.

Keywords

networks cut

1 Introduction

A network is often modeled by a graph G = (V, E) with the vertices representing nodes such as processors or stations, and the edges representing links between the nodes [1 –3]. One fundamental consideration in the design of networks is reliability. An edge cut of a connected graph G is a set of edges whose removal disconnects G. The edge connectivity λ (G) of G is the minimum cardinality of an edge cut S of G. The edge connectivity λ (G) is an important feature determining reliability and fault-tolerance of the network. In the definitions of λ (G), no restrictions are imposed on the components of G - S. To compensate for this shortcoming, it would seem natural to generalize the notion of the classical connectivity by imposing some conditions or restrictions on the components of G - S.

Following this idea, k-restricted edge connectivity were proposed in [4]. An edge set S ⊂ E is said to be a k-restricted edge cut, if G - S is disconnected and every component of G - S has at least k vertices. The k-restricted edge connectivity of G, denoted by λ_k (G), is the cardinality of a minimum k-restricted-edge-cut of G. If S is a k-restricted edge cut and |S| = λ_k (G), then we call S a λ_k-cut. If there are k-restricted edge cuts in G, then G is λ_k-connected [5 –7].

Thus k-restricted edge connectivity is generalization of the classical edge connectivity and can provide more accurate measures for the reliability and the fault-tolerance of a large-scale parallel processing system, and so has received much attention in recent years (see the survey [8]). We will discuss the 3-restricted edge connectivity of graphs.

Let G = (V, E) be a connected graph, d_G (v) the degree of a vertex v in G (simply d (v)), and δ (G) the minimum degree of G. Moreover, for S ⊂ V, G [S] is the subgraph induced by S, and G - S denotes the subgraph of G induced by the vertex set of V - S. The girth of G is the shortest circle of G. For X, Y ⊂ V, denote by [X, Y] the set of edges with one end in X and the other in Y. Let the vertex subset U ⊆ V and $\bar{U} = V ∖ U$ be the complement of U. Set $\begin{matrix} ξ_{3} (G) & = & \min {| [U, \bar{U}] | : U \subset V, | U | = 3 and \\ G [U] is connected} . \end{matrix}$

For 3-restricted edge connectivity of graphs, there is an important result.

Theorem A. [9] IfGis aλ₃-connected graph, thenλ₃ (G) ≤ ξ₃ (G).

Then G is called λ₃-optimal, if λ₃ (G) = ξ₃ (G). If every minimum 3-restricted edge cut is a set of edges incident to a set of three vertices, then G is said to be super 3-restricted edge connected or super-λ₃ for simplicity.

If G is a graph with girth g ≥ 4, then a connected subgraph of G with three vertices is a path P = xyz of length two. Thus, ξ₃ (G)= min{d (x) + d (y) + d (z) -4 : xyz is a path of length two in G}.

Define the inverse degree of a graph G with no isolated vertices as $R (G) = \sum_{v \in V} \frac{1}{d (v)} .$ The inverse degree first attracted attention through conjectures of the computer program Graffiti [10]. It has been studied by several authors [11, 12]. In this paper, we show that, let G be a λ₃-connected graph of order n and girth g ≥ 6, δ ≥ 2. If $\begin{matrix} R (G) & \leq & 2 + \frac{1}{δ} - \frac{ξ_{3}}{(3 δ - 4) (3 δ - 5)} \\ + \frac{n - 3 δ - ξ + 4}{(n - 2 δ + 1) (n - 2 δ + 2)}, \end{matrix}$ then G is super-λ₃.

For graph-theoretical terminology and notation not defined here we follow [13]. All graphs considered in this paper are simple, finite and undirected.

2 Super-λ₃ and inverse degree

We start the section with the following useful lemmas.

Lemma 1.LetGbe aλ₃-connected graph with girthg ≥ 6, δ ≥ 2. IfGis not super-λ₃, then there exists aλ₃-cut [X, Y] with two disjoint setsX, Y ⊂ V (G), X ∪ Y = V (G) and | [X, Y] | = λ₃such that |X|, |Y| ≥ ξ₃.

Proof. By the hypothesis |X|, |Y|≥4. Let X₁ ⊆ X be the set of vertices, in which each vertex is incident with at least one edge of [X, Y], and X₀ = X - X₁. We will discuss it in two cases.

Case 1.X₀ =Ø.

Hence each vertex of X is incident with at least one edge of [X, Y]. Notice that girth g ≥ 6. Take a path xyz in G [X], we have $\begin{matrix} ξ_{3} (G) \leq d (x) + d (y) + d (z) - 4 \\ = | N (x) | + | N (y) | + | N (z) | - 4 \\ = | (N (x) \cap X) ∖ {y} | + | N (x) \cap Y | \\ + | (N (y) \cap X) ∖ {x, z} | \\ + | N (y) \cap Y | + | (N (z) \cap X) ∖ {y} | \\ + | N (z) \cap Y | \\ \leq | [{x, y, z}, Y] | + | [X ∖ {x, y, z}, Y] | \\ = | [X, Y] | = λ_{3} (G) . \end{matrix}$

We get that λ₃ (G) = ξ₃ (G). That is |N (x) ∩ Y| + |N (y) ∩ Y| + |N (z) ∩ Y| = | [{x, y, z}, Y] | and | (N (x) ∩ X) ∖ {y} | + | (N (y) ∩ X) ∖ {x, z} | + | (N (z) ∩ X) ∖ {y} | = | [X ∖ {x, y, z}, Y] |. And each vertex of ((N (x) ∩ X) ∖ {y}) ∪ ((N (y) ∩ X) ∖ {x, z}) ∪ ((N (z) ∩ X) ∖ {y}) has only one neighbor in Y. Take z′ ∈ (N (x) ∩ X) ∖ {y} and the path yxz′. Applying the above method to yxz′, we can get y has only one neighbor in Y. Similarly, x and z has only one neighbor in Y. Hence |X| ≥ d (x) + d (y) + d (z) -4 ≥ ξ₃ (G).

Case 2.X₀≠ Ø.

Subcase 2.1. G [X₀] is an independent set. Let x ∈ X₀, y, z ∈ X₁ and xyz be a path in G [X], then N (x) ⊆ X₁. We can get $\begin{matrix} ξ_{3} (G) \leq d (x) + d (y) + d (z) - 4 \\ = | N (x) | + | N (y) | + | N (z) | - 4 \\ = | (N (x) \cap X) ∖ {y} | + | (N (y) \cap X) ∖ {x, z} | \\ + | N (y) \cap Y | + | (N (z) \cap X) ∖ {y} | + | N (z) \cap Y | \\ = | (N (x) \cap X) ∖ {y} | + | N (y) \cap X_{1} ∖ {x} | \\ + | (N (y) \cap X_{0}) ∖ {x} | + | N (y) \cap Y | \\ + | N (z) \cap X_{1} ∖ {y} | + | N (z) \cap X_{0} | + | N (z) \cap Y | \\ \leq | (N (x) \cap X) ∖ {y} | + | N (y) \cap X_{1} | \\ + \sum_{u \in (N (y) \cap X_{0}) ∖ {x}} | N (u) \cap X_{1} | \\ + | N (y) \cap Y | + | N (z) \cap X_{1} ∖ {y} | \\ + \sum_{u \in (N (z) \cap X_{0})} | N (u) \cap X_{1} | + | N (z) \cap Y | \\ \leq | [{x, y, z}, Y] | + | [X ∖ {x, y, z}, Y] \\ = | [X, Y] | = λ_{3} (G) . \end{matrix}$

That is $\begin{matrix} | (N (x) \cap X) ∖ {y} | + | N (y) \cap X_{1} ∖ {z} | \\ + \sum_{u \in (N (y) \cap X_{0}) ∖ {x}} | N (u) \cap X_{1} | + | N (z) \cap X_{1} ∖ {y} | \\ + \sum_{u \in (N (z) \cap X_{0})} | N (u) \cap X_{1} | = | [X ∖ {x, y}, Y] | \end{matrix}$ and $\begin{matrix} | N (y) \cap X_{0} ∖ {x} | = \sum_{u \in (N (y) \cap X_{0}) ∖ {x}} | N (u) \cap X_{1} | \\ | N (z) \cap X_{0} | = \sum_{u \in (N (z) \cap X_{0})} | N (u) \cap X_{1} | . \end{matrix}$

Each vertex in $\begin{matrix} ((N (x) \cap X) ∖ {y}) \cup (N (y) \cap X_{1} ∖ {z}) \\ \cup {N (u) \cap X_{1} | u \in (N (y) \cap X_{0}) ∖ {x}} \\ \cup (N (z) \cap X_{1} ∖ {y}) \cup {N (u) \cap X_{1} | u \\ \in (N (z) \cap X_{0})} \end{matrix}$ has only one neighbor in Y.

Since δ (G) ≥2, girth g ≥ 6, take y′ ∈ N (x) - xz′ ∈ (N (y′) ∩ X₁) ∖ {y}. Applying the above method to the path xy′z′, we can get y and z have only one neighbor in Y. Hence |X| ≥ d (x) + d (y) + d (z) -4 ≥ ξ₃ (G).

Subcase 2.2. G [X₀] has an edge e = xy. It is similar to the above case, we have |X| ≥ ξ₃ (G). Similarly, we can obtain |Y| ≥ ξ₃ (G).

Corollary 2.LetGbe aλ₃-connected graph of ordernwith girthg ≥ 6, δ ≥ 2. Ifn ≤ 2ξ (G) -1, thenGis super-λ₃.

We will introduce a very useful lemma as follows.

Lemma 3. [12]

Let a₁, a₂, ⋯, a_p, A be positive reals with $\sum_{i = 1}^{p} a_{i} \leq A$ . Then $\sum_{i = 1}^{p} (1 / a_{i}) \geq p^{2} / A$ .

If, in addition a₁, a₂, …, a_p, A are positive integers, and a, b are integers with A = ap + b and 0 ≤ b ≤ p, then $\sum_{i = 1}^{p} (1 / a_{i}) \geq (p - b) / a + b / (a + 1)$ . Equality holds if and only if p - b of the a_i equal a and the remaining a_i equal a + 1.

If f (x) is continuous and convex on an interval [L, R], and if l, r ∈ [L, R], with l + r = L + R, then f (L) + f (R) ≥ f (l) + f (r).

Theorem 4.LetGbe aλ₃-connected graph of ordernand girthg ≥ 6, δ ≥ 2. If $\begin{matrix} R (G) & \leq & 2 + \frac{1}{δ} - \frac{ξ_{3}}{(3 δ - 4) (3 δ - 5)} \\ + \frac{n - 3 δ - ξ + 4}{(n - 2 δ + 1) (n - 2 δ + 2)}, \end{matrix}$ then G is super-λ₃.

Proof. By Lemma 1, then there exist a λ₃-cut [X, Y] with two disjoint sets X, Y ⊂ V (G), X ∪ Y = V (G) and | [X, Y] | = λ₃ such that |X|, |Y| ≥ ξ₃ (G) ≥3δ - 4, that is 3δ - 4 ≤ |X|, |Y| ≤ n - 3δ + 4.

Hence we get ∑_y∈Yd (y) < |Y| (|Y|-1) + λ₃. By Lemma 3 (2), we have $\begin{matrix} \sum_{y \in Y} \frac{1}{d (y)} & > & \frac{| Y | - λ_{3}}{| Y | - 1} + \frac{λ_{3}}{| Y |} \\ = & 1 + \frac{1}{| Y | - 1} - \frac{λ_{3}}{| Y | (| Y | - 1)} . \end{matrix}$

Because G has a vertex v of degree δ. Without loss of generality, assume v ∈ X. Then $\sum_{x \in X - v} d (x) < (| X | - 1)^{2} + λ_{3} .$

According to Lemma 3 (2), we can obtain $\begin{matrix} \sum_{x \in X} \frac{1}{d (x)} & > & \frac{1}{δ} + \frac{| X | - 1 - λ_{3}}{| X | - 1} + \frac{λ_{3}}{| X |} \\ = & 1 + \frac{1}{δ} - \frac{λ_{3}}{| X | (| X | - 1)} . \end{matrix}$

Because of 1/(|Y|-1) ≥1/(n - 3δ + 3), we obtain $\begin{matrix} R (G) & > & 2 + \frac{1}{δ} + \frac{1}{n - 3 δ + 3} \\ - \frac{λ_{3}}{| Y | (| Y | - 1)} - \frac{λ_{3}}{| X | (| X | - 1)} . \end{matrix}$

We consider the function $g (t) = \frac{1}{t (t - 1)}$ . It is easy to verify that g″ (t) >0 for t > 0, so g is convex. By |X|, |Y|≥3δ - 4, |X| + |Y| = n and Lemma 3 (3) applied to the function g (t), we get $\begin{matrix} \frac{1}{| X | (| X | - 1)} + \frac{1}{| Y | (| Y | - 1)} \\ \leq \frac{1}{(3 δ - 4) (3 δ - 5)} + \frac{1}{(n - 3 δ + 4) (n - 3 δ + 3)} . \end{matrix}$

And in conjunction with λ₃ ≤ ξ₃, we have $\begin{matrix} R (G) > 2 + \frac{1}{δ} + \frac{1}{n - 3 δ + 3} - \frac{ξ_{3}}{(3 δ - 4) (3 δ - 5)} \\ - \frac{ξ_{3}}{(n - 3 δ + 4) (n - 3 δ + 3)} \\ = 2 + \frac{1}{δ} - \frac{ξ_{3}}{(3 δ - 4) (3 δ - 5)} \\ + \frac{n - 3 δ - ξ + 4}{(n - 2 δ + 1) (n - 2 δ + 2)} . \end{matrix}$

There is a contradiction.

References

Pongnu

and Pochai

, Numerical simulation of groundwater measurement using alternating direction methods, Journal of Interdisciplinary Mathematics20(2) (2017), 513–541.

Aladadi

W.M.

, Moustafa

M.F.

and Alruman

S.A.

, Genetic variability among seven cultivars of date palm (Phoenix dactylifera L.) based on embryonic DNA of old fruit, Kuwait Journal of Science45(1) (2018), 108–114.

Chen

, Zhao

and Su

, Raw material inventory optimization for MTO enterprises under price fluctuations, Journal of Discrete Mathematical Sciences and Cryptography20(1) (2017), 255–270.

Fábrega

and Fiol

M.A.

, On the extraconnectivity of graphs, Discrete Mathematics155 (1996), 49–57.

Gao

and Wang

W.F.

, The fifth geometric-arithmetic index of bridge graph and carbon nanocones, Journal of Difference Equations and Applications23(1-2SI) (2017), 100–109.

Lan

, Lan

, Chen

and Lo

, A study of investigating adolescents’ eating out behavior by using analytic hierarchy process, Eurasia Journal of Mathematics Science and Technology Education13(7) (2017), 3227–3234.

Peng

, Lin

, Wang

, Chang

, Gu

and Zhu

, Molecular characteristics of Illicium verum extractives to activate acquired immune response, Saudi Journal of Biological Sciences23(3) (2016), 348–352.

Hellwig

and Volkmann

, Maximally edge-connected and vertex-connected graphs and digraphs: A survey, Discrete Mathematics308 (2008), 3265–3296.

Bonsna

, Ueffing

and Volkmann

, Edge-cuts leaving components of order at least three, Discrete Math256 (2002), 431–439.

10.

Fajtlowicz

, On conjectures of Graffiti – III, Congressus Numerantium66 (1988), 23–32.

11.

Dankelmann

, Swart

H.C.

and Berg

, Diameter and inverse degree, Discrete Math308 (2008), 670–673.

12.

Dankelmann

, Hellwig

and Volkmann

, Inverse degree and edge-connectivity, Discrete Math309 (2009), 2943–2947.

13.

Bondy

J.A.

and Murty

U.S.R.

, Graph theory and its application, Academic Press, 1976.

Restricted edge connectivity of graphs on degree

Abstract

Keywords

1 Introduction

2 Super-λ3 and inverse degree

References

2 Super-λ₃ and inverse degree