For a graph G of order n GE 2, define the kappa-connectivity kappa kappa (G) of

Question

For a graph G of order n GE 2, define the kappa-connectivity kappa kappa (G) of G (2 LE kappa LE n) as the minimum number of vertices whose removal from G results in a graph with at least kappa components or a graph of order less than kappa. (Therefore, kappa2 (G) = kappa(G).) A graph G is defined to be (l, kappa)-connected if kappa kappa(G) Le l Let G be a graph of order n containing a set of at least k pairwise nonadjacent vertices. Show that if for every nu V(G), then G is (l, kappa)-connected.

Explanation / Answer

Solution :

The connectivity or k- connectivity (G) (where G is not a complete graph) is the size of a minimal vertex cut. A graph is called k-connected or k-vertex-connected if its vertex connectivity is k or greater.

To show :

Let k = degG(v).

Fix an ordering v1, . . . , vn of V (G) such that each vi has at most k neighbours among v1, . . . , vi1. Use the greedy colouring on G with respect to this vertex ordering. This colouring uses at most k colours, because when one colours vi there are at most k colours which cannot be used.

Therefore, (l,k) - connected and the degree of graph is greater than and equal to [(n + (k - 1)(l - 2)) / k].

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.