A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$, the $X$-eccentricity $e_X\left(v\right)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$-colored vertex furthest from $v$. The minimum $X$-eccentricity among the vertices of $G$ is the $X$-radius ${\mathrm{r}ad}_{X}G$ of $G$...

The signed total domination number of a graph is a certain variant of the domination number. If $v$ is a vertex of a graph $G$, then $N\left(v\right)$ is its oper neighbourhood, i.e. the set of all vertices adjacent to $v$ in $G$. A mapping $f:V\left(G\right)\to \{-1,1\}$, where $V\left(G\right)$ is the vertex set of $G$, is called a signed total dominating function (STDF) on $G$, if ${\sum }_{x\in N\left(v\right)}f\left(x\right)\ge 1$ for each $v\in V\left(G\right)$. The minimum of values ${\sum }_{x\in V\left(G\right)}f\left(x\right)$, taken over all STDF’s of $G$, is called the signed total domination number of $G$ and denoted by ${\gamma }_{\mathrm{s}t}\left(G\right)$. A theorem stating lower bounds for ${\gamma }_{\mathrm{s}t}\left(G\right)$ is...

Let V₁, V₂ be a partition of the vertex set in a graph G, and let ${\gamma }_i$ denote the least number of vertices needed in G to dominate $V_i$. We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest...

Let $G=(V,E)$ be a simple graph. A $3$-valued function $fV\left(G\right)\to \{-1,0,1\}$ is said to be a minus dominating function if for every vertex $v\in V$, $f\left(N\left[v\right]\right)={\sum }_{u\in N\left[v\right]}f\left(u\right)\ge 1$, where $N\left[v\right]$ is the closed neighborhood of $v$. The weight of a minus dominating function $f$ on $G$ is $f\left(V\right)={\sum }_{v\in V}f\left(v\right)$. The minus domination number of a graph $G$, denoted by ${\gamma }^{-}\left(G\right)$, equals the minimum weight of a minus dominating function on $G$. In this paper, the following two results are obtained. (1) If $G$ is a bipartite graph of order $n$, then $${\gamma }^{-}\left(G\right)\ge 4\left(\sqrt{n+1}-1\right)-n.$$ (2) For any negative integer $k$ and any positive integer...

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class $C_f$ of all finite undirected graphs. If G is a graph from $C_f$, then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

A graph $G$ is a $\{d,d+k\}$-graph, if one vertex has degree $d+k$ and the remaining vertices of $G$ have degree $d$. In the special case of $k=0$, the graph $G$ is $d$-regular. Let $k,p\ge 0$ and $d,n\ge 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected $\{d,d+k\}$-graph of order $n$ without a matching $M$ of size $2\left|M\right|=n-p$, then we show in this paper the following: If $d=2$, then $k\ge 2(p+2)$ and (i) $n\ge k+p+6$. If $d\ge 3$ is odd and $t$ an integer with $1\le t\le p+2$, then (ii) $n\ge d+k+1$ for $k\ge d(p+2)$, (iii) $n\ge d(p+3)+2t+1$ for $d(p+2-t)+t\le k\le d(p+3-t)+t-3$, (iv) $n\ge d(p+3)+2p+7$ for $k\le p$. If $d\ge 4$ is even, then (v) $n\ge d+k+2-\eta$ for $k\ge d(p+3)+p+4+\eta$, (vi) $n\ge d+k+p+2-2t=d(p+4)+p+6$ for $k=d(p+3)+4+2t$ and $p\ge 1$,...