Klepsydrą nazywamy graf \(\displaystyle{ G _{n} }\) powstały z dwóch kopii cyklu \(\displaystyle{ C _{n} }\), \(\displaystyle{ n \ge 4}\), poprzez
dodanie nowego wierzchołka i połączenie go ze wszystkimi wierzchołkami obu cykli.
a) Podaj rząd, rozmiar, stopień minimalny oraz maksymalny i średnicę grafu \(\displaystyle{ G _{n} }\).
b)Dla jakich \(\displaystyle{ n}\) graf \(\displaystyle{ G _{n} }\)jest dwudzielny?
c)Znajdź najliczniejsze skojarzenie, najmniej liczne pokrycie oraz najliczniejszy
zbiór niezależny w grafie \(\displaystyle{ G _{n} }\).
Podpunkt a) rozwiązałam proszę o sprawdzenie czy poprawnie:
rząd \(\displaystyle{ 2n+1}\)
rozmiar \(\displaystyle{ 2n}\)
stopień minimalny \(\displaystyle{ 3}\)
stopień maksymalny \(\displaystyle{ 2n}\)
średnica \(\displaystyle{ n}\) ,\(\displaystyle{ n \ge 4}\)
Natomiast nie wiem kiedy graf będzie dwudzielny w tym przypadku, znam definicję ( zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łączą wierzchołków tego samego zbioru) natomiast w naszym przypadku jeden punkt (srodek klepsydry) łączy wszystkie inne wierzchołki, a w cyklach wierzchołki tez są połączone te obok siebie . Nie wiem jak to rozwiązać.