| Naslov: | Induced matching vs edge open packing: trees and product graphs |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Dravec, Tanja (Avtor)
ID Hedžet, Jaka (Avtor)
ID Samadi, Babak (Avtor) |
|---|
| Datoteke: |  RAZ_Bresar_Bostjan_2025.pdf (1,31 MB)
MD5: 5063B28258C11C9B62A33E78975BA693
 https://doi.org/10.1016/j.disc.2025.114458
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Znanstveno delo |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | induced matching, edge open packing, graph product, independent set, trees |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Poslano v recenzijo: | 15.09.2024 |
|---|
| Datum sprejetja članka: | 22.02.2025 |
|---|
| Datum objave: | 04.03.2025 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 19 str. |
|---|
| Številčenje: | Letn. 348, št. 7, št. članka 114458 |
|---|
| PID: | 20.500.12556/DKUM-91972  |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 228279299 |
|---|
| DOI: | 10.1016/j.disc.2025.114458 |
|---|
| ISSN pri članku: | 0012-365X |
|---|
| Datum objave v DKUM: | 25.07.2025 |
|---|
| Število ogledov: | 185 |
|---|
| Število prenosov: | 10 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
