Saturday October 24, 2026

Sponsored by 

The Metropolitan New York Section of the Mathematical Association of America

and the Department of Mathematics at Seton Hall University

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: Seton Hall University. Arts and Sciences Hall 109, Seton Hall University, 400 S Orange Ave, South Orange, NJ. There is a train leaving NYC, NY Penn St (Moynihan) at 9:11 and arriving to South Orange at 9:48.  Campus map and other information.

Registration:  There is no registration fee. However, please register online by October 22, 2026 by filling this Registration Form. If you forget to register please come anyway. There may not be lunch for you, but your participation will be welcomed.

Schedule (in Eastern Time ET)

10:30 am: Welcome and Registration

11:00 - 12:00: Michael Yatauro (Penn State Brandywine)

12:00 - 2:00 pm: Lunch and Poster Session

2:00 pm - 2:20 pm: John T. Saccoman (Seton Hall University)

2:20 pm - 2:40 pm: Kristi Luttrell (Seton Hall University)

2:40 pm - 3:00 pm: Nathan Kahl (Seton Hall University)

_________________________________________

Abstracts

Nathan Kahl (Seton Hall University)

Title: An Alternative Construction for (k,q)-graphs

Abstract: The independence polynomial of a graph G evaluated at -1, denoted here as I(G;-1), has become an object of interest in a number of different areas.  Levit and Mandrescu conjectured that for every possible integer k and integer q, there is a connected graph G with decycling number equal to k and I(G;-1) equal to q.  Recently Cutler and Kahl gave a construction that proved the conjecture, but that construction was both recursive and quite edge-sparse.  Here we provide an alternative construction which is simpler, direct (non-recursive) and 2-connected.  The construction builds the necessary (k,q) graph from the binary expansion of the value q.  This is joint work with undergraduate Kayla Wager.

Kristi Luttrell (Seton Hall University)

Title: Neighbor-Component Order Connectivity of Satellite Communication Networks

Abstract: This research extends neighbor-component order connectivity, a graph-theoretic parameter that measures the vulnerability of a network by removing closed neighborhoods of vertices until the order of the remaining components fall below a given threshold value, to a new setting motivated by the Kessler effect. In the context of the Kessler effect, where vertices represent satellites and edges represent inter-satellite communication links, collisions among orbiting objects can generate cascading debris and lead to further collisions. We focus on Low Earth Orbit satellite constellations and model such a network as a complete subgraph representing Earth-based communication together with one or more orbital rings of satellites connected to it. We derive formulas for neighbor-component order connectivity for the single-ring and two-ring cases, providing a graph-theoretic framework for analyzing the vulnerability of these satellite network structures.

John T. Saccoman (Seton Hall University)

Title: Spectra for multigraphs that are underlying complete split

Abstract: Complete split graphs are threshold graphs that have all nodes in the independent set adjacent to all nodes in the clique. In 2002, Hansen et. al. presented criteria for complete split graphs that have integral spectra for their adjacency matrix. We explore spectra of multigraphs that are underlying complete split for some of the matrices associated with graphs. This is joint work with various undergraduate mathematics majors at Seton Hall University.

Michael Yatauro (Penn State Brandywine)

Title: 2-factors in 1-tough k-connected graphs with prescribed independence number: updates and extensions

Abstract:  In 1972, Chvátal and Erdös proved the classic result that any graph whose independence number is at most its vertex-connectivity is Hamiltonian. Since then, researchers have explored the cycle structure of graphs having an independence number greater than the vertex-connectivity. For example, O, West, and Wu proved that any n-vertex k-connected graph with independence number a > k has a cycle of length at least k(n+a-k)/a. In this talk we discuss updates to results concerning the existence of 2-factors in 1-tough graphs for which the independence number exceeds the vertex connectivity by a fixed small amount. In each case, we demonstrate the exceptional 1-tough graphs having no 2-factor and provide related corollaries.

_________________________________________

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

There is a place to upload poster title and abstract on the registration form.  Bring your poster with you. We will provide tape for posting it. If you have any questions about the poster session, please email Sandra Kingan (skingan@brooklyn.cuny.edu).

Local Organizing Committee: Nathan Kahl and John Saccoman

Graph Theory Day Steering Committee: Deepak Bal, Nadia Benakli, Jonathan Cutler, Ezra Halleck, Nathan Kahl, Sandra Kingan, Kerry Ojakian, Eric Ramos, Abigail Raz, John Saccoman, and Mingxian Zhong.

Transit Information:

NJ Transit trains: Departing from NY Penn Station there is a 9:09am and a 9:43  am train on the Montclair Boonton Line (arriving at 9:51 and 10:32 respectively). Please get off at the MONTCLAIR HEIGHTS station, not the Montclair State University station. 

NJ Transit buses: Departing from NY Port Authority Bus Terminal there is a 191 Bus at 9:39am and arriving at MSU at 10:18am.

Driving/Parking: Direct your GPS to the Red Hawk Deck. This is a paid deck. 

A map showing the locations of Montclair Heights station, the Red Hawk Deck and Schmitt Hall is included below.