Let G = (V,E) be a simple, undirected graph. A set of vertices D is called an odd dominating set if |N[v] ∩ D| ≡ 1 (mod 2) for every vertex v ∈ V(G). The minimum cardinality of an odd dominating set is called the odd domination number of G, denoted by γ₁(G). In this paper, several algorithmic and structural results are presented on this parameter for grids, complements of powers of cycles, and other graph classes as well as for more general forms of "residue" domination.

A set S is an offensive alliance if for every vertex v in its boundary N(S)- S it holds that the majority of vertices in v's closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number...

One of numerical invariants concerning domination in graphs is the $k$-subdomination number ${\gamma }_{kS}^{-11}\left(G\right)$ of a graph $G$. A conjecture concerning it was expressed by J. H. Hattingh, namely that for any connected graph $G$ with $n$ vertices and any $k$ with $\frac{1}{2}n<k\leqq n$ the inequality ${\gamma }_{kS}^{-11}\left(G\right)\leqq 2k-n$ holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and $k=5$.

The aim of the paper is to show that no simple graph has a proper subgraph with the same neighborhood hypergraph. As a simple consequence of this result we infer that if a clique hypergraph $𝒢$ and a hypergraph $\mathscr{H}$ have the same neighborhood hypergraph and the neighborhood relation in $𝒢$ is a subrelation of such a relation in $\mathscr{H}$, then $\mathscr{H}$ is inscribed into $𝒢$ (both seen as coverings). In particular, if $\mathscr{H}$ is also a clique hypergraph, then $\mathscr{H}=𝒢$.

We partially strengthen a result of Shelah from [Sh] by proving that if $\kappa ={\kappa }^{\omega }$ and $P$ is a CCC partial order with e.g. $\left|P\right|\le {\kappa }^{+\omega }$ (the ${\omega }^{\text{th}}$ successor of $\kappa$) and $\left|P\right|\le 2^{\kappa }$ then $P$ is $\kappa$-linked.

A co-biclique of a simple undirected graph G = (V,E) is the edge-set of two disjoint complete subgraphs of G. (A co-biclique is the complement of a biclique.) A subset F ⊆ E is an independent of G if there is a co-biclique B such that F ⊆ B, otherwise F is a dependent of G. This paper describes the minimal dependents of G. (A minimal dependent is a dependent C such that any proper subset of C is an independent.) It is showed that a minimum-cost dependent set of G can be determined in polynomial...

In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and are investigated...

For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.

Let $G$ be a simple graph. A subset $S\subseteq V$ is a dominating set of $G$, if for any vertex $v\in V-S$ there exists a vertex $u\in S$ such that $uv\in E\left(G\right)$. The domination number, denoted by $\gamma \left(G\right)$, is the minimum cardinality of a dominating set. In this paper we prove that if $G$ is a 4-regular graph with order $n$, then $\gamma \left(G\right)\le \frac{4}{11}n$.

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number ${\gamma }_{\times 2}\left(G\right)$. A function f(p) is defined, and it is shown that ${\gamma }_{\times 2}\left(G\right)=minf\left(p\right)$, where the minimum is taken over the n-dimensional cube $Cⁿ=p=(p₁,...,pₙ)|p_i\in IR,0\le p_i\le 1,i=1,...,n$. Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then ${\gamma }_{\times 2}\left(G\right)\le ((ln(1+d)+ln\delta +1)/\delta )n$.

We estimate the number of possible degree patterns of k-lacunary polynomials of degree t < p which split completely modulo p. The result is based on a combination of a bound on the number of zeros of lacunary polynomials with some graph theory arguments.

A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices of the...

Let be a set of graphs and for a graph G let ${\alpha }_{}\left(G\right)$ and $\alpha {*}_{}\left(G\right)$ denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on ${\alpha }_{}\left(G\right)$ and $\alpha {*}_{}\left(G\right)$ are presented.

In this paper we derive necessary and sufficient conditions for the existence of kernels by monochromatic paths in the corona of digraphs. Using these results, we are able to prove the main result of this paper which provides necessary and sufficient conditions for the corona of digraphs to be monochromatic kernel-perfect. Moreover we calculate the total numbers of kernels by monochromatic paths, independent by monochromatic paths sets and dominating by monochromatic paths sets in this digraphs...

In [5] the necessary and sufficient conditions for the existence of (k,l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k,l)-kernels, k-independent sets and l-dominating sets in a D-join of digraphs.

A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $\gamma {ₜ}^L\left(G\right)$ and $\gamma {ₜ}^D\left(G\right)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total...

A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number ${\gamma }_L\left(G\right)$ is the minimum cardinality of a LDS of G, and the upper locating-domination number, ${\Gamma }_L\left(G\right)$ is the maximum cardinality of a minimal LDS of G. We present different bounds on ${\Gamma }_L\left(G\right)$ and ${\gamma }_L\left(G\right)$.