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.
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.
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.
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.
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)\).
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.