2021/04/15 by Florin Catrina, Catrina, Florin, Rainah Khan +7
Computer Science · Mathematics · #68W25 #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Limits and Structures in Graph Theory #Primary: 05C05 #Secondary: 05C38
paper · pdf · doi:10.48550/arxiv.2104.07872
openalex publication_date 2021/04/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The main goal of this article is to introduce new quantitative characteristics of cycles in finite simple connected graphs and to establish relations of these characteristics with the stretch and spanning tree congestion of graphs. The main new parameter is named the support number. We give a polynomial approximation algorithm for the support number with the aid of yet another characteristic we introduce, named the cycle width of the graph.