Optimization Problem for Star Covers of Graphs without Four Cycles

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.

Authors

Publication Details

Journal
The Electronic Journal of Combinatorics
Published
2026-11-20
DOI
https://doi.org/10.37236/15642
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Optimization Problem for Star Covers of Graphs without Four Cycles

Polona Oblak, Helena Šmigoc, Damjana Kokol Bukovšek
1 links
The Electronic Journal of Combinatorics
Advanced Graph Theory Research
article

Optimization Problem for Star Covers of Graphs without Four Cycles

Polona Oblak, Helena Šmigoc, Damjana Kokol Bukovšek
article en

Abstract

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.

The Electronic Journal of CombinatoricsVol. 33(4)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon