## The American Journal of Combinatorics

The American Journal of Combinatorics (AJC) is a double-blind refereed open-access online journal. AJC publishes research articles, notes, and surveys in all branches of combinatorics as well as articles related to combinatorics. AJC was established to support growing research on combinatorics all over the world and to create a free online research publishing platform that is accessible to all. There are no Article Processing Charges.

ISSN 2768-4202

## Recent Articles

• Research note
Some relations between the largest eigenvalue and the frustration index of a signed graph
Zoran Stanić
Let $$\dot{G}$$ be a signed graph with $$n$$ vertices and the frustration index $$\ell$$. We prove the existence of $$k~(k\geq \ell)$$ edges $$e_1, e_2, \ldots, e_k$$ of $$\dot{G}$$ such that $\begin{equation*}\lambda_1(\dot{G})\leq \lambda_1(\dot{G}-e_1)\leq \lambda_1(\dot{G}-e_1-e_2)\leq\cdots\leq\lambda_1\Big(\dot{G}-\sum_{i=1}^k e_i\Big),\end{equation*}$ where $$\lambda_1$$ denotes the largest eigenvalue, and an inequality in above chain is strict unless the signed graph on the left hand side is disconnected with at least two components with the same largest eigenvalue. We also prove the existence of a connected balanced spanning subgraph $$\dot{H}$$ such that $\begin{equation*}\ell\geq \frac{\big(\lambda_1(\dot{H}\big)-\lambda_1(\dot{G})\big)\big(\Delta+\lambda_1(\dot{H})\big)}{2\Delta}\sqrt{\frac{n}{n-1}},\end{equation*}$ where $$\Delta$$ is the maximum vertex degree in $$\dot{H}$$, along with the equality precisely in the trivial case when $$\dot{G}$$ is balanced. We also derive some consequences of the previous results.

• Research article
Gallai-Edmonds decomposition of unicyclic graphs from null space
L. Emilio Allem, Daniel A. Jaume, Gonzalo Molina, and Maikon M. Toledo
In this paper, we compute the Gallai-Edmonds decomposition of a unicyclic graph $$G$$ using linear algebraic tools. More precisely, the Gallai-Edmonds decomposition of $$G$$ is obtained from the null space associated with adjacency matrices of its subtrees.

• Research note
New formulations of the union-closed sets conjecture
Sudipta Mallik
The union-closed sets conjecture states that if a finite set $$\mathcal A$$ of finite sets is union-closed and $$\mathcal A\neq \{ \varnothing\}$$, then there exists an element in $$\displaystyle\cup_{A\in \mathcal A} A$$ that belongs to at least half of the sets in $$\mathcal A$$. We present three new formulations of the union-closed conjecture in terms of matrices, graphs, and hypergraphs.

• Research article
Normalized Laplacians for gain graphs
M. Rajesh Kannan, Navish Kumar, and Shivaramakrishna Pragada
We propose the notion of normalized Laplacian matrix $$\mathcal{L}(\Phi)$$ for a gain graph $$\Phi$$ and study its properties in detail, providing insights and counterexamples along the way. We establish bounds for the eigenvalues of $$\mathcal{L}(\Phi)$$ and characterize the classes of graphs for which equality holds. The relationships between the balancedness, bipartiteness, and their connection to the spectrum of $$\mathcal{L}(\Phi)$$ are also studied. Besides, we extend the edge version of eigenvalue interlacing for the gain graphs. Thereupon, we determine the coefficients for the characteristic polynomial of $$\mathcal{L}(\Phi)$$.

• Research article
Spectral ordering and 2-switch transformations
Elismar Oliveira, Victor N. Schvöllner, and Vilmar Trevisan
We address the problem of ordering trees with the same degree sequence by their spectral radii. To achieve that, we consider 2-switch transformations which preserve the degree sequence and establish when the index decreases. Our main contribution is to determine a total ordering of a particular family by their indices according to a given parameter related to sizes in the tree.