More Like this

1. Maximum Spread of $$K_{s,t}$$-Minor-Free Graphs

   https://doi.org/10.37236/13410  

   Linz, William; Lu, Linyuan; Wang, Zhiyu (January 2025, The Electronic Journal of Combinatorics)

   The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. In this paper, we consider the family of graphs which contain no $$K_{s,t}$$-minor. We show that for any $$t\geq s \geq  2$$ and sufficiently large $$n$$, there is an integer $$\xi_{t}$$ such that the extremal $$n$$-vertex $$K_{s,t}$$-minor-free graph attaining the maximum spread is the graph obtained by joining a graph $$L$$ on $(s-1)$ vertices to the disjoint union of $$\lfloor \frac{2n+\xi_{t}}{3t}\rfloor$$ copies of $$K_t$$ and $$n-s+1 - t\lfloor \frac{2n+\xi_t}{3t}\rfloor$$ isolated vertices. Furthermore, we give an explicit formula for $$\xi_{t}$$ and an explicit description for the graph $$L$$ for $$t \geq \frac32(s-3) +\frac{4}{s-1}$$. 

   more » « less
2. On the Maximum Spread of Planar and Outerplanar Graphs

   https://doi.org/10.37236/11844  

   Li, Zelong; Linz, William; Lu, Linyuan; Wang, Zhiyu (July 2024, The Electronic Journal of Combinatorics)

   The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. Gotshall, O'Brien and Tait conjectured that for sufficiently large $$n$$, the $$n$$-vertex outerplanar graph with maximum spread is the graph obtained by joining a vertex to a path on $n-1$ vertices. In this paper, we disprove this conjecture by showing that the extremal graph is the graph obtained by joining a vertex to a path on $$\lceil(2n-1)/3\rceil$$ vertices and $$\lfloor(n-2)/3\rfloor$$ isolated vertices. For planar graphs, we show that the extremal $$n$$-vertex planar graph attaining the maximum spread is the graph obtained by joining two nonadjacent vertices to a path on $$\lceil(2n-2)/3\rceil$$ vertices and $$\lfloor(n-4)/3\rfloor$$ isolated vertices. 

   more » « less
3. Edge Cover Through Edge Coloring

   https://doi.org/10.37236/13163  

   Chen, Guantao; Shan, Songling (April 2025, The Electronic Journal of Combinatorics)

   Let $$G$$ be a multigraph. A subset $$F$$ of $E(G)$ is an edge cover of $$G$$ if every vertex of $$G$$ is incident to an edge of $$F$$. The cover index, $$\xi(G)$$, is the largest number of edge covers into which the edges of $$G$$ can be partitioned. Clearly $$\xi(G) \le \delta(G)$$, the minimum degree of $$G$$. For $$U\subseteq V(G)$$, denote by $E^+(U)$ the set of edges incident to a vertex of $$U$$. When $|U|$ is odd, to cover all the vertices of $$U$$, any edge cover needs to contain at least $(|U|+1)/2$ edges from $E^+(U)$, indicating $$ \xi(G) \le |E^+(U)|/ ((|U|+1)/2)$$. Let $$\rho_c(G)$$, the co-density of $$G$$, be defined as the minimum of $|E^+(U)|/((|U|+1)/2)$ ranging over all $$U\subseteq V(G)$$, where $$|U| \ge 3$$ and $|U|$ is odd. Then $$\rho_c(G)$$ provides another upper bound on $$\xi(G)$$. Thus $$\xi(G) \le \min\{\delta(G), \lfloor \rho_c(G) \rfloor \}$$. For a lower bound on $$\xi(G)$$, in 1978, Gupta conjectured that $$\xi(G) \ge \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \}$$. Gupta himself verified the conjecture for simple graphs, and Cao et al. recently verified this conjecture when $$\rho_c(G)$$ is not an integer. In this paper, we confirm the conjecture when the maximum multiplicity of $$G$$ is at most two or $$ \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \} \le 6$$. The proof relies on a newly established result on edge colorings. The result holds independent interest and has the potential to significantly contribute towards resolving the conjecture entirely. 

   more » « less
4. Maximum spread of graphs and bipartite graphs

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

   Breen, Jane; Riasanovsky, Alex W.; Tait, Michael; Urschel, John (December 2022, Communications of the American Mathematical Society)

   Given any graph G G , the spread of G G is the maximum difference between any two eigenvalues of the adjacency matrix of G G . In this paper, we resolve a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs. The first states that for all positive integers n n , the n n -vertex graph G G that maximizes spread is the join of a clique and an independent set, with ⌊ 2 n / 3 ⌋ \lfloor 2n/3 \rfloor and ⌈ n / 3 ⌉ \lceil n/3 \rceil vertices, respectively. Using techniques from the theory of graph limits and numerical analysis, we prove this claim for all n n sufficiently large. As an intermediate step, we prove an analogous result for a family of operators in the Hilbert space over L 2 [ 0 , 1 ] \mathscr {L}^2[0,1] . The second conjecture claims that for any fixed m ≤ n 2 / 4 m \leq n^2/4 , if G G maximizes spread over all n n -vertex graphs with m m edges, then G G is bipartite. We prove an asymptotic version of this conjecture. Furthermore, we construct an infinite family of counterexamples, which shows that our asymptotic solution is tight up to lower-order error terms. 

   more » « less
5. Sharp bounds for decomposing graphs into edges and triangles

   https://doi.org/10.1017/S0963548320000358  

   Blumenthal, Adam; Lidický, Bernard; Pehova, Yanitsa; Pfender, Florian; Pikhurko, Oleg; Volec, Jan (March 2021, Combinatorics, Probability and Computing)

   null (Ed.)

   Abstract For a real constant α , let $$\pi _3^\alpha (G)$$ be the minimum of twice the number of K 2 ’s plus α times the number of K 3 ’s over all edge decompositions of G into copies of K 2 and K 3 , where K r denotes the complete graph on r vertices. Let $$\pi _3^\alpha (n)$$ be the maximum of $$\pi _3^\alpha (G)$$ over all graphs G with n vertices. The extremal function $$\pi _3^3(n)$$ was first studied by Győri and Tuza ( Studia Sci. Math. Hungar. 22 (1987) 315–320). In recent progress on this problem, Král’, Lidický, Martins and Pehova ( Combin. Probab. Comput. 28 (2019) 465–472) proved via flag algebras that $$\pi _3^3(n) \le (1/2 + o(1)){n^2}$$ . We extend their result by determining the exact value of $$\pi _3^\alpha (n)$$ and the set of extremal graphs for all α and sufficiently large n . In particular, we show for α = 3 that K n and the complete bipartite graph $${K_{\lfloor n/2 \rfloor,\lceil n/2 \rceil }}$$ are the only possible extremal examples for large n . 

   more » « less