Sufficient conditions for triangle-free graphs to be super k-restricted edge-connected

Sufficient conditions for triangle-free graphs to be super k-restricted edge-connected

0.00 Avg rating0 Votes
Article ID: iaor201530345
Volume: 116
Issue: 2
Start Page Number: 163
End Page Number: 167
Publication Date: Feb 2016
Journal: Information Processing Letters
Authors: ,
Keywords: graphs, heuristics
Abstract:

An edge cut S of a connected graph G = ( V , E ) equ1 is a k‐restricted edge cut if every component of G S equ2 contains at least k vertices. A graph is said to be super k‐restricted edge‐connected if every minimum k‐restricted edge cut is a set of edges incident to a certain connected subgraph of order k. Let k be a positive integer, and let G be a connected triangle‐free graph of order n 2 k equ3. In this paper, we prove that if the minimum degree δ ( G ) k + 1 ( 1 ) k equ4 and there are at least k + 1 + ( 1 ) k 2 equ5 common vertices in the neighbor sets of each pair of nonadjacent vertices in G, then G is super k‐restricted edge‐connected.

Reviews

Required fields are marked *. Your email address will not be published.