Browsing by Subject "dominating set"

Now showing 1 - 7 of 7

Access status: Open Access ,
Dominating sets and domination polynomials of certain graphs, II
(2010) Alikhani, Saeid; Peng, Yee Hock
The domination polynomial of a graph $G$ of order $n$ is the polynomial $D(G,x) = \sum _{i=\gamma(G)}^n d(G,i)x^i$, where $d(G,i)$ is the number of dominating sets of $G$ of size $i$, and $\gamma (G)$ is the domination number of $G$. In this paper, we obtain some properties of the coefficients of $D(G,x)$. Also, by study of the dominating sets and the domination polynomials of specific graphs denoted by $G^{\prime}(m)$, we obtain a relationship between the domination polynomial of graphs containing an induced path of length at least three, and the domination polynomial of related graphs obtained by replacing the path by shorter path. As examples of graphs $G^{\prime}(m)$, we study the dominating sets and domination polynomials of cycles and generalized theta graphs. Finally, we show that, if $n \equiv 0,2(mod\, 3)$ and $D(G,x) = D(C_n, x)$, then $G = C_n$.
Access status: Open Access ,
Domination hypergraphs of certain digraphs
(Wydawnictwa AGH, 2010) Sonntag, Martin; Teichert, Hanns-Martin
If $D=(V,A)$ is a digraph, its domination hypergraph $\mathcal{DH}(D) = (V,\mathcal{E})$ has the vertex set $V$ and $e \subseteq V$ is an edge of $\mathcal{DH}(D)$ if and only if e is a minimal dominating set of $D$. We investigate domination hypergraphs of special classes of digraphs, namely tournaments, paths and cycles. Finally, using a special decomposition/composition method we construct edge sets of domination hypergraphs of certain digraphs.
Access status: Restricted ,
Liczby wielokrotnie dominujące graf
(Data obrony: 2012-09-27) Dziewońska, Marta
Wydział Matematyki Stosowanej
Access status: Open Access ,
M₂-edge colorings of dense graphs
(2016) Ivančo, Jaroslav
An edge coloring $\varphi$ of a graph $G$ is called an $\mathrm{M}_i$-edge coloring if $|\varphi(v)|\leq i$ for every vertex $v$ of $G$, where $\varphi(v)$ is the set of colors of edges incident with $v$. Let $\mathcal{K}_i(G)$ denote the maximum number of colors used in an $\mathrm{M}_i$-edge coloring of $G$. In this paper we establish some bounds of $\mathcal{K}_2(G)$, present some graphs achieving the bounds and determine exact values of $\mathcal{K}_2(G)$ for dense graphs.
Access status: Open Access ,
On equality in an upper bound for the acyclic domination number
(2008) Samodivkin, Vladimir
A subset $A$ of vertices in a graph $G$ is acyclic if the subgraph it induces contains no cycles. The acyclic domination number $\gamma_a(G)$ of a graph $G$ is the minimum cardinality of an acyclic dominating set of $G$. For any graph $G$ with $n$ vertices and maximum degree $\Delta(G)$, $\gamma_a(G) \leq n - \Delta(G)$. In this paper we characterize the connected graphs and the connected triangle-free graphs which achieve this upper bound.
Access status: Open Access ,
On minimum intersections of certain secondary dominating sets in graphs
(Wydawnictwa AGH, 2023) Kosiorowska, Anna; Michalski, Adrian; Włoch, Iwona
In this paper we consider secondary dominating sets, also named as $(1,k)$-dominating sets, introduced by Hedetniemi et al. in 2008. In particular, we study intersections of the $(1,1)$-dominating sets and proper $(1,2)$-dominating sets. We introduce $(1,\overline{2})$-intersection index as the minimum possible cardinality of such intersection and determine its value for some classes of graphs.
Access status: Open Access ,
On the existence of independent (1,k) -dominating sets for k∈{1,2} in two products of graphs
(Wydawnictwa AGH, 2026) Bednarz, Paweł; Michalski, Adrian; Paja, Natalia
A subset $J$ of vertices is said to be a $(1,k)$-dominating set if every vertex $v$ not belonging to the set $J$ has a neighbour in $J$ and there exists also another vertex in $J$ within the distance at most $k$ from $v$. In this paper, we study the problem of the existence of independent $(1,k)$-dominating sets for $k\in\{1,2\}$ in the tensor product and in the strong product of two graphs. We give complete characterisations of these graph products, which have independent $(1,1)$-dominating sets or independent $(1,2)$-dominating sets, with respect to the properties of their factors.