Somers Science Research
  • Home
  • About
    • Sample Timeline
    • Areas of Research
    • Course Overview
  • Students
    • ZOOM Link
    • Science Research Calendar
    • Forms >
      • Research Plan
      • Rules Wizard
      • WESEF Forms
      • WR-JSHS Forms (Certifications)
      • Rubrics
      • Symposium Program Template
    • Poster Templates
    • Resources
    • Summer Assignment
    • Mentor Search Form
    • Current Mentor Bank Information
    • New Student Survey
    • Alumni Mailing List
    • Student Profiles >
      • Class of 2020 >
        • Maeve Janecka
      • Class of 2019 >
        • Raghav Nathan
        • Noah Sanz
        • Emma Jones
        • Christopher Orzech
      • Class of 2018 >
        • Alyssa Klee
        • Rachel Mendelson
      • Class of 2017 >
        • Manisha Kunala
        • Nimat Maloney
        • Maya Berlinger
        • Casey Zorn
        • Justin D'Souza
      • Class of 2016 & Older >
        • Jessica Shaw
        • Simon Zheng
  • Foundation
    • About
    • Mission Statement
    • Newsletter >
      • April 2021
      • February 2021
      • May 2021
      • June 2021
    • Upcoming Events >
      • Holiday Cookie Swap
    • Become A Member!
    • Donations
    • Foundation Mailing List
    • Science Research Brochure
    • Mentor Information
    • Areas of Research
    • By-Laws
  • Mentors
    • Mentors
  • Media
    • Pictures
    • Videos
    • 2020 Virtual Symposium
    • Podcast
  • Competitions
    • Somers Science Fair
    • WESEF
    • WR-JSHS
    • Regeneron STS >
      • Info
      • Regeneron STS Paper Portal
    • ISEF
    • Westlake Science Fair
    • I-SWEEEP
    • Siemens Competition
    • Symposium >
      • Symposium RSVP
  • Awards
  • Store
  • Home
  • About
    • Sample Timeline
    • Areas of Research
    • Course Overview
  • Students
    • ZOOM Link
    • Science Research Calendar
    • Forms >
      • Research Plan
      • Rules Wizard
      • WESEF Forms
      • WR-JSHS Forms (Certifications)
      • Rubrics
      • Symposium Program Template
    • Poster Templates
    • Resources
    • Summer Assignment
    • Mentor Search Form
    • Current Mentor Bank Information
    • New Student Survey
    • Alumni Mailing List
    • Student Profiles >
      • Class of 2020 >
        • Maeve Janecka
      • Class of 2019 >
        • Raghav Nathan
        • Noah Sanz
        • Emma Jones
        • Christopher Orzech
      • Class of 2018 >
        • Alyssa Klee
        • Rachel Mendelson
      • Class of 2017 >
        • Manisha Kunala
        • Nimat Maloney
        • Maya Berlinger
        • Casey Zorn
        • Justin D'Souza
      • Class of 2016 & Older >
        • Jessica Shaw
        • Simon Zheng
  • Foundation
    • About
    • Mission Statement
    • Newsletter >
      • April 2021
      • February 2021
      • May 2021
      • June 2021
    • Upcoming Events >
      • Holiday Cookie Swap
    • Become A Member!
    • Donations
    • Foundation Mailing List
    • Science Research Brochure
    • Mentor Information
    • Areas of Research
    • By-Laws
  • Mentors
    • Mentors
  • Media
    • Pictures
    • Videos
    • 2020 Virtual Symposium
    • Podcast
  • Competitions
    • Somers Science Fair
    • WESEF
    • WR-JSHS
    • Regeneron STS >
      • Info
      • Regeneron STS Paper Portal
    • ISEF
    • Westlake Science Fair
    • I-SWEEEP
    • Siemens Competition
    • Symposium >
      • Symposium RSVP
  • Awards
  • Store

Simon Zheng '13

Title: Pegging Numbers of Strongly Regular Graphs and Grid Graphs

Problem: What is the minimum number pegs required to reach the entire vertex set of different classes of graphs?

Mentor: Padraic Bartlett, California Institute of Technology

Activities and Interests: Math Team, Varsity Soccer, French Club

Abstract: This research studies the mathematical game of graph pegging, which has applications related to modeling network flow, transportation, and supply chain problems in computer science and economics. In graph pegging, we place at most one peg in each vertex of a graph. Given two adjacent pegs and an empty vertex adjacent to the second peg, a pegging move consists of jumping the first peg over the second peg into the empty vertex. The second peg is then removed. We define the pegging number of a graph as the minimum number of pegs such that starting from any distribution of that size, every vertex can be reached with pegging moves. Similarly, we define the optimal pegging number as the minimum number of pegs such that there exists at least one distribution of that size for which every vertex can be reached. We characterize strongly regular graphs with optimal pegging number 2 and 3. In addition, we compute the pegging number and optimal pegging number of the 2 x n grid graph. Finally, we compute the optimal pegging number of the 3 x n grid graph. Overall, we successfully derived the pegging numbers of two classes of graphs.

Picture
© 2016 Somers Science Research. All Rights Reserved.
Picture
Picture