Problem B. 4052. (January 2008)

B. 4052. A path P₁,P₂,...,P_k in a simple graph is said to be a fan if the degree of every point P_i is i. What is the maximum number of points that a fan may have in a simple graph on n points?

Suggested by G. Mészáros

(4 pont)

Deadline expired on February 15, 2008.

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

Megoldás: Jelölje a kérdéses számot f(n). Könnyen ellenőrizhető, hogy f(1)=0, f(2)=1, f(3)=f(4)=2 és f(5)=3. Tegyük fel, hogy a gráfban van egy P₁,P₂,...,P_k ugróiskola, ahol k $\ge$ 4. P_k az út csúcsai közül P₁-gyel, P₂-vel és saját magával nem lehet összekötve, vagyis a gráfnak kell legyen még legalább 3 további csúcsa. Ez azt mutatja, hogy n $\ge$ 6 esetén f(n) $\le$ n-3. A továbbiakban megmutatjuk, hogy n $\ge$ 6 esetén f(n) $\ge$ n-3 is fennáll, vagyis k $\ge$ 3 esetén van olyan k+3 szögpontú egyszerű G_k gráf, amely tartalmaz k csúcsú ugróiskolát.

Vegyünk fel ehhez egy $P_1P_2\ldots P_k$ utat, és 3 $\le$ i,j $\le$ k, i $\ne$ j, k+3 $\le$ i+j esetén kössük össze a P_i és a P_j csúcsokat (amennyiben eddig még nem voltak összekötve) egy éllel. Az így kapott H_k egyszerű gráfban jelölje d(i) a P_i csúcs fokát. Nyilván d(1)=1 és d(2)=2. Ha i $\ge$ 3, akkor k+3-i $\le$ j $\le$ k, i $\ne$ j esetén P_i össze van kötve P_j-vel, vagyis d(i) $\ge$ (i-2)-1=i-3. Másrészt azon az i-2 darab P_j csúcson kívül, amelyre k+3-i $\le$ j $\le$ k teljesül, P_i legfeljebb két további csúccsal lehet összekötve a $P_1P_2\ldots P_k$ út mentén, vagyis d(i) $\le$ (i-2)+2=i. összefoglalva, i $\ge$ 3 esetén 0 $\le$ i-d(i) $\le$ 3. Ha felveszünk három további csúcsot, és 3 $\le$ i $\le$ k esetén a P_i csúcsot ezek közül i-d(i) darabbal összekötjük, olyan k+3 csúcsot tartalmazó G_k egyszerű gráfot kapunk, amelyben P₁,P₂,...,P_k ugróiskola.

Megállapíthatjuk tehát, hogy n $\ge$ 6 esetén f(n)=n-3.

Statistics:

82 students sent a solution.

4 points: Aczél Gergely, Ágoston Tamás, Bálint Dániel, Balla Attila, Bencs 111 Ferenc, Bodor Bertalan, Börcsök Bence, Cséke Balázs, Csere Kálmán, Czeller Ildikó, Dudás 002 Zsolt, Éles András, Farkas Márton, Fonyó Dávid, Frankl Nóra, Gele Viktória, Gévay Gábor, Gőgös Balázs, Grósz Dániel, Kalina Kende, Kiss 243 Réka, Kiss 902 Melinda Flóra, Kiss 991 Mátyás, Konkoly 001 Csaba, Kovács 729 Gergely, Kovács Kristóf, Kristóf Panna, Marák Károly, Mészáros András, Mihálykó Ágnes, Nagy 648 Donát, Palincza Richárd, Peregi Tamás, Perjési Gábor, Réti Dávid, Salát Zsófia, Szabó 124 Zsolt, Szabó 895 Dávid, Szalkai Balázs, Szőke Nóra, Tóth 369 László Márton, Véges Márton, Zelena Réka.

3 points: 12 students.

2 points: 4 students.

1 point: 9 students.

0 point: 11 students.

Unfair, not evaluated: 3 solutionss.

Problems in Mathematics of KöMaL, January 2008

82 students sent a solution.
4 points:	Aczél Gergely, Ágoston Tamás, Bálint Dániel, Balla Attila, Bencs 111 Ferenc, Bodor Bertalan, Börcsök Bence, Cséke Balázs, Csere Kálmán, Czeller Ildikó, Dudás 002 Zsolt, Éles András, Farkas Márton, Fonyó Dávid, Frankl Nóra, Gele Viktória, Gévay Gábor, Gőgös Balázs, Grósz Dániel, Kalina Kende, Kiss 243 Réka, Kiss 902 Melinda Flóra, Kiss 991 Mátyás, Konkoly 001 Csaba, Kovács 729 Gergely, Kovács Kristóf, Kristóf Panna, Marák Károly, Mészáros András, Mihálykó Ágnes, Nagy 648 Donát, Palincza Richárd, Peregi Tamás, Perjési Gábor, Réti Dávid, Salát Zsófia, Szabó 124 Zsolt, Szabó 895 Dávid, Szalkai Balázs, Szőke Nóra, Tóth 369 László Márton, Véges Márton, Zelena Réka.
3 points:	12 students.
2 points:	4 students.
1 point:	9 students.
0 point:	11 students.
Unfair, not evaluated:	3 solutionss.

Already signed up?
New to KöMaL?