Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: generalized connectivity

Sortuj według:

Ogranicz wyniki do:

On the Maximum and Minimum Sizes of a Graph with Givenk-Connectivity

100%

Sun Y.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 3

623-632

The concept of k-connectivity κk(G), introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. For an integer k ≥ 2, the k-connectivity of a connected graph G with order n ≥ k is the smallest number of vertices whose removal from G produces a graph with at least k components or a graph with fewer than k vertices. In this paper, we get a sharp upper bound for the size of G with κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3; moreover, the unique extremal graph is given. Based on this result, we get the exact values for the maximum size, denoted by g(n, k, t), of a connected graph G with order n and κk(G) = t. We also compute the exact values and bounds for another parameter f(n, k, t) which is defined as the minimum size of a connected graph G with order n and κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3.

A Sharp Lower Bound For The Generalized 3-Edge-Connectivity Of Strong Product Graphs

100%

Sun Y.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 4

975-988

The generalized k-connectivity κk(G) of a graph G, mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λk(G) = min{λG(S) | S ⊆ V (G) and |S| = k}, where λG(S) denote the maximum number ℓ of pairwise edge-disjoint trees T1, T2, . . . , Tℓ in G such that S ⊆ V (Ti) for 1 ≤ i ≤ ℓ. In this paper we get a sharp lower bound for the generalized 3-edge-connectivity of the strong product of any two connected graphs.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Sun Y.

2 2017

Wyniki wyszukiwania

On the Maximum and Minimum Sizes of a Graph with Givenk-Connectivity

A Sharp Lower Bound For The Generalized 3-Edge-Connectivity Of Strong Product Graphs