Optimization Problem for Star Covers of Graphs without Four Cycles
The Electronic Journal of Combinatorics · 20.11.2026 · 33 (4)
DOI: 10.37236/15642 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 20.11.2026. Verfasst von Damjana Kokol Bukovšek und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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 $\operatorname{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 $\operatorname{gap}(G)$ consisting of three main steps: (1) transformation of $G$ to a weighted multigraph $\Gamma$, (2) reduction of $\Gamma$ to a multigraph $\tau(\Gamma)$ with all edge weights equal to $0$ and all vertex degrees at least three, (3) iterative process for computing $\operatorname{gap}(G)$ by removing vertices in $\tau(\Gamma)$. While steps (1) and (2) are straightforward and control the $\operatorname{gap}$, step (3) is computationally complex but allows us to compute the $\operatorname{gap}$ for any graph in the considered family.
Zitieren
APA
Bukovšek, D. K., Oblak, P., & Šmigoc, H. (2026). Optimization Problem for Star Covers of Graphs without Four Cycles. The Electronic Journal of Combinatorics, 33(4). https://doi.org/10.37236/15642
Vancouver
Bukovšek DK, Oblak P, Šmigoc H. Optimization Problem for Star Covers of Graphs without Four Cycles. The Electronic Journal of Combinatorics. 2026;33(4). doi:10.37236/15642
BibTeX
@article{Bukovek2026,
author = {Bukovšek, Damjana Kokol and Oblak, Polona and Šmigoc, Helena},
title = {Optimization Problem for Star Covers of Graphs without Four Cycles},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {4},
doi = {10.37236/15642}
}
EUVIMED