New York Combinatorics Seminar
Graduate Center, CUNY Fridays 11:00 am  12:00 am Room 4419 This seminar covers a wide range of topics in combinatorics and its applications to other disciplines, especially computer science. The CUNY Graduate Center is located at 365 Fifth Avenue (at the corner of 34th Street), New York. It can be easily approached by subway, using the B,D,F,N,Q,R, or 6 trains. Seminar organizers are Jonathan Cutler, Ezra Halleck, Christopher Hanusa, Sandra Kingan, and Kerry Ojakian. Spring 2015 Talks January 30, 2015: Sandra Kingan (Brooklyn College, CUNY)
Title: Social Network Analysis
February 20 and 27, 2015: Kerry Ojakian (Bronx Community College, CUNY)
Title: An exposition of the Graph Minor Theorem
March 13, 2015: Yared Nigussie (Columbia University)
Title: WQO theorems versus proof systems
March 27, 2015: Henning Ulfarsson (Reykjavik University, Iceland)
Title: TBA
April 17, 2015: Jonathan Cutler (Montclair State University)
Title: TBA
March 1 or 8 (tentative), 2015: Milan Bradonjic (AlcatelLucent)
Title: TBA
May 15, 2015: Carol Zamfirescu (Technical University of Dortmund, Germany)
Title: TBA
Abstract: A graph is hypohamiltonian if it is not hamiltonian but, when omitting an arbitrary vertex, it becomes hamiltonian. A problem of Sousselier from 1963 initiated the study of these graphs. The smallest hypohamiltonian graph is the famous Petersen graph on 10 vertices. Among the work concerning hypohamiltonian graphs, Chv\'{a}tal asked in 1973 whether there exist planar hypohamiltonian graphs, while Gr\"{u}nbaum conjectured that these graphs do not exist. An infinite family of such graphs was subsequently found by Thomassen, the smallest among them having order 105. In the past four decades smaller and smaller planar hypohamiltonian graphs have been found. These recordholders will be the main focus of the first part of the talk. In the second part, we present Grinberg's Criterion in the context of planar hypohamiltonian graphs and give two strengthenings of a theorem of Araya and Wiener. (One of these strengthenings is joint work with Jooyandeh, McKay, \"{O}sterg{\aa}rd, and Pettersson.) For the final part of the presentation, we call a graph G almost hypohamiltonian if G is nonhamiltonian, there exists a vertex w such that Gw is nonhamiltonian, and for any vertex v not equal to w the graph G  v is hamiltonian. We discuss connections between hypohamiltonian and almost hypohamiltonian graphs and presentmotivated by an old question of Thomassena 4connected almost hypohamiltonian graph.
Previous Speakers
Fall 2014
