Answers are grounded in this paper and cite their sources.
The symmetric nonnegative trifactorization of matrices motivates the study of the SNT-rank of graphs. We focus on the family of graphs characterized by three forbidden closed $4$-walks and show that the calculation of the SNT-rank of graphs from this family can be formulated as an optimization problem for star covers on graphs. Unlike traditional optimization that minimizes the number of stars, our objective is to minimize the number of components used in the cover, where each star is a join of two components. We introduce a graph parameter gap(G) and show that for a graph G from the family in question it is equal to the difference between the number of vertices in the graph and the minimal number of components needed in any star cover of G. We develop an algorithm for computing gap(G) consisting of three main steps: (1) transformation of G to a weighted multigraph Γ, (2) reduction of Γ to a multigraph τ(Γ) with all edge weights equal to $0$ and all vertex degrees at least three, (3) iterative process for computing gap(G) by removing vertices in τ(Γ). While steps (1) and (2) are straightforward and control the gap, step (3) is computationally complex but allows us to compute the gap for any graph in the considered family.
No takes yet. Share an insight, caveat, or question.
Bukovšek et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: