Under which conditions is λ″(G)=κ″(L(G))?

Abstract

In this paper we show that if G is a connected graph such that $\left|G\right|\ge 2(\delta (G)+1)$, $\delta (G)\ge 2$ and $G\ncong G_{t,n}^{*}$ then ${\kappa }^{{}^{″}}(L(G))$ exists and ${\lambda }^{{}^{″}}(G)={\kappa }^{{}^{″}}(L(G))$ if and only if G is not super-${\lambda }^{{}^{″}}$. We also obtain some other results.

KEYWORDS:

• m-restricted edge-cut
• line graph
• super-${\lambda }^{(m)}$

2010 MATHEMATICS SUBJECT CLASSIFICATION:

• 05C40
• 05C90

1 Introduction

We follow [1, 14] for graph-theoretical terminology and notation not defined here. Throughout this paper, a graph $G=(V,E)$ always means a finite undirected graph without self-loops or multiple edges, where $V=V(G)$ is the vertex-set and $E=E(G)$ is the edge-set. For any two adjacent vertices u, v, use $u\sim v$ or $\{u,v\}$ to denote the edge incident with u and v. The edge-connectivity $\lambda (G)$ of G is an important measurement for fault-tolarance of the networks, and the larger $\kappa (G)$ or $\lambda (G)$ is, the more reliable the network is. It is well known that $\kappa (G)\le \lambda (G)\le \delta (G)$, where $\delta (G)$ is the minimum degree of G. As more refined indices than connectivity and edge-connectivity, super connectivity and super edge-connectivity were proposed in [2, 3]. An edge set F (vertex set $F_1$) of graph G is called an m -restricted edge-cut (m -restricted cut) if $G-F$ ($G-F_1$) is disconnected and each component of $G-F$ ($G-F_1$) contains at least m vertices. In literature some authors use the terminology super vertex cut instead of 2-restricted cut.

${\lambda }^{(m)}(G)$ (${\kappa }^{(m)}(G)$) is the minimum size of all m-restricted edge-cuts (m-restricted cuts) and ${\xi }_m(G)=\min \left\{\right|\omega (U)|:|U|=m\text{ and }G[U]\text{ is connected}\}$ where $\omega (U)$ is the set of edges with exactly one end vertex in U and G[U] is the subgraph of G induced by U. A graph G is ${\lambda }^{(m)}$-graph if ${\lambda }^{(m)}(G)={\xi }_m(G)$. An ${\lambda }^{(m)}$-graph is called super m-restricted edge-connected or simply super-${\lambda }^{(m)}$ if every minimum m-restricted edge cut isolates one component G[U] with $\left|U\right|=m$. By the definition of ${\lambda }^{(m)}(G)$, we can see that ${\lambda }^{(1)}(G)\le {\lambda }^{(2)}(G)\le {\lambda }^{(3)}(G)\le \cdots$ as long as these parameters exist. It is clear that $\lambda (G)={\lambda }^{(1)}(G)$. Also we denote ${\lambda }^{(2)}(G)$ by ${\lambda }^{{}^{\prime }}(G)$ and ${\lambda }^{(3)}(G)$ by ${\lambda }^{{}^{″}}(G)$ (for more information see [4–13, 16, 18]).

Let $G_1,G_2,\dots ,G_n$ be n copies of $K_t$. We add a new vertex u and let u be adjacent to every vertex in $V(G_i)$, $i=1,\dots ,n$. The resulting graph is denoted by $G_{n,t}^{*}$. It can be verified that $G_{n,t}^{*}$ has no $(\delta (G_{n,t}^{*})+1)$-restricted edge cuts. In [17] Zhang and Yuan showed that if G is a connected graph which is not isomorphic to $G_{n,t}^{*}$, where $t=\delta (G)$ and $\left|G\right|\ge 2(\delta (G)+1)$ then G has a k-restricted edge cut and ${\lambda }^{(k)}(G)\le {\xi }_m(G)$ for $k\le \delta (G)+1$.

Proposition 1.1.

[17, Theorem 1] Let G be a connected graph with order at least $2(\delta (G)+1)$ which is not isomorphic to any $G_{n,t}^{*}$ with $t=\delta (G)$. Then for any $k\le \delta (G)+1$, G has k-restricted edge cuts and ${\lambda }^{(k)}(G)\le {\xi }_m(G)$.

Let $G=(V,E)$ be a simple connected graph. The line graph of G, denoted by $L(G)$, or L shortly, is a graph with the vertex-set $V(L)=E(G)$, and a vertex xy is adjacent to a vertex wz in L if and only if they are adjacent as edges in G.

Proposition 1.2.

[15, Theorem 2] Suppose that G has order at least four and G is not a star. Then ${\lambda }^{{}^{\prime }}(G)={\kappa }^{{}^{\prime }}(L(G))$ if and only if G is not super-${\lambda }^{{}^{\prime }}$.

2 Main results

The complete bipartite graph $K_{1,3}$ is usually called a claw and a graph that does not contain an induced claw is called claw-free. It is easy to see that every line graph is claw-free. With the similar arguments in the proof of Lemma 5 in [15] we prove the following lemma.

Lemma 2.1.

Let G be a connected claw-free graph. Then $G-S$ contains exactly two components for any minimum m-restricted cut S of G, where $m\ge 2$.

Proof.

Suppose that S is a minimum m-restricted cut of G and $G_1,G_2,\dots ,G_r$ are the connected components of $G-S$. Thus $G_i$ contains at least $m\ge 2$ vertices, where $1\le i\le r$. Since S is a vertex-cut, there is a vertex $x\in S$ such that x is adjacent to every component, otherwise $S^{{}^{\prime }}=S-\left\{x\right\}$ is also a m-restricted cut, contradicting the minimality of S. If $r\ge 3$ the vertex x is adjacent to at least three components, which is impossible as G is a claw-free graph. Therefore, $r=2$ and the lemma holds. ▪

Lemma 2.2.

Suppose that G is a graph and $m\ge 1$. Then each of the following holds:

1. graph G is super-${\lambda }^{(m)}$ if and only if ${\lambda }^{(m+1)}(G)>{\lambda }^{(m)}(G)$,

2. graph G is super-${\kappa }^{(m)}$ if and only if ${\kappa }^{(m+1)}(G)>{\kappa }^{(m)}(G)$.

Proof.

1. First suppose that G is super-${\lambda }^{(m)}$. Thus each minimum m-restricted edge-cut isolates a component of order m. We know that ${\lambda }^{(m+1)}(G)\ge {\lambda }^{(m)}(G)$. Let ${\lambda }^{(m+1)}(G)={\lambda }^{(m)}(G)$ and F be a minimum $(m+1)$-restricted edge-cut. Thus $\left|F\right|={\lambda }^{(m+1)}(G)={\lambda }^{(m)}(G)$ and so F is minimum m-restricted edge-cut and isolate no component of order m, a contradiction. Now suppose that ${\lambda }^{(m+1)}(G)>{\lambda }^{(m)}(G)$. If G is not super-${\lambda }^{(m)}$ then G has a minimum m-restricted edge-cut, say F, such that each component of $G-F$ has order at least $m+1$. Thus ${\lambda }^{(m+1)}(G)\le {\lambda }^{(m)}(G)$, a contradiction.

2. Proof is similar to Case $(1)$. ▪

In the rest of the paper we assume that G is triangle-free graph and $\delta (G)\ge 2$. Thus it is easy to see that G is not isomorphic to $G_{n,t}^{*}$. Also for a subset $E^{{}^{\prime }}\subseteq E(G)$, we use $G[E^{{}^{\prime }}]$ to denote the edge-induced subgraph of G by $E^{{}^{\prime }}$.

Lemma 2.3.

Suppose that G is a graph and $L_1$ is a subgraph of $L(G)$, $V(L_1)=E_1$ and $G_1=G[E_1]$. If $L_1$ is a connected subgraph of $L(G)$ with order at least 3 then the subgraph $G_1$ is connected and $|V(G_1)|\ge 4$.

Proof.

Suppose that x and y are two distinct arbitrary vertices of $G_1$. We show that there is a path from x to y. If $xy\in E(G_1)$ then the assertion holds. Thus, we may suppose that x is not adjacent to y and so x is adjacent to another vertex, say z. Let $e=\{x,z\}$, where $z\in V(G_1)$ and $z\ne y$. Thus y is incident with another edge, say $e^{{}^{\prime }}$. Let $e^{{}^{\prime }}=\{w,y\}$. Now e and $e^{{}^{\prime }}$ are two edges in $G_1$ and so are two vertices in $L_1$. Since $L_1$ is connected it follows that there is a path, say P, between e and $e^{{}^{\prime }}$. Let $P=(xz,z{z}_1,z_1{z}_2,\dots ,z_{k}w,wy)$. Now the corresponding edges $xz,z{z}_1,z_1{z}_2,\dots ,z_{k}w,wy$ form a walk in $G_1$ from x to y. We conclude that $G_1$ is connected. Also since G is triangle-free graph, x is not adjacent to y, $|E(G_1)|=|V(L_1)|\ge 3$ and $x\ne y$ we see that $|V(G_1)|\ge 4$. ▪

Theorem 2.4.

Suppose that G is a connected graph of order at least $2(\delta (G)+1)$. Then ${\kappa }^{{}^{″}}(L(G))$ exists and ${\lambda }^{{}^{″}}(G)={\kappa }^{{}^{″}}(L(G))$ if and only if G is not super-${\lambda }^{{}^{″}}$.

Proof.

By our assumption $|V(G)|\ge 6$ and by Proposition 1.1 we see that ${\lambda }^{{}^{″}}(G)$ exists. First suppose that G is not super-${\lambda }^{{}^{″}}$. First we prove that ${\kappa }^{{}^{″}}(L(G))\ge {\lambda }^{{}^{″}}(G)$. Let S be a minimum 3-restricted cut of $L(G)$. We know that $L(G)$ is claw free and so by Lemma 2.1 $L(G)-S$ has exactly two components say, $L_1$ and $L_2$. Also by Lemma 2.3, $G_i=G[V(L_i)]$ is connected and $|V(G_i)|\ge 4$ $(1\le i\le 2)$, where $G[V(L_i)]$ is the edge-induced subgraph of G by $V(L_i)$. Thus S is an 3-restricted edge cut of G. By our assumption about S, we have ${\lambda }^{{}^{″}}(G)\le \left|S\right|={\kappa }^{{}^{″}}(L(G))$. Now in the following we show that ${\kappa }^{{}^{″}}(L(G))\le {\lambda }^{{}^{″}}(G)$. We know that G is not super-${\lambda }^{{}^{″}}$. Thus there exists a minimum 3-restricted edge-cut, say F, such that no component of $G-F$ has order 3. By our assumption we see that all components of $G-F$ have order at least 4. $L(G)-F$ has at least two components. Suppose that C is an arbitrary component of $G-F$. Now $L(C)$ is connected and $|V(L(C))|=|E(C)|\ge 3$. On the other hand, since F is an 3-restricted edge-cut in G then $L(C)$ is a component of $L(G)$ and F is a 3-restricted cut for $L(G)$. Thus ${\kappa }^{{}^{″}}(L(G))$ exists and ${\kappa }^{{}^{″}}(L(G))\le \left|F\right|={\lambda }^{{}^{″}}(G)$.

Now suppose that ${\kappa }^{{}^{″}}(L(G))$ exists and ${\kappa }^{{}^{″}}(L(G))={\lambda }^{{}^{″}}(G)$. We show that G is not super-${\lambda }^{{}^{″}}$. Suppose to contrary that G is super-${\lambda }^{{}^{″}}$. Then each minimum 3-restricted edge-cut has an exactly one component of order 3. By considering ${\kappa }^{{}^{″}}(L(G))$, there exists a 3-restricted cut S of $L(G)$ such that each component of $L(G)-S$ has order at least 3 and $\left|S\right|={\kappa }^{{}^{″}}(L(G))$. Thus (*) $$\left|S\right|={\kappa }^{{}^{″}}(L(G))={\lambda }^{{}^{″}}(G)$$(*)

We know that $L(G)$ is claw free and so by Lemma 2.1, $L(G)-S$ has exactly two components, say $L_1$ and $L_2$. By Lemma 2.3, $|V(G_i)|\ge 4$ where $G_i=G[V(L_i)]$ and $1\le i\le 2$. Since there is no path between $L_1$ and $L_2$ it follows that there is no path between $G_1$ and $G_2$. Thus S is an 3-restricted edge cut of G and by $(*)$ S is a minimum 3-restricted edge cut of G such that $G-S$ has not component of order three, a contradiction. ▪

Theorem 2.5.

Suppose that G is a connected graph of order at least $2(\delta (G)+1)$. Then ${\lambda }^{{}^{\prime }}(G)={\kappa }^{{}^{″}}(L(G))$ if and only if G is not super-${\lambda }^{{}^{\prime }}$.

Proof.

By our assumption we see that G has at least 6 vertices, ${\lambda }^{{}^{″}}(G)$ exists and G is not star. First suppose that G is not super-${\lambda }^{{}^{\prime }}$. By Proposition 1.2, we see that ${\kappa }^{{}^{\prime }}(L(G))$ exists and ${\lambda }^{{}^{\prime }}(G)={\kappa }^{{}^{\prime }}(L(G))$. Also since G is not super-${\lambda }^{{}^{\prime }}$ it follows that there is a minimum 2-restricted edge-cut, say F, such that $G-F$ has no component of order 2 and ${\lambda }^{{}^{″}}(G)=\left|F\right|$. By Lemma 2.2, ${\lambda }^{{}^{\prime }}(G)={\lambda }^{{}^{″}}(G)$. Also by Theorem 2.4, ${\kappa }^{{}^{″}}(L(G))$ exists and ${\lambda }^{{}^{″}}(G)={\kappa }^{{}^{″}}(L(G))$. Now by considering ${\lambda }^{{}^{\prime }}(G)={\kappa }^{{}^{\prime }}(L(G))$ and ${\lambda }^{{}^{\prime }}(G)={\lambda }^{{}^{″}}(G)=\left|F\right|$ we see that ${\kappa }^{{}^{″}}(L(G))={\lambda }^{{}^{″}}(G)={\lambda }^{{}^{\prime }}(G)={\kappa }^{{}^{\prime }}(L(G))$ and so ${\kappa }^{{}^{″}}(L(G))={\lambda }^{{}^{\prime }}(G)$.

Conversely, suppose that ${\lambda }^{{}^{\prime }}(G)={\kappa }^{{}^{″}}(L(G))$. Assume that G is super-${\lambda }^{{}^{\prime }}$. Thus each minimum 2-restricted edge cut isolates an edge. Let S be minimum 3-restricted cut of $L(G)$ such that $\left|S\right|={\kappa }^{{}^{″}}(L(G))={\lambda }^{{}^{\prime }}(G)$. Clearly each component of $L(G)-S$ has order at least three. We know that $L(G)$ is claw-free and so by Lemma 2.1, $L(G)-S$ has exactly two components, say $L_1$ and $L_2$. Also by Lemma 2.3, $G_i=G[V(L_i)]$ is connected and $|V(G_i)|\ge 4$ $(1\le i\le 2)$. Thus S is an 2-restricted edge cut for G. Also since $\left|S\right|={\kappa }^{{}^{″}}(L(G))={\lambda }^{{}^{\prime }}(G)$ we see that S is the minimum 2-restricted edge cut of G. But $G-S$ contains no component of order 2, a contradiction. ▪

Theorem 2.6.

Suppose that G is a connected graph of order at least $2(\delta (G)+1)$. Then $L(G)$ is super-${\kappa }^{{}^{\prime }}$ if and only if G is super-${\lambda }^{{}^{″}}$.

Proof.

First suppose that $L(G)$ is super-${\kappa }^{{}^{\prime }}$. Suppose to contrary that G is not super-${\lambda }^{{}^{″}}$. Then by Lemma 2.2, and Theorem 2.5, we have ${\lambda }^{{}^{″}}(G)={\lambda }^{{}^{\prime }}(G)$ and ${\lambda }^{{}^{\prime }}(G)={\kappa }^{{}^{″}}(L(G))$. Also since $L(G)$ is super-${\kappa }^{{}^{\prime }}$, again by Lemma 2.2, we have ${\kappa }^{{}^{″}}(L(G))>{\kappa }^{{}^{\prime }}(L(G))$. Moreover, since $L(G)$ is super-${\kappa }^{{}^{\prime }}$, it follows that every minimum 2-restricted cut isolate a component of order 2. Let S be a minimum 2-restricted cut and ${\kappa }^{{}^{\prime }}(L(G))=\left|S\right|$. Knowing that $L(G)$ is claw-free, by Lemma 2.1, $L(G)-S$ has exactly two components, say $L_1$ and $L_2$. Also by Lemma 2.3, $G_i=G[V(L_i)]$ is connected and $|V(G_i)|\ge 4$ $(1\le i\le 2)$. Thus S is 3-restricted edge cut of G and so ${\lambda }^{{}^{″}}(G)\le \left|S\right|$. Therefore $$\left|S\right|={\kappa }^{{}^{\prime }}(L(G))<{\kappa }^{{}^{″}}(L(G))={\lambda }^{{}^{\prime }}(G)={\lambda }^{{}^{″}}(G)\le \left|S\right|.$$

Thus ${\kappa }^{{}^{″}}(L(G))={\kappa }^{{}^{\prime }}(L(G))$, a contradiction.

Conversely, suppose that G is super-$$. If $L(G)$ is not super-${\kappa }^{{}^{\prime }}$ then there exists a minimum 2-restricted cut of $L(G)$, say S, such that each component of $L(G)-S$ has order at least three. Knowing that $L(G)$ is claw-free, by Lemma 2.1, $L(G)-S$ has exactly two components, say $L_1$ and $L_2$. Also by Lemma 2.3, $G_i=G[V(L_i)]$ is connected and $|V(G_i)|\ge 4$ $(1\le i\le 2)$. Thus S is 3-restricted edge cut of G such that each component of $G-S$ has order at least four. If S is minimum 3-restricted edge cut then by our assumption $G-S$ should have a component of order three, a contradiction. Also if S is not minimum 3-restricted edge cut then there exists a minimum 3-restricted edge cut of G, say F, such that $\left|F\right|<\left|S\right|$. Clearly, F is a 2-restricted cut of $L(G)$ and this contradicts the minimality of S. ▪

Corollary 2.7.

Suppose that G is a connected graph of order at least $2(\delta (G)+1)$. If G is not super-${\lambda }^{{}^{″}}$, then ${\kappa }^{{}^{\prime }}(L(G))={\lambda }^{{}^{″}}(G)$.

Proof.

Since G is not super-${\lambda }^{{}^{″}}$, ${\kappa }^{{}^{″}}(L(G))$ exists and ${\lambda }^{{}^{″}}(G)={\kappa }^{{}^{″}}(L(G))$ by Theorem 2.4. Also, by Theorem 2.6, $L(G)$ is not super-${\kappa }^{{}^{\prime }}$. Now by Lemma 2.2, ${\kappa }^{{}^{\prime }}(L(G))={\kappa }^{{}^{″}}(L(G))$ and so ${\kappa }^{{}^{\prime }}(L(G))={\lambda }^{{}^{″}}(G)$. ▪