z-logo
open-access-imgOpen Access
A sufficient condition for graphs to be super k-restricted edge connected
Author(s) -
Meiyu Wang,
Shiying Wang,
Lei Zhang
Publication year - 2016
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1939
Subject(s) - mathematics , combinatorics , enhanced data rates for gsm evolution , discrete mathematics , computer science , artificial intelligence
For a subset S of edges in a connected graph G, S is 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 defined as the cardinality of a minimum k-restricted edge cut. Let ξk(G) = min{|[X, X̄]| : |X| = k, G[X] is connected}, where X̄ = V (G)\X. A graph G is super k-restricted edge connected if every minimum k-restricted edge cut of G isolates a component of order exactly k. Let k be a positive integer and let G be a graph of order ν ≥ 2k. In this paper, we show that if |N(u) ∩ N(v)| ≥ k +1 for all pairs u, v of nonadjacent vertices and ξk(G)≤⌊ν2⌋+k$\xi _k (G) \le \left\lfloor {{\nu \over 2}} \right\rfloor + k$, then G is super k-restricted edge connected

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom