More Like this

1. An Ore-Type Condition for Hamiltonicity in Tough Graphs and the Extremal Examples

   https://doi.org/10.37236/12483  

   Sanka, Masahiro; Shan, Songling (January 2024, The Electronic Journal of Combinatorics)

   Let $$G$$ be a $$t$$-tough graph on $$n\ge 3$$ vertices for some $t>0$. It was shown by Bauer et al. in 1995 that if the minimum degree of $$G$$ is greater than $$\frac{n}{t+1}-1$$, then $$G$$ is hamiltonian. In terms of Ore-type hamiltonicity conditions, the problem was only studied when $$t$$ is between 1 and 2, and recently the second author proved a general result. The result states that if the degree sum of any two nonadjacent vertices of $$G$$ is greater than $$\frac{2n}{t+1}+t-2$$, then $$G$$ is hamiltonian. It was conjectured in the same paper that the $+t$ in the bound $$\frac{2n}{t+1}+t-2$$ can be removed. Here we confirm the conjecture. The result generalizes the result by Bauer, Broersma, van den Heuvel, and Veldman. Furthermore, we characterize all $$t$$-tough graphs $$G$$ on $$n\ge 3$$ vertices for which $$\sigma_2(G) = \frac{2n}{t+1}-2$$ but $$G$$ is non-hamiltonian. 

   more » « less
2. On the Biplanarity of Blowups

   https://doi.org/10.7155/jgaa.v28i2.2989  

   Eppstein, David (May 2024, Journal of Graph Algorithms and Applications)

   The 2-blowup of a graph is obtained by replacing each vertex with two non-adjacent copies; a graph is biplanar if it is the union of two planar graphs. We disprove a conjecture of Gethner that 2-blowups of planar graphs are biplanar: iterated Kleetopes are counterexamples. Additionally, we construct biplanar drawings of 2-blowups of planar graphs whose duals have two-path induced path partitions, and drawings with split thickness two of 2-blowups of 3-chromatic planar graphs, and of graphs that can be decomposed into a Hamiltonian path and a dual Hamiltonian path. 

   more » « less
3. Simple Topological Drawings of k-Planar Graphs.

   https://doi.org/10.1007/978-3-030-68766-3_31  

   Hoffmann, Michael; Liu, Chih-Hung; Reddy, Meghana M.; Toth, Csaba D. (February 2021, Graph Drawing and Network Visualization)

   null (Ed.)

   Every finite graph admits a simple (topological) drawing, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other restrictions simple drawings do not universally exist. For instance, k-planar graphs are those graphs that can be drawn so that every edge has at most k crossings (i.e., they admit a k-plane drawing). It is known that for k≤3 , every k-planar graph admits a k-plane simple drawing. But for k≥4 , there exist k-planar graphs that do not admit a k-plane simple drawing. Answering a question by Schaefer, we show that there exists a function Open image in new window such that every k-planar graph admits an f(k)-plane simple drawing, for all Open image in new window. Note that the function f depends on k only and is independent of the size of the graph. Furthermore, we develop an algorithm to show that every 4-planar graph admits an 8-plane simple drawing. 

   more » « less
4. A synthesis for uniformly 3-edge-connected graphs

   https://doi.org/10.1016/j.dam.2025.02.005  

   Kingsford, Carl; Marçais, Guillaume (June 2025, Discrete Applied Mathematics)

   A multigraph is uniformly k-edge-connected if there are exactly k edge-disjoint paths between any pair of vertices. For example, a uniformly k-edge-connected graph is obtained from a k-edge-connected graph by collapsing the nodes connected by more than k edge-disjoint paths into supernodes. We characterize the class of uniformly 3-edge-connected graphs, giving a synthesis involving two operations by which every uniformly 3-edge-connected multigraph can be generated. Slightly modified syntheses give the planar uniformly 3-edge-connected graphs and the uniformly 3-edge-connected graphs with the fewest possible edges, generalizing the well-known Harary graphs. In proving the correctness of the synthesis, we also show the existence of a particular type of induced, non-separating cycle in near 3-regular graphs, which is of interest in its own right. 

   more » « less
5. Gap sets for the spectra of cubic graphs

   https://doi.org/10.1090/cams/3  

   Kollár, Alicia; Sarnak, Peter (October 2021, Communications of the American Mathematical Society)

   We study gaps in the spectra of the adjacency matrices of large finite cubic graphs. It is known that the gap intervals ( 2 2 , 3 ) (2 \sqrt {2},3) and [ − 3 , − 2 ) [-3,-2) achieved in cubic Ramanujan graphs and line graphs are maximal. We give constraints on spectra in [ − 3 , 3 ] [-3,3] which are maximally gapped and construct examples which achieve these bounds. These graphs yield new instances of maximally gapped intervals. We also show that every point in [ − 3 , 3 ) [-3,3) can be gapped by planar cubic graphs. Our results show that the study of spectra of cubic, and even planar cubic, graphs is subtle and very rich. 

   more » « less