Relative Fractional Packing Number and Its Properties

2023/11/28 by Mehrshad Taziki, Taziki, Mehrshad
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Information Theory (cs.IT) #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2311.16390

openalex publication_date 2023/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The concept of the relative fractional packing number between two graphs G and H, initially introduced in arXiv:2307.06155 [math.CO], serves as an upper bound for the ratio of the zero-error Shannon capacity of these graphs. Defined as: sup_W (α(G \boxtimes W))/(α(H \boxtimes W)) where the supremum is computed over all arbitrary graphs and \boxtimes denotes the strong product of graphs. This article delves into various critical theorems regarding the computation of this number. Specifically, we address its NP-hardness and the complexity of approximating it. Furthermore, we develop a conjecture for necessary and sufficient conditions for this number to be less than one. We also validate this conjecture for specific graph families. Additionally, we present miscellaneous concepts and introduce a generalized version of the independence number that gives insights that could significantly contribute to the study of the relative fractional packing number.

Related

• On the Ratio of Shannon Numbers of Graphs
• Integer and fractional packing of families of graphs
• A group-theoretic approach to Shannon capacity of graphs and a limit theorem from lattice packings
• On a fractional version of Haemers' bound
• Asymptotically optimal K_k-packings of dense graphs via fractional K_k-decompositions