Saturday November 18, 2023

Sponsored by 

The Metropolitan New York Section of the Mathematical Association of America

and hosted by the

School of Arts and Sciences of New York City College of Technology

Graph Theory Day is held at different locations in and around New York City. 
Our goal is to provide a learning and sharing experience on recent developments.
Please encourage your students to attend and present a poster.

Location: New York College of Technology, CUNY, Room A105, Academic Complex, 285 Jay St., Brooklyn NY 11201.
Directions to City Tech.

Registration:  There is no registration fee and lunch is free. However, please register online by Nov 15, 2023 by filling this Registration Form.
On-site registration is available with the understanding that lunch is for registered participants. 

Schedule (in Eastern Time ET)

10:30 am:  Check-In/Coffee and Bagels

10:45 am:  Welcome Remarks by Jonathan Natov (City Tech Math Dept. Chair)

11:00 am - 12:00 pm:  Aihua Li (Montclair State University)

12:00 pm - 12:30 pm: Lunch

12:30 - 2:00 pm: Poster Session

2:00 pm - 3:00 pm:  Abigail Raz (The Cooper Union)

3:00 - 3:15 pm: Coffee Break

3:15 - 4:15 pm: Sandra Kingan (Brooklyn College and the Graduate Center, CUNY)

4:15 - 5:00 pm: Open Problems and Final Remarks

5:00 pm: Dinner at the Park Plaza Restaurant, 220 Cadman Plaza West, Brooklyn, NY 

_________________________________________

Abstracts

Aihua Li (Montclair State University)

Title:  Restricted Edge Connectivities of Alternating Group Graphs
Abstract:  In this research, we study restricted edge-cut sets and the related restricted-edge connectivity in certain alternating group graphs. Let S be a subset of the edge set of a graph G and m be a positive integer. The set S is a restricted edge-cut of order m if G - S is disconnected with each component consisting of at least m vertices. The m-restricted edge connectivity of G is the minimum cardinality of all restricted edge-cuts of order m, if it exists. An n-dimensional alternating group graph AG_n is constructed from the alternating group of degree n. We give formulas for the m-restricted edge connectivity of AG_n  for small values of m.

Abigail Raz (The Cooper Union)

Title:  The Explorer-Director Game on Graphs
Abstract:  The Explorer-Director game, first introduced by Nedev and Muthukrishnan, can be described as a game where two players—Explorer and Director— determine the movement of a token that is positioned on the vertices of some given graph. At each time step, the Explorer specifies a distance that the token must move with an aim to maximize the total number of vertices ultimately visited. However, the Director adversarially chooses where to move token in an effort to minimize this number. The game ends when no new vertices can be visited. Given a graph G and a starting vertex v, the number of vertices that are visited under optimal play is denoted by fd(G, v). In this talk we will explore this game providing some general bounds, exact results on fd(G, v) for specific graph families, and, time permitting, discuss some scenarios when the Explorer can still force fd(G, v) vertices to be visited with a non-adaptive strategy (i.e. the Explorer’s choices are independent of the Director’s choices). This research is joint with Pat Devlin, Erin Meger, and a group of over 20 undergraduate students participating in the 2020 Polymath REU. 

Sandra Kingan (Brooklyn College and the Graduate Center)

Title: On the epidemic threshold of a network

Abstract: In this talk we present an approach to vertex centrality that measures the impact of a vertex v in a graph G by removing it and considering the subgraph G-v. Various parameters can be calculated for G and compared with the corresponding parameters for G-v to obtain a ranking of the vertices. The parameter examined in this paper is the largest eigenvalue of the adjacency matrix of the graph. It is a key quantity in the study of processes such as a virus spreading on a network of people or computers, ideas spreading on social media, viral marketing, etc. The inverse of the largest eigenvalue is the epidemic threshold in a non-linear dynamical system model of a contagion spreading on a network. We define the spread centrality of a vertex v as the difference between the largest eigenvalues of G and G-v and compare it to other centrality measures. This is joint work with REU students V. Cherniavskyi and G. Dennis.

_________________________________________

Poster Session (12:30 - 2:00 pm)

Santiago Adams (California Institute of Technology). 

Poster Title: Pancyclicity of Almost Planar graphs

Faculty Advisor: Sandra Kingan (Brooklyn College)

Erik Dahlen (DePaul University). 

Poster Title: b-Chromatic Number of Star Graph Families

Faculty Advisor: Emily Barnard (DePaul University)

Gabriel Dennis (Brooklyn College). 

Poster Title: On the Epidemic Threshold of a Network

Faculty Advisor: Sandra Kingan (Brooklyn College)

Jiah Jin (Cooper Union). 

Poster Title:  Coalescing Results for the Distance Matrix

Faculty Advisor: Steve Butler

Jesen Tanadi (Brooklyn College). P

oster Title: Central Perks: Impact of Subway Access on Rent in NYC Neighborhoods

Faculty Advisor: Sandra Kingan (Brooklyn College)

There is a place to upload poster title and abstract on the registration form.  If you have any questions about the poster, please email Dr. Sandra Kingan (skingan@brooklyn.cuny.edu).

_________________________________________

Local Organizing Committee: Nadia Benakli, Ezra Halleck, and Satyanand Singh (New York City College of Technology).

Student Helpers: Andrew Vaughn and Julia Rivera 

For information on registration and logistics contact Dr. Ezra Halleck (ehalleck@citytech.cuny.edu).

_________________________________________

Graph Theory Day Steering Committee: 

Deepak Bal, Nadia Benakli, Jonathan Cutler, Ezra Halleck, Nathan Kahl, Sandra Kingan, Joseph Malkevitch, Kerry Ojakian, Abigail Raz, John Saccoman, and Mingxian Zhong.