David Aulicino (Brooklyn College)

Title: A New Approach to the Automorphism Group of a Regular Mapping

Abstract: A regular mapping is a regular (multi)graph whose dual is also a regular graph. The simplest examples are the skeletons of the Platonic solids. We produce a large normal subgroup of the automorphism group of a regular mapping, which is often so large it equals the automorphism group of the graph itself. Everything will be presented graph theoretically. However, time permitting, we will explain the origin of the argument, which arose from studying hyperbolic analogs of the surfaces of the Platonic solids. This is joint work with Jayadev Athreya and Pat Hooper.

Deepak Bal (Montclair State University)

Title: Monochromatic Components in Random Graphs

Abstract: We are concerned with the following Ramsey-type question: if the edges of a graph are r-colored (not necessarily properly), what is the largest monochromatic component (or path, or cycle) which must appear? We address this question for random regular and random k-out graphs. This is joint work with Michael Anastos.

Jonathan Cutler (Montclain State University)

Title: Supersaturation in Extremal Enumeration

Abstract: Turán's theorem states that the maximum number of edges in K_r+1-free graph on n vertices is attained by the complete r-partite graph with part sizes as equal as possible. We write the number of edges in this graph as ex(n,K_r+1), the extremal number of K_r+1. Supersaturation in graphs asks if G has more than ex(n,K_r+1) edges, how many copies of K_r+1 must G contain? Recently, Alon and Shikhelman introduced a generalization of the extremal number. Given graphs H and G, let ex_G(n, H) be the maximum number of copies of G an H-free graph on n vertices can contain. It is natural to ask supersaturation questions in this context as well. We present some results in this area. This is joint work with JD Nir and Jamie Radcliffe.

Anthony Delgado (Columbia University)

Title: Addressing Trees

Abstract: The hypercube, Q_n, has the vertex set {(x₁, x₂, …, x_n) | x_i = 1 or 0}. Vertices x and y are adjacent when their addresses differ in exactly one place. Graham and Pollack tried to address graphs other than hypercubes using binary labels. This did not work for non-bipartite graphs. So they modified the addresses to include a third element, *, which does not differ from 0 or 1. As an example, the vertices of K₃ can be labeled 00, 10, and *1. Let f(G) be the minimum number of places in a valid addressing of a graph G. Thus, f(K₃) = 2. Winkler showed that if G is a connected graph on n vertices, then f(G) ≤ n – 1. The inequality becomes equality if G is a tree or K_n. We present an easy algorithm for addressing trees. This is joint work with M. Lewinter and K.Phillips.

Nathan Kahl (Seton Hall University)

Title: Tutte Polynomials and Graph Compression

Abstract: Kelmans, and independently Satyanarayana, Schoppmann, and Suffel, showed that a graph operation called the compression of a graph decreased both the number of spanning trees and the all-terminal reliability of the graph. A number of other graph parameters have since been shown to be affected by compression, including recently when Csikvari showed that compression could only decrease the magnitude of the coefficients of the graph's chromatic polynomial. In this talk we determine how compression affects the Tutte polynomial of graphs. As a result we are able to generalize all three of the previously mentioned results, as well as a number of others, and some interesting new consequences result as well.

Marty Lewinter (Purchase College)

Title: Making a Graph Eulerian

Abstract: A graph is Eulerian if it has a closed walk that traverses each edge exactly once. A graph is Eulerian if and only if all of its vertices have even degree. The Euler number of a graph is defined to be the minimum number of edges that must be added to G to render it Eulerian. This becomes trivial if the odd vertices of G form an independent set, since the number of odd vertices of any graph is even. Thus, if G contains 2k odd vertices, the Euler number of G is k. We present several results and open problems concerning the Euler number. This is joint work with A. Delgardo and P. Magrini.

Joseph Malkevitch (York College and the Graduate Center, CUNY)

Title: Simplicial Polyhedra with at Most Two Edge Lengths

Abstract: Planar triangulations with at least 4 vertices can be realized by convex 3-dimensional polyhedra. Many interesting combinatorial and geometrical questions arise from considering triangulations whose edges are two-colored, which can be interpreted as the associated polyhedron having at most two different edge lengths. Such polyhedra include polyhedra where all of the faces are strictly isosceles triangles as well as where there are mixtures of equilateral and isosceles triangles.

Bhargav Narayanan (Rutgers University)

Title: Exceptional graphs for the random walk

Abstract: A long enough random word on the alphabet {Up, Down, Left, Right} simultaneously “solves” every maze living inside an n x n grid. What happens for infinite mazes living in the square lattice Z² ? The talk will revolve around trying to answer this question.

Louis Petingi (College of Staten Island and The Graduate Center, CUNY)

Title: Construction/Destruction Monte Carlo to Calculate the Number of Path-sets and Cut-sets of a Graph with Diameter Constraints and Applications to Network Reliability Theory

Abstract: Consider a network G = (V,E) composed of a set V of vertices, a set E of edges, and a set K of vertices called the terminal-set. In this paper we show how the Construction/Destruction (C/D) Monte Carlo simulation methods can be applied to estimate the number of topological structures of a graph G, called path-sets (and their combinatorial dual cut-sets), which are subgraphs of G where the maximum distance between the vertices of K (i.e., the K-diameter) is less than or equal to a given diameter bound d. The number of path-sets (or cut-sets) are required to calculate the Diameter-constrained reliability of a network, and since determining the number of such structures are intractable problems, these techniques are shown to be very accurate and therefore useful to solve optimization problems in reliability theory. This is joint work with Ilya Gertsbakh.

Kevin Phillips (Horace Greeley High School)

Title: Randomly Paintable Graphs

Abstract: A nontrivial graph G of order n is paintable if its vertex set can be labeled with the natural numbers {1,2,…,n} such that for each i=1,2,…,n-1, the edge (i)(i+1)∉ E(G). If the assignment of the vertex labels can be accomplished using a greedy algorithm, the graph is called randomly paintable. The path P₄ is paintable, but is not randomly paintable. The cycle C₅ is randomly paintable. A graph is paintable if and only if its complement is traceable, that is, it has a spanning path. Moreover, a graph is randomly paintable if and only if its complement is randomly traceable. We present several theorems and pose open questions. This is joint work with A.Delgado and M.Lewinter.

John Saccoman (Seton Hall University)

Title: Laplacian Eigenvalue Results for Threshold Graphs and Multigraphs

Abstract: A graph is a split graph if its node set can be partitioned into a clique and an independent set. A split graph G is a threshold graph if, for all pairs of nodes u and v in G, N(u)-{v} is a subset of N(v) -{u} whenever deg(u) is at most deg(v). Threshold graphs have degree sequences that uncover some interesting properties; for example, their Laplacian spectra can be completely determined by their degree sequences. In this way, they play an important role in reliability synthesis. Since the computation of a graph's All-Terminal Reliability (ATR) is known to be intractable, it is advantageous to bound this quantity. In particular, threshold graphs are believed to bound the number of spanning trees and ATR from below for connected graphs in the same node/edge class. In this talk, we will look at three ways to determine the number of spanning trees in a threshold graph, and present some results for multigraphs that are underlying threshold.

Charlie Suffel (Stevens Institute of Technology)

Title: Component Order Neighbor Connectivity – a Generalization of Domination

Given a graph G on n nodes with e edges and a threshold value 1≤k≤n, the component order neighbor connectivity of G, K_nc^(k)(G), is the minimum order of a set of nodes U such that each component of G – N[U] has order ≤ k – 1 (where N[U] is the closed neighborhood of U). Of course if k = 1, K_nc ⁽¹⁾(G) = γ(G), the well known parameter domination. It is known that, in general, domination is an “exceptional invariant,” i.e. removal of nodes from G can make it go up or down. The same is true for K_nc^(k) for k ≥2. We investigate this phenomenon for K_nc^(k) and , in particular, determine some results for this phenomenon regarding γ that carry over to K_nc^(k) and some that do not. This is joint work with A.Doucette and A.Muth.

Sanju Vaidya (Mercy College)

Title: Computation of Graph Vulnerability Measures and Topological Indices

Abstract: Vulnerability measures and topological indices are crucial in solving various problems such as assessment of communication networks and development of mathematical models for chemical compounds. In 1947 Harry Wiener introduced a topological index related to molecular branching. Now there are more than 100 topological indices for molecular graphs. In this presentation, we will establish bounds for various topological indices such as First Zagreb Index, Estrada Index, and certain indices based on eccentricities of vertices. Additionally, we will establish formulas for certain graph vulnerability measures such as Residual Closeness and certain topological indices such as hyper-Wiener index for various graphs. We will do this by computing Hosoya polynomials (also called Wiener polynomials) and their derivatives. It is amazing to see how Hosoya polynomials give powerful tools for fields of Communications and Chemistry.

Christina Zamfirescu (Hunter College and the Graduate Center, CUNY)

Title: Intersection and Transformations of Digraphs, Survey Connections

Abstract: Most known transformations on graphs/digraphs are the line, total and middle, as well as subdivision, square, etc (di)graphs. We express them as intersection digraphs, study their intersection numbers, and express them using the data of the original digraph that is transformed. Connections with applications, especially in survey design are drawn.