|
|
|
|||||||
| Év szerint | Hónap szerint | Ugrás a hónaphoz | |||||||
Tóth Géza: Gyufagráfok és más egységtávolság-gráfok |
|
|||
|
|
||||
|
||||
| Gyufagráfnak (matchstick graph) hívunk egy olyan, metszés nélkül lerajzolt gráfot, amelynek az élei egység hosszú szakaszok. Egy n csúcsú gyufagráfnak nyilván legfeljebb 3n-6 éle van. Lavollée és Swanepoel 2024-ben pontosan meghatározta az n csúcsú gyufagráfok maximális élszámát. (Ez \lfloor 3n-\sqrt{12n-3}\rfloor). Ennek a meglepő eredménynek különböző érdekes általánosításait, változatait fogjuk vizsgálni. Többek között bebizonyítjuk a következő, ugyancsak meglepő eredményt. Ha az élek továbbra is egység hosszú szakaszok, de minden él metszhet legfeljebb egy másik élt, akkor az élek maximális száma alig változik (legfeljebb 3n-\sqrt[4]{n}/15). Sőt, elképzelhető, hogy ez akkor is így van, ha két metszést engedünk élenként. Közös munka Gehér Pannával, Pach Jánossal és Konrad Swanepoel-lel. |
||||
Esemény exportálása JEvents v3.1.8 Stable Copyright © 2006-2013
