20.500.12556/DKUM-91972 Induced matching vs edge open packing: trees and product graphs Krepko prirejanje vs povezavno odprto pakiranje: drevesa in produkti grafov 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. Naj bo dan graf ▫$G$▫. Največji red induciranega podgrafa grafa ▫$G$▫, katerega vsaka komponenta je zvezda, se imenuje število povezavnega odprtega pakiranja grafa ▫$G$▫, označimo pa ga z ▫$\rho_{e}^{o} (G)$▫. Največji red induciranega podgrafa grafa ▫$G$▫, katerega vsaka komponenta je zvezda ▫$K_{1,1}$▫ pa se imenuje število krepkega prirejanja grafa ▫$G$▫ in se označi z ▫$\nu_I(G)$▫. Medtem, ko je neenakost ▫$\rho_{e}^{o}(G)\ge\nu_I(G)$▫ očitna, v članku dokažemo strukturno karakterizacijo tistih dreves, ki dosežejo enakost. Dokažemo, da je število krepkega prirejanja leksikografskega produkta ▫$G\circ H$▫ poljubnih grafov ▫$G$▫ in ▫$H$▫ enako ▫$\alpha(G)\nu_I(H)$▫. S podobnimi metodami dokažemo natančne spodnje in zgornje meje za število povezavnega odprtega pakiranja leksikografskega produkta grafov, ki med drugim vodijo do rezultata o NP-polnosti v triangularnih grafih za obe osrednji invarianti tega članka. Za direktni produkt ▫$G\times H$▫ dveh grafov dokažemo spodnji meji za ▫$\nu_I(G\times H)$▫ in ▫$\rho_{e}^{o} (G\times H)$▫, ki sta doseženi za velike družine grafov. Prav tako predstavimo natančne spodnje meje za obe invarianti v kartezičnem in krepkem produktu dveh grafov. Nazadnje obravnavamo število povezavnega odprtega pakiranja v hiperkockah, kjer dobimo točne vrednosti za ▫$\rho_{e}^{o} (Q_n)$▫ v primeru, ko je ▫$n$▫ potenca števila ▫$2$▫, predstavimo pa tudi zaprto formulo za število krepkega prirejanja v korenskem produktu poljubnih dveh grafov, kjer je koren poljubno izbrano vozlišče. 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 Znanstveno delo 2025-03-09 05:01:21 2025-07-25 11:46:35 2025-07-26 03:14:14 0000-00-00 00:00:00 2025 0 0 19 str. št. 7, št. članka 114458 Letn. 348 Jul. 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2024-09-15 2025-02-22 2025-03-04 519.17 228279299 10.1016/j.disc.2025.114458 0012-365X RAZ_Bresar_Bostjan_2025.pdf RAZ_Bresar_Bostjan_2025.pdf 1 5063B28258C11C9B62A33E78975BA693 ca8e03cdee6316684319e2cd371fa455d46acbdbddc307ad9800c3bf021db390 33083312-693d-11f0-b339-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=194166 https://doi.org/10.1016/j.disc.2025.114458 0 472b2854-693d-11f0-b339-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=194167 Fakulteta za naravoslovje in matematiko 0 0 0