Grafsten
Grafsten är ett matematiskt spel som spelas på en graf med noll eller fler småstenar på var och en av dess hörn . 'Spelspel' består av en serie småstensrörelser. Ett stendrag på en graf består av att välja ett hörn med minst två småstenar, ta bort två småstenar från det och lägga till en till en intilliggande hörn (den andra borttagna stenen kastas ur spelet). π( G ), stentalet för en graf G , är det lägsta naturliga talet n som uppfyller följande villkor:
Med tanke på vilket mål eller 'rot' som helst i grafen och varje initial konfiguration av n stenar på grafen, är det möjligt, efter en serie av stenrörelser, att nå en ny konfiguration där den angivna rotvertexen har en eller flera stenar.
Till exempel, på en graf med 2 hörn och 1 kant som förbinder dem är stentalet 2. Oavsett hur de två stenarna placeras på grafens hörn är det alltid möjligt att flytta en sten till valfri hörn i grafen. En av de centrala frågorna med grafsten är värdet på π( G ) för en given graf G .
Andra ämnen inom klappersten inkluderar klappersten, optimal klappersten, dominerande klappersten, gränser och trösklar för siffror för småsten, såväl som djupa grafer.
π( G ) — stentalet för en graf
Pebbling-spelet föreslogs först av Lagarias och Saks, som ett verktyg för att lösa ett visst problem inom talteorin . 1989 FRK Chung begreppet i litteraturen och definierade stentalet, π( G ).
Småstensnumret för en komplett graf på n hörn kan lätt verifieras att vara n : Om vi hade ( n − 1) småsten att sätta på grafen skulle vi kunna sätta en sten på varje hörn utom målet. Eftersom ingen vertex har två eller flera småsten är inga rörelser möjliga, så det är omöjligt att placera en sten på målet. Alltså måste stentalet vara större än n − 1. Givet n småsten finns det två möjliga fall. Om varje vertex har en sten, krävs inga rörelser. Om någon vertex är blottad, måste minst en annan vertex ha två stenar på sig, och en stenrörelse gör att en sten kan läggas till valfri målpunkt i hela grafen.
π( G ) för familjer av grafer
Småstensnumret är känt för följande graffamiljer:
- där är en komplett graf på n hörn.
- där är en väggraf på n hörn.
- där är en hjulgraf på n hörn.
Grahams småsteniga gissningar
Är stentalet för en kartesisk produkt av grafer högst produkten av grafernas stental?
Chung (1989) tillskriver Ronald Graham gissningen att stentalet för en kartesisk produkt av grafer som mest är lika med produkten av stentalen för faktorerna i produkten. Detta har kommit att bli känt som Grahams småstensförmodan . Från och med 2019 är det fortfarande olöst, även om speciella fall är kända.
γ( G ) — omslagsstenens nummer för en graf
Crull et al. introducerade begreppet omslagssten. γ( G ), numret på täckstenen för en graf är det minsta antalet småstenar som behövs så att från varje initialt arrangemang av småstenarna, efter en serie av småstensrörelser, täcks grafen: det finns minst en sten på varje vertex . Ett resultat som kallas staplingssatsen hittar täckningsstenstalet för vilken graf som helst.
Staplingssatsen
Enligt staplingssatsen inträffar den initiala konfigurationen av småsten som kräver att de flesta småstenarna täcks löst när alla småsten placeras på en enda vertex. Baserat på denna observation, definiera
för varje hörn v i G , där d ( u , v ) anger avståndet från u till v . Då är täckstenstalet det största s ( v ) som blir resultatet.
γ( G ) för familjer av grafer
Omslagsstensnumret är känt för följande graffamiljer:
- där är en komplett graf på n hörn.
- där är en sökväg på n hörn.
- där är en hjulgraf på n hörn.
Se även
Vidare läsning
- Chan, Melodi ; Godbole, Anant P. (2008). "Förbättrade stengränser". Diskret matematik . 308 (11): 2301–2306. arXiv : math/0510045 . doi : 10.1016/j.disc.2006.06.032 . MR 2404560 . S2CID 5501949 .
- Hurlbert, Glenn H. (1999). "En undersökning av grafsten" (PDF) . Proceedings of the Thirtionth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999) . Congressus Numerantium. Vol. 139. s. 41–64. MR 1744229 .
- Pachter, Lior ; Snevily, Hunter S.; Voxman, Bill (1995). "Om grusgrafer" (PDF) . Proceedings of the Twenty-Sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995) . Congressus Numerantium. Vol. 107. s. 65–80. MR 1369255 . Arkiverad från originalet (PDF) 2015-11-25.