The study of domination in Cartesian products has received its main motivation from attempts to settle a conjecture made by V.G. Vizing in 1968. He conjectured that γ(G)γ(H) is a lower bound for the domination number of the Cartesian product of any two graphs G and H. Most of the progress on settling this conjecture has been limited to verifying the conjectured lower bound if one of the graphs has a certain structural property. In addition, a number of authors have established bounds for dominating...

A set S ⊆ V of vertices in a graph G = (V, E) is called a dominating set if every vertex in V-S is adjacent to a vertex in S. A dominating set which intersects every maximum independent set in G is called an independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of G and is denoted by ${\gamma }_{it}\left(G\right)$. In this paper we begin an investigation of this parameter.

A subset $D$ of the vertex set $V\left(G\right)$ of a graph $G$ is called dominating in $G$, if each vertex of $G$ either is in $D$, or is adjacent to a vertex of $D$. If moreover the subgraph $<D>$ of $G$ induced by $D$ is regular of degree 1, then $D$ is called an induced-paired dominating set in $G$. A partition of $V\left(G\right)$, each of whose classes is an induced-paired dominating set in $G$, is called an induced-paired domatic partition of $G$. The maximum number of classes of an induced-paired domatic partition of $G$ is the induced-paired domatic...

Let $f$ be an integer-valued function defined on the vertex set $V\left(G\right)$ of a graph $G$. A subset $D$ of $V\left(G\right)$ is an $f$-dominating set if each vertex $x$ outside $D$ is adjacent to at least $f\left(x\right)$ vertices in $D$. The minimum number of vertices in an $f$-dominating set is defined to be the $f$-domination number, denoted by ${\gamma }_f\left(G\right)$. In a similar way one can define the connected and total $f$-domination numbers ${\gamma }_{c,f}\left(G\right)$ and ${\gamma }_{t,f}\left(G\right)$. If $f\left(x\right)=1$ for all vertices $x$, then these are the ordinary domination number, connected domination number and total domination...

We study the thresholds for the emergence of various properties in random subgraphs of (ℕ, <). In particular, we give sharp sufficient conditions for the existence of (finite or infinite) cliques and paths in a random subgraph. No specific assumption on the probability is made. The main tools are a topological version of Ramsey theory, exchangeability theory and elementary ergodic theory.

In this paper, we consider the intersection graph $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$ of gamma sets in the total graph on ℤₙ. We characterize the values of n for which $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$ is complete, bipartite, cycle, chordal and planar. Further, we prove that $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$ is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$.

In this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is NP-complete, and they asked if Xii(G) ≤ 2Δ(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with Δ(G) = 3.