Az A. 508. feladat (2010. április)

A. 508. A \(\displaystyle G\) gráfnak egy \(\displaystyle S\) feszített részgráfját ,,dominánsnak'' nevezzük, ha \(\displaystyle G\) minden \(\displaystyle S\)-en kívüli csúcsának van szomszédja \(\displaystyle S\)-ben. Létezik-e olyan gráf, aminek páros számú számú domináns részgráfja van?

Javasolta: Lovász László Miklós (Budapest)

(5 pont)

A beküldési határidő 2010. május 10-én LEJÁRT.

Megoldásvázlat. Legyen a gráf G=(V,E), és definiáljunk egy új gráfot. Az új gráf csúcsai legyenek V nemüres részhalmazai. Két részhalmazt akkor kössünk össze, ha diszjunktak, és nem megy él az egyik halmazból a másikba.

Nézzük, mennyi lehet egy HV részhalmaznak a foka az új gráfban. Ha egy H domináns, akkor minden P pont vagy benne van H-ban, vagy megy él P-ből H-ba. Ez azt jelenti, hogy ha V egy nemüres részhalmaza diszjunkt H-tól, akkor megy belőle él H-ba, tehát semmiképpen sincs összekötve H-val az új gráfban, vagyis egy domináns részhalmaz foka nulla.

Most tegyük fel, hogy H nem domináns. Álljon H₁ azokból a pontokból, amelyek nincsenek H-ban, és nem is megy belőlük él H-ba. Ez tehát nem üres. Egy H₂V akkor és csak akkor lesz H-val összekötve, ha H₁-nek részhalmaza. Mivel az üres halmaz nincs a csúcsok között, ha H₁-ben k pont van, akkor H-nak 2^k-1 szomszédja van, ami páratlan, mivel k>0.

Tehát pontosan a nem domináns részhalmazoknak páratlan a foka az új gráfban, így páros sok van belőlük. Az üres halmaz nyilvan sosem domináns, így összesen páratlan sok nemdomináns halmaz van, de összesen páros sok részhalmaz van, tehát páratlan sok domináns részhalmaz van.

Statisztika:

6 dolgozat érkezett.
5 pontot kapott:	Backhausz Tibor, Bodor Bertalan, Nagy 235 János, Nagy 648 Donát.
1 pontot kapott:	2 versenyző.

A KöMaL 2010. áprilisi matematika feladatai