1. Best possible upper bounds on the restrained domination number of cubic graphsBoštjan Brešar, Michael A. Henning, 2024, izvirni znanstveni članek Povzetek: A dominating set in a graph $G$ is a set $S$ of vertices such that every vertex in $V(G) \setminus S$ is adjacent to a vertex in $S$. A restrained dominating set of $G$ is a dominating set $S$ with the additional restraint that the graph $G - S$ obtained by removing all vertices in $S$ is isolate-free. The domination number $\gamma(G)$ and the restrained domination number $\gamma_{r}(G)$ are the minimum cardinalities of a dominating set and restrained dominating set, respectively, of $G$. Let $G$ be a cubic graph of order $n$. A classical result of Reed [Combin. Probab. Comput. 5 (1996), 277-295] states that $\gamma(G) \le \frac{3}{8}n$, and this bound is best possible. To determine a best possible upper bound on the restrained domination number of $G$ is more challenging, and we prove that $\gamma_{r}(G) \le \frac{2}{5}n$.
Ključne besede: domination, restrained domination, cubic graphs
Objavljeno v DiRROS: 18.06.2024; Ogledov: 79; Prenosov: 63
 Celotno besedilo (2,13 MB)
Gradivo ima več datotek! Več... |
2. Resolvability and convexity properties in the Sierpiński product of graphsMichael A. Henning, Sandi Klavžar, Ismael G. Yero, 2024, izvirni znanstveni članek Povzetek: Let $G$ and $H$ be graphs and let $f \colon V(G)\rightarrow V(H)$ be a function. The Sierpiński product of $G$ and $H$ with respect to $f$, denoted by $G \otimes _f H$, is defined as the graph on the vertex set $V(G)\times V(H)$, consisting of $|V(G)|$ copies of $H$; for every edge $gg'$ of $G$ there is an edge between copies $gH$ and $g'H$ of $H$ associated with the vertices $g$ and $g'$ of $G$, respectively, of the form $(g,f(g'))(g',f(g))$. The Sierpiński metric dimension and the upper Sierpiński metric dimension of two graphs are determined. Closed formulas are determined for Sierpiński products of trees, and for Sierpiński products of two cycles where the second factor is a triangle. We also prove that the layers with respect to the second factor in a Sierpiński product graph are convex.
Ključne besede: Sierpiński product of graphs, metric dimension, trees, convex subgraph
Objavljeno v DiRROS: 16.02.2024; Ogledov: 288; Prenosov: 126
Celotno besedilo (432,07 KB)
Gradivo ima več datotek! Več... |
3. Partial domination in supercubic graphsCsilla Bujtás, Michael A. Henning, Sandi Klavžar, 2024, izvirni znanstveni članek Povzetek: For some $\alpha$ with $0 < \alpha \le 1$, a subset $X$ of vertices in a graph $G$ of order $n$ is an $\alpha$-partial dominating set of $G$ if the set $X$ dominates at least $\alpha \times n$ vertices in $G$. The $\alpha$-partial domination number ${\rm pd}_{\alpha}(G)$ of $G$ is the minimum cardinality of an $\alpha$-partial dominating set of $G$. In this paper partial domination of graphs with minimum degree at least $3$ is studied. It is proved that if $G$ is a graph of order $n$ and with $\delta(G)\ge 3$, then ${\rm pd}_{\frac{7}{8}}(G) \le \frac{1}{3}n$. If in addition $n\ge 60$, then ${\rm pd}_{\frac{9}{10}}(G) \le \frac{1}{3}n$, and if $G$ is a connected cubic graph of order $n\ge 28$, then ${\rm pd}_{\frac{13}{14}}(G) \le \frac{1}{3}n$. Along the way it is shown that there are exactly four connected cubic graphs of order $14$ with domination number $5$.
Ključne besede: domination, partial domination, cubic graphs, supercubic graphs
Objavljeno v DiRROS: 15.02.2024; Ogledov: 276; Prenosov: 108
Celotno besedilo (304,87 KB)
Gradivo ima več datotek! Več... |
