More Like this

1. Embedding Directed Graphs in Potential Fields Using FastMap-D

   Gopalakrishnan, S.; Cohen, L.; Koenig, S.; Kumar, S. (January 2020, Symposium on Combinatorial Search (SoCS))

   Embedding undirected graphs in a Euclidean space has many computational benefits. FastMap is an efficient embedding algorithm that facilitates a geometric interpretation of problems posed on undirected graphs. However, Euclidean distances are inherently symmetric and, thus, Euclidean embeddings cannot be used for directed graphs. In this paper, we present FastMap-D, an efficient generalization of FastMap to directed graphs. FastMap-D embeds vertices using a potential field to capture the asymmetry between the pairwise distances in directed graphs. FastMap-D learns a potential function to define the potential field using a machine learning module. In experiments on various kinds of directed graphs, we demonstrate the advantage of FastMap-D over other approaches. Errata: This version of the paper corrects a programming mistake, resulting in even better experimental results than those reported in the original paper. 

   more » « less
2. Degree of h-polynomials of edge ideals

   https://doi.org/10.1007/s10801-025-01411-9  

   Biermann, Jennifer; Kara, Selvi; O’Keefe, Augustine; Skelton, Joseph; Sosa_Castillo, Gabriel (July 2025, Journal of Algebraic Combinatorics)

   Abstract In this paper, we investigate the degree ofh-polynomials of edge ideals of finite simple graphs. In particular, we provide combinatorial formulas for the degree of theh-polynomial for various fundamental classes of graphs such as paths, cycles, and bipartite graphs. To the best of our knowledge, this study represents the first investigation into the combinatorial interpretation of this algebraic invariant. Additionally, we characterize all connected graphs in which the sum of the Castelnuovo–Mumford regularity and the degree of theh-polynomial of an edge ideal achieve its maximum value, equal to the number of vertices in the graph. 

   more » « less
3. Nimber Sequences of Node-Kayles Games

   Brown, S.; Daugherty, S.; Fiorini, E.; Maldonado, B.; Manzano-Ruiz, D.; Rainville, S.; Waechter, R.; Wong, T. (March 2020, Journal of integer sequences)

   Node-Kayles is an impartial game played on a simple graph. The Sprague-Grundy theorem states that every impartial game is associated with a nonnegative integer value called a Nimber. This paper studies the Nimber sequences of various families of graphs, including 3-paths, lattice graphs, prism graphs, chained cliques, linked cliques, linked cycles, linked diamonds, hypercubes, and generalized Petersen graphs. For most of these families, we determine an explicit formula or a recursion on their Nimber sequences. 

   more » « less
4. An infinite family of two-distance tight frames

   https://doi.org/10.1117/12.2528878  

   Brown, Nicholas P.; Jasper, John (September 2019, Wavelets and Sparsity XVIII)

   The relationship between equiangular tight frames and strongly regular graphs has been known for several years. This relationship has been exploited to construct many of the latest examples of new strongly regular graphs. Recently it was shown that there is a similar relationship between two-distance tight frames and strongly regular graphs. In this paper we present a new tensor like construction of two-distance tight frames, and hence a family of strongly regular graphs. While graphs with these parameters were known to exist, this new construction is very simple, requiring only the existence of an affine plane, whereas the original constructions often require more complicated objects such as generalized quadrangles. 

   more » « less
5. On the Number of Edges of the Frechet Mean and Median Graphs

   https://doi.org/10.1007/978-3-030-97240-0_3  

   Ferguson, Daniel; Meyer, Francois G. (February 2022, Network Science)

   Ribeiro, Pedro; Silva, Fernando; Mendes, José Fernando; Laureano, Rosário (Ed.)

   The availability of large datasets composed of graphs creates an unprecedented need to invent novel tools in statistical learning for graph-valued random variables. To characterize the average of a sample of graphs, one can compute the sample Frechet mean and median graphs. In this paper, we address the following foundational question: does a mean or median graph inherit the structural properties of the graphs in the sample? An important graph property is the edge density; we establish that edge density is an hereditary property, which can be transmitted from a graph sample to its sample Frechet mean or median graphs, irrespective of the method used to estimate the mean or the median. Because of the prominence of the Frechet mean in graph-valued machine learning, this novel theoretical result has some significant practical consequences. 

   more » « less