Given an undirected graph find the following kvalues in this

Given an undirected graph, find the following k-values in this reachability problem.

Find a k-clique with the largest possible value of Find a k-club with the largest possible value of k Find a k-core with the largest possible value of k Find a k-plex with the largest possible value of k

Solution

Solution:

C)k-core with largest possible value of k

[4]->1->2->3->5->6

[3]->1->2->4->5->6

D) k-plex with largest possible value of k

=> {1, 5} is not a dominating set, but with any other vertex, say 6, the resulting set {1, 5, 6} is a dominating set, and so is any other triplet of vertices. The paper by Seidman and Foster also establishes some of the basic graph theoretic properties of a k-plex that are stated here.

  Illustration of k-plexes for k = 1, 2, 3