20.500.12556/DiRROS-21650 Induced matching vs edge open packing: trees and product graphs Given a graph $G$, the maximum size of an induced subgraph of $G$ each component of which is a star is called the edge open packing number, $\rho_{e}^{o} (G)$, of $G$. Similarly, the maximum size of an induced subgraph of $G$ each component of which is the star $K_{1,1}$ is the induced matching number, $\nu_I(G)$, of $G$. While the inequality $\rho_{e}^{o}(G)\ge \nu_I(G)$ clearly holds for all graphs $G$, we provide a structural characterization of those trees that attain the equality. We prove that the induced matching number of the lexicographic product $G\circ H$ of arbitrary two graphs $G$ and $H$ equals $\alpha(G)\nu_I(H)$. By similar techniques, we prove sharp lower and upper bounds on the edge open packing number of the lexicographic product of graphs, which in particular lead to NP-hardness results in triangular graphs for both invariants studied in this paper. For the direct product $G\times H$ of two graphs we provide lower bounds on $\nu_I(G\times H)$ and $\rho_{e}^{o} (G\times H)$, both of which are widely sharp. We also present sharp lower bounds for both invariants in the Cartesian and the strong product of two graphs. Finally, we consider the edge open packing number in hypercubes establishing the exact values of $\rho_{e}^{o} (Q_n)$ when $n$ is a power of $2$, and present a closed formula for the induced matching number of the rooted product of arbitrary two graphs over an arbitrary root vertex. induced matching edge open packing graph product independent set trees krepko prirejanje povezavno odprto pakiranje produkt grafov neodvisna množica drevesa true false true Angleški jezik Slovenski jezik Neznano 2025-03-07 10:36:43 2025-03-07 10:36:44 2025-03-08 03:36:22 0000-00-00 00:00:00 2025 0 0 19 str. iss. 7, [article no.] 114458 Vol. 348 Jul. 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2025-07-01 519.17 0012-365X 10.1016/j.disc.2025.114458 228279299 1-s2.0-S0012365X25000664-main.pdf 1-s2.0-S0012365X25000664-main.pdf 1 F5B697A4617658BF62597C7B73BB4F22 4a5a90ca211fa42546a5186e3b161065ae1df95522ba7ba642004bf5ba137c27 34f4f0bc-fb38-11ef-88ed-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=31021 https://www.sciencedirect.com/science/article/pii/S0012365X25000664 1 b04e94a1-fb37-11ef-88ed-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=31020 Inštitut za matematiko, fiziko in mehaniko 0 0 0