Aug 2026· 2 citations· ⚡ 1 influential· 10 references
Mathematics
Abstract
For a graph $G$, let $\alpha(G)$ be the second smallest eigenvalue of the Laplacian matrix of $G$, also known as the algebraic connectivity. Algebraic connectivity plays an important role in characterizing the connectivity of graphs and convergence properties of networks. Kolokolnikov conjectured that among all graphs on $n$ vertices with exactly $2n-4$ edges, $\alpha(G)\leq 2$ and one of the maximizers is the complete bipartite graph whose two parts have sizes two and $n-2$, respectively. In this paper, we completely resolve this conjecture.
Given a graph $G$, we show that the mixed metric dimension of $G$ is exactly $\ell(G)+2c(G)$ if and only if $G$ is either a cactus graph in which every cycle has precisely one vertex of degree at least $3$, or a balanced $\Theta$-graph, where $\ell(G)$ and $c(G)$ denote the number of leaves and the cyclomatic number of...
The algebraic connectivity of a graph $G$ is a well-studied graph invariant that is related to other properties of the graph such as connectivity and expansion. Given $n$ and $m$, $\alpha(n,m)$ is the maximum algebraic connectivity of a graph with $n$ vertices and $m$ edges. In 2015, Kolokolnikov conjectured that $\alp...
S. Cioabă, Abhay Jayarajan, M. Kannan et al.· 1 citation
Aldous and Fill (2002) conjectured the asymptotic maximum relaxation time of a random walk on a connected regular graph. Since the relaxation time of a $d$-regular graph $G$ is $d/\mu(G)$, where $\mu(G)$ denotes its algebraic connectivity, this conjecture is closely related to the problem of minimizing algebraic connec...
A graph $G$ is called $F$-irregular if all its vertices have distinct $F$-degrees, defined as the number of subgraphs of $G$ isomorphic to a given graph $F$ and containing the respective vertex. We prove the Strong Conjecture about $F$-irregular graphs (Dovzhenok, Filuta, and Chuhai, 2024), which states that for every...
We introduce a new minor monotone graph parameter, the algebraic frustration dimension $\textnormal{frustdim}(G)$ of a graph $G$, as the greatest minimum rank of an optimal solution in a certain family of embedding problems for signed graphs with underlying graph $G.$ Our main results are forbidden minor characterizati...
Uwe Schwerdtfeger· Electronic Journal of Combin...· 0 citations
Kolokolnikov conjectured that, among all simple graphs on \(n\) vertices with exactly \(2(n-2)\) edges, the complete bipartite graph maximizes algebraic connectivity. This paper proves the conjecture. The underlying Lean~4 formalization was generated with MerLean and checked by the Lean kernel.
