1. Best possible upper bounds on the restrained domination number of cubic graphsBoštjan Brešar, Michael A. Henning, 2024, original scientific article Abstract: 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$. Keywords: domination, restrained domination, cubic graphs Published in DiRROS: 18.06.2024; Views: 139; Downloads: 129 Full text (2,13 MB) This document has many files! More... |
2. Cubic vertex-transitive graphs admitting automorphisms of large orderPrimož Potočnik, Micael Toledo, 2023, original scientific article Abstract: A connected graph of order $n$ admitting a semiregular automorphism of order $n/k$ is called a $k$-multicirculant. Highly symmetric multicirculants of small valency have been extensively studied, and several classification results exist for cubic vertex- and arc-transitive multicirculants. In this paper, we study the broader class of cubic vertex-transitive graphs of order $n$ admitting an automorphism of order $n/3$ or larger that may not be semiregular. In particular, we show that any such graph is either a $k$-multicirculant for some $k \le 3$, or it belongs to an infinite family of graphs of girth $6$. Keywords: cubic vertex-transitive graphs, multicirculants, automorphisms of large order Published in DiRROS: 18.03.2024; Views: 273; Downloads: 126 Full text (929,04 KB) This document has many files! More... |
3. On the structure of consistent cycles in cubic symmetric graphsKlavdija Kutnar, Dragan Marušič, Štefko Miklavič, Primož Šparl, 2024, original scientific article Keywords: 1/2-consistent cycles, automorphisms, consistent cycles, cubic symmetric graphs, shunt, s-regular graphs Published in DiRROS: 13.03.2024; Views: 269; Downloads: 149 Full text (1,02 MB) This document has many files! More... |
4. On orders of automorphisms of vertex-transitive graphsPrimož Potočnik, Micael Toledo, Gabriel Verret, 2024, original scientific article Abstract: In this paper we investigate orders, longest cycles and the number of cycles of automorphisms of finite vertex-transitive graphs. In particular, we show that the order of every automorphism of a connected vertex-transitive graph with $n$ vertices and of valence $d$, $d\le 4$, is at most $c_d n$ where $c_3=1$ and $c_4 = 9$. Whether such a constant $c_d$ exists for valencies larger than $4$ remains an unanswered question. Further, we prove that every automorphism $g$ of a finite connected $3$-valent vertex-transitive graph $\Gamma$, $\Gamma \not\cong K_{3,3}$, has a regular orbit, that is, an orbit of $\langle g \rangle$ of length equal to the order of $g$. Moreover, we prove that in this case either $\Gamma$ belongs to a well understood family of exceptional graphs or at least $5/12$ of the vertices of $\Gamma$ belong to a regular orbit of $g$. Finally, we give an upper bound on the number of orbits of a cyclic group of automorphisms $C$ of a connected $3$-valent vertex-transitive graph $\Gamma$ in terms of the number of vertices of $\Gamma$ and the length of a longest orbit of $C$. Keywords: graphs, automorphism groups, vertex-transitive, regular orbit, cubic, tetravalent Published in DiRROS: 19.02.2024; Views: 395; Downloads: 163 Full text (573,20 KB) This document has many files! More... |
5. Partial domination in supercubic graphsCsilla Bujtás, Michael A. Henning, Sandi Klavžar, 2024, original scientific article Abstract: 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$. Keywords: domination, partial domination, cubic graphs, supercubic graphs Published in DiRROS: 15.02.2024; Views: 358; Downloads: 136 Full text (304,87 KB) This document has many files! More... |