The concept of the \textit{ 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: \begin{ equation*} \sup\limits_{ W} \frac{ \alpha(G \boxtimes W)}{ \alpha(H \boxtimes W)} \end{ equation*} 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.
Categories: math.CO cs.IT math.IT