Question

(a) Classify all simple graphs G on n vertices such that γ(G)-1. [1] (b) Classify all simple graphs G on n vertices such that β(G)-1. [1] (c) For positive integers m and n, with m2 n, find, in terms of m and n, the values of γ(G) and β(G) when G is the complete bipartite 2 0 graph Kmn

Answer 1

A graph G has domination number 1 iff some vertex neighbours all others i.e, G similar K_1, m beta(G) = 1 iff G is a non trivial star plus G has all isolated vertices g. G = The vertex cover number is 1 iff one vertex is incident to all edges. Dominating set of k_m, n m greaterthanorequalton contains m vertices as dominating set is largest independent set in k_m.n we have only two such sets one containing m elements other containing n vertices and m greaterthanorequalton therefore gamma(k_m, n) = m beta(G) = 1 iff G is a non trivia star plus G has all isolated vertices the vertex cover number is 1 iff are vertex is incident to all edges dominating set of k_m, n contains m vertices as dominating set is largest independent set are adjacent in k_m, n we have only two such sets one containing m elements other containing n vertices and m greaterthanorequalton therefore gamma (k_m, n) = m beta(k_m, n) = min{m, n} = n minimum vertex cover s has all those vertices such all edges of graph are incident to atleast one vertex in 5 g have atleast on endpoint in s) since th graph in consideration is k_m, n minimum vertex cover has min{m, n} = n vertices.