More Like this

1. Removing Symmetry in Circulant Graphs and Point-Block Incidence Graphs

   https://doi.org/10.3390/math9020166  

   Brooks, Josephine; Carbonero, Alvaro; Vargas, Joseph; Florez, Rigoberto; Rooney, Brendan; Narayan, Darren A (January 2021, Mathematics)

   null (Ed.)

   An automorphism of a graph is a mapping of the vertices onto themselves such that connections between respective edges are preserved. A vertex v in a graph G is fixed if it is mapped to itself under every automorphism of G. The fixing number of a graph G is the minimum number of vertices, when fixed, fixes all of the vertices in G. The determination of fixing numbers is important as it can be useful in determining the group of automorphisms of a graph-a famous and difficult problem. Fixing numbers were introduced and initially studied by Gibbons and Laison, Erwin and Harary and Boutin. In this paper, we investigate fixing numbers for graphs with an underlying cyclic structure, which provides an inherent presence of symmetry. We first determine fixing numbers for circulant graphs, showing in many cases the fixing number is 2. However, we also show that circulant graphs with twins, which are pairs of vertices with the same neighbourhoods, have considerably higher fixing numbers. This is the first paper that investigates fixing numbers of point-block incidence graphs, which lie at the intersection of graph theory and combinatorial design theory. We also present a surprising result-identifying infinite families of graphs in which fixing any vertex fixes every vertex, thus removing all symmetries from the graph. 

   more » « less
2. An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of k

   https://doi.org/10.3390/math11194068  

   Kaudan, Chirag; Taylor, Rachel; Narayan, Darren A. (October 2023, Mathematics)

   For a given a graph G, the zero forcing number of G, Z(G), is the smallest cardinality of any set S of vertices on which repeated applications of the forcing rule results in all vertices being included in S. The forcing rule is as follows: if a vertex v is in S, and exactly one neighbor u of v is not in S, then u is added to S in the next iteration. The failed zero forcing number of a graph was introduced by Fetcie, Jacob, and Saavedra and was defined as the cardinality of the largest set of vertices which fails to force all vertices in the graph. In 2021, Gomez et al. proved that there were exactly 15 graphs with a failed zero forcing number of two, but their proof was complicated, requiring the analysis of many graph families. We present an “inverse” approach where we start with a set of vertices S and then see which graphs have S as a maximum-sized failed zero forcing set. This results in not only a shorter proof but characterizes which graphs have a particular failed zero forcing set. In our proof, we characterize the graphs which have a failed zero forcing set S where |S|=2, meaning considering all simple graphs of order two as induced subgraphs. This approach also has greater potential for characterizing graphs where F(G)>2 since many general arguments on the structure of graphs are developed in this type of analysis and are applicable for failed zero forcing sets of any size. 

   more » « less
3. Universal Geometric Graphs

   https://doi.org/10.1007/978-3-030-60440-0_14  

   Frati, Fabrizio; Hoffmann, Michael; Toth, Csaba D. (October 2020, Graph-Theoretic Concepts in Computer Science (WG 2020))

   null (Ed.)

   We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an n-vertex graph with O(nlogn) edges that contains every n-vertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0 , every n-vertex convex geometric graph that is universal for the class of the n-vertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex caterpillars. 

   more » « less
4. A completion of the proof of the Edge-statistics Conjecture

   https://doi.org/10.19086/aic.12047  

   Fox, Jacob; Sauermann, Lisa (February 2020, Advances in Combinatorics)

   Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $$H$$ in an $$n$$-vertex graph. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $$H$$ and the number of all subgraphs with the same number vertices as $$H$$; this quantity is known as the _inducibility_ of $$H$$. More generally, one can define the inducibility of a family of graphs in the analogous way.Among all graphs with $$k$$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $$k$$ vertices be? Fix $$k$$, consider a graph with $$n$$ vertices join each pair of vertices independently by an edge with probability $$\binom{k}{2}^{-1}$$. The expected number of $$k$$-vertex induced subgraphs with exactly one edge is $$e^{-1}+o(1)$$. So, the inducibility of large graphs with a single edge is at least $$e^{-1}+o(1)$$. This article establishes that this bound is the best possible in the following stronger form, which proves a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn: the inducibility of the family of $$k$$-vertex graphs with exactly $$l$$ edges where $$0<\binom{k}{2}$$ is at most $$e^{-1}+o(1)$$. The example above shows that this is tight for $l=1$ and it can be also shown to be tight for $l=k-1$. The conjecture was known to be true in the regime where $$l$$ is superlinearly bounded away from $$0$$ and $$\binom{k}{2}$$, for which the sum of the inducibilities goes to zero, and also in the regime where $$l$$ is bounded away from $$0$$ and $$\binom{k}{2}$$ by a sufficiently large linear function. The article resolves the hardest cases where $$l$$ is linearly close to $$0$$ or close to $$\binom{k}{2}$$, and provides generalizations to hypergraphs. 

   more » « less
5. Longest cycles in vertex‐transitive and highly connected graphs

   https://doi.org/10.1112/blms.70134  

   Groenland, Carla; Longbrake, Sean; Steiner, Raphael; Turcotte, Jérémie; Yepremyan, Liana (July 2025, Bulletin of the London Mathematical Society)

   Abstract We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lovász from 1969 and Thomassen from 1978, respectively, states that all connected vertex‐transitive graphs contain a Hamiltonian path, and that all sufficiently large such graphs even contain a Hamiltonian cycle. The third conjecture, due to Smith from 1984, states that for in every ‐connected graph any two longest cycles intersect in at least vertices. In this paper, we prove a new lemma about the intersection of longest cycles in a graph, which can be used to improve the best known bounds toward all the aforementioned conjectures: First, we show that every connected vertex‐transitive graph on vertices contains a cycle (and hence path) of length at least , improving on from DeVos [arXiv:2302:04255, 2023]. Second, we show that in every ‐connected graph with , any two longest cycles meet in at least vertices, improving on from Chen, Faudree, and Gould [J. Combin. Theory, Ser. B,72(1998) no. 1, 143–149]. Our proof combines combinatorial arguments, computer search, and linear programming. 

   more » « less