Zadania z dominowania, zestaw nr 1.

1. Wiadomo, że jeśli G jest grafem spójnym rzędu n z δ( G) ­ 3 , to γ( G) ¬ 3 n . Znajdź

8

nieskończoną rodzinę grafów, które osiągają to górne ograniczenie.

2. Znajdź graf G rzędu n = 10 o m = 24 krawędziach, dla którego γ( G) = 4 .

3. Znajdź graf G, dla którego γ( G) = 4 oraz γ( G) < δ( G) .

4. Jaka jest największa liczba krawędzi w grafie G rzędu n = 10 z γ( G) = 3?

5. Udowodnij, że dla każdego grafu G bez wierzchołków izolowanych jest γ( G) ¬

n+2 −δ( G) .

2

6. Znajdź rodzinę grafów o średnicy równej dwa i dowolnie dużej liczbie dominowania.

7. Znajdź graf G rzędu siedem o dziesięciu krawędziach taki, że γ( G) = 3 , ∆( G) = 3 .

8. Znajdź graf kubiczny G (tzn. każdy wierzchołek ma stopień trzy) taki, że γ( G) = 3 n .

8