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 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 n hörn.
  • där är en väggraf n hörn.
  • där är en hjulgraf n hörn.

Grahams småsteniga gissningar

Olöst problem i matematik :

Ä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 n hörn.
  • där är en sökväg n hörn.
  • där är en hjulgraf n hörn.

Se även

Vidare läsning