A Sufficient Condition for Graphs to Be SuperK-Restricted Edge Connected

• Autorzy: Shiying Wang , Meiyu Wang , Lei Zhang
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph; neighborhood; k-restricted edge connectivity; super k-restricted edge connected graph

Kategorie tematyczne

• 05C40: Connectivity

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 3
• Strony: 537-545

Daty

wydano

2017-08-01

otrzymano

2015-08-13

poprawiono

2016-05-11

zaakceptowano

2016-05-11

online

2017-07-06

Twórcy

autor

Shiying Wang

• , , , , Henan , P.R.

autor

Meiyu Wang

• , , , Shanxi , P.R.

autor

Lei Zhang

• , , , Shanxi , P.R.

Identyfikatory

DOI

10.7151/dmgt.1939