Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Browse
New in RUL
About RUL
In numbers
Help
Sign in
Packings in bipartite prisms and hypercubes
ID
Brešar, Boštjan
(
Author
),
ID
Klavžar, Sandi
(
Author
),
ID
Rall, Douglas F.
(
Author
)
PDF - Presentation file,
Download
(231,57 KB)
MD5: BC4297894DBBF84BEE1923433A1D0D53
URL - Source URL, Visit
https://www.sciencedirect.com/science/article/pii/S0012365X24000062
Image galllery
Abstract
The $2$-packing number $\rho_2(G)$ of a graph $G$ is the cardinality of a largest $2$-packing of $G$ and the open packing number $\rho^{\rm o}(G)$ is the cardinality of a largest open packing of $G$, where an open packing (resp. $2$-packing) is a set of vertices in $G$ no two (closed) neighborhoods of which intersect. It is proved that if $G$ is bipartite, then $\rho^{\rm o}(G\Box K_2) = 2\rho_2(G)$. For hypercubes, the lower bounds $\rho_2(Q_n) \ge 2^{n - \lfloor \log n\rfloor -1}$ and $\rho^{\rm o}(Q_n) \ge 2^{n - \lfloor \log (n-1)\rfloor -1}$ are established. These findings are applied to injective colorings of hypercubes. In particular, it is demonstrated that $Q_9$ is the smallest hypercube which is not perfect injectively colorable. It is also proved that $\gamma_t(Q_{2^k}\times H) = 2^{2^k-k}\gamma_t(H)$, where $H$ is an arbitrary graph with no isolated vertices.
Language:
English
Keywords:
2-packing number
,
open packing number
,
bipartite prism
,
hypercube
,
injective coloring
,
total domination number
Work type:
Article
Typology:
1.01 - Original Scientific Article
Organization:
FMF - Faculty of Mathematics and Physics
Publication status:
Published
Publication version:
Version of Record
Year:
2024
Number of pages:
6 str.
Numbering:
Vol. 347, iss. 4, art. 113875
PID:
20.500.12556/RUL-154513
UDC:
519.17
ISSN on article:
0012-365X
DOI:
10.1016/j.disc.2024.113875
COBISS.SI-ID:
181387523
Publication date in RUL:
19.02.2024
Views:
584
Downloads:
32
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
Share:
Record is a part of a journal
Title:
Discrete mathematics
Shortened title:
Discrete math.
Publisher:
Elsevier
ISSN:
0012-365X
COBISS.SI-ID:
1118479
Licences
License:
CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:
http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:
The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Secondary language
Language:
Slovenian
Keywords:
2-pakirno število
,
odprto pakirno število
,
dvodelna prizma
,
hiperkocke
,
injektivno barvanje
,
celotno dominacijsko število
Projects
Funder:
ARRS - Slovenian Research Agency
Project number:
BI-US/22-24-038
Name:
Domination in graphs, digraphs and their products
Funder:
ARRS - Slovenian Research Agency
Project number:
P1-0297
Name:
Teorija grafov
Funder:
ARRS - Slovenian Research Agency
Project number:
J1-2452
Name:
Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov
Funder:
ARRS - Slovenian Research Agency
Project number:
N1-0285
Name:
Metrični problemi v grafih in hipergrafih
Funder:
ARRS - Slovenian Research Agency
Project number:
J1-3002
Name:
Prirejanja in barvanja povezav v kubičnih grafih
Similar documents
Similar works from RUL:
Similar works from other Slovenian collections:
Back