KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem A. 508. (April 2010)

A. 508. An induced subgraph \(\displaystyle S\) of the graph \(\displaystyle G\) is called ``dominant'' if every vertex of \(\displaystyle G\), outside \(\displaystyle S\), has a neighbor in \(\displaystyle S\). Does there exist such a graph which has an even number of dominant subgraphs?

Proposed by: László Miklós Lovász, Budapest

(5 pont)

Deadline expired on 10 May 2010.


Sorry, the solution is available only in Hungarian. Google translation

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 H\subsetV 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 H1 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 H2\subsetV akkor és csak akkor lesz H-val összekötve, ha H1-nek részhalmaza. Mivel az üres halmaz nincs a csúcsok között, ha H1-ben k pont van, akkor H-nak 2k-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.


Statistics:

6 students sent a solution.
5 points:Backhausz Tibor, Bodor Bertalan, Nagy 235 János, Nagy 648 Donát.
1 point:2 students.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley