## The American Journal of Combinatorics

The American Journal of Combinatorics (AJC) is a double-blind refereed diamond 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.

## Recent Articles

• Research note
On the Min4PC Matrix of a Tree
Ali Azimi, Rakesh Jana, Mukesh K Nagar, and Sivaramakrishnan Sivasubramanian
The Four point condition (abbreviated as 4PC) is a condition used to test if a given distance matrix arises from shortest path distances on trees. From a tree $$T$$, Bapat and Sivasubramanian defined a matrix $$\operatorname{Min4PC}_T$$ based on this condition. They also gave a basis $$B$$ for the row space of $$\operatorname{Min4PC}_T$$ and determined its Smith Normal Form. In this paper, we consider the matrix $$\operatorname{Min4PC}_T[B,B]$$ restricted to a basis $$B$$ and give an explicit inverse for it. It is known that the distance matrix $$D_T$$ of a tree $$T$$, is invertible and that its inverse is a rank-one update of its scaled Laplacian. Our inverse has a similar form and is a rank-one update of a Laplacian like matrix.

• Research article
The nullity of the net Laplacian matrix of a signed graph
Zhuang Xiong
The net Laplacian matrix of a signed graph $$\Gamma = (G, \sigma)$$, where $$G = (V(G),E(G))$$ is an unsigned graph (referred to as the underlying graph) and $$\sigma: E(G) \rightarrow \{-1, +1\}$$ is the sign function, is defined as $$L^{\pm}(\Gamma) = D^{\pm}(\Gamma) - A(\Gamma)$$. Here, $$D^{\pm}(\Gamma)$$ and $$A(\Gamma)$$ represent the diagonal matrix of net-degrees and the adjacency matrix of $$\Gamma$$, respectively. The nullity of $$L^{\pm}(\Gamma)$$, denoted as $$\eta (L^{\pm} (\Gamma))$$, refers to the multiplicity of $$0$$ as an eigenvalue of $$L^{\pm}(\Gamma)$$. In this paper, we concentrate on the nullity of the net Laplacian matrix of a connected signed graph $$\Gamma$$, and establish that $$1 \leq \eta (L^{\pm} (\Gamma)) \leq \min\{ \beta(\Gamma) + 1, |V(\Gamma)| - 1 \}$$, where $$\beta(\Gamma) = |E(\Gamma)| - |V(\Gamma)| + 1$$ denotes the cyclomatic number of $$\Gamma$$. We completely determine the connected signed graphs with nullity $$|V(\Gamma)| - 1$$. Additionally, we characterize the signed cactus graphs with nullity $$1$$ or $$\beta(\Gamma) + 1$$.

• Research note
Rank of signed cacti
Zoran Stanić
A signed cactus $$\dot{G}$$ is a connected signed graph such that every edge belongs to at most one cycle. The rank of $$\dot{G}$$ is the rank of its adjacency matrix. In this paper we prove that $\sum_{i=1}^k n_i-2k\leq \operatorname{rank}(\dot{G})\leq \sum_{i=1}^k n_i-2t +2 s,$ where $$k$$ is the number of cycles in $$\dot{G}$$, $$n_1, n_2, \ldots, n_k$$ are their lengths, $$t$$ is the number of cycles whose rank is their order minus two, and $$s$$ is the number of edges outside cycles. Signed cacti attaining the lower bound are determined.

• Research article
Eigenvalues of multipart matrices and their applications
Ranjit Mehatari
A square matrix is called a multipart matrix if all its diagonal entries are zero and all other entries in each column are constant. In this paper, we describe various interesting spectral properties of multipart matrices. We provide suitable bounds for the spectral radius of a multipart matrix. Later on, we show applications of multipart matrices in spectral graph theory.

• Research article
On the structure of the fundamental subspaces of acyclic matrices with $$0$$ in the diagonal
Daniel A. Jaume and Adrián Pastine
A matrix is called acyclic if replacing the diagonal entries with $$0$$, and the nonzero diagonal entries with $$1$$, yields the adjacency matrix of a forest. In this paper we show that the null space and the rank of an acyclic matrix with $$0$$ in the diagonal is obtained from the null space and the rank of the adjacency matrix of the forest by multipliying by nonsingular diagonal matrices. We combine these with an algorithm for finding a sparsest basis of the null space of a forest to provide an optimal time algorithm for finding a sparsest basis of the null space of acyclic matrices with $$0$$ in the diagonal.

• Research article
On the distance spectrum of certain distance biregular graphs
Miriam Abdón, Tayná Lobo, and Renata Del-Vecchio
In this article we present an infinite family of bipartite distance biregular graphs having an arbitrarily large diameter and whose distance matrices have exactly four distinct eigenvalues. This result answers a question posed by F. Atik and P. Panigrahi in On the distance spectrum of distance regular graphs (Linear Algebra and its Applications, 478 (2015), pp. 256-273) about the existence of connected graphs with diameter $$d$$ that are not distance regular, whose distance matrix has less than $$d + 1$$ distinct eigenvalues.

• Research article
Incidence and Laplacian matrices of wheel graphs and their inverses
It has been an open problem to find the Moore-Penrose inverses of the incidence, Laplacian, and signless Laplacian matrices of families of graphs except trees and unicyclic graphs. Since the inverse formulas for an odd unicyclic graph and an even unicyclic graph are quite different, we consider wheel graphs as they are formed from odd or even cycles. In this article we solve the open problem for wheel graphs. This work has an interesting connection to inverses of circulant matrices.

• 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.