Chartrand et al. (2004) have given an upper bound for the nearly antipodal chromatic number $a{c}^{\text{'}}\left(P_n\right)$ as $\left(\genfrac{}{}{0pt}{}{n-2}{2}\right)+2$ for $n\ge 9$ and have found the exact value of $a{c}^{\text{'}}\left(P_n\right)$ for $n=5,6,7,8$. Here we determine the exact values of $a{c}^{\text{'}}\left(P_n\right)$ for $n\ge 8$. They are $2p^2-6p+8$ for $n=2p$ and $2p^2-4p+6$ for $n=2p+1$. The exact value of the radio antipodal number $ac\left(P_n\right)$ for the path $P_n$ of order $n$ has been determined by Khennoufa and Togni in 2005 as $2p^2-2p+3$ for $n=2p+1$ and $2p^2-4p+5$ for $n=2p$. Although the value of $ac\left(P_n\right)$ determined there is correct, we found a mistake in the proof of the lower bound when $n=2p$ (Theorem...

A graph $G$ is a stratified graph if its vertex set is partitioned into classes (each of which is a stratum or a color class). A stratified graph with $k$ strata is $k$-stratified. If $G$ is a connected $k$-stratified graph with strata $S_i$ $(1\le i\le k)$ where the vertices of $S_i$ are colored $X_i$ $(1\le i\le k)$, then the $X_i$-proximity ${\rho }_{X_i}\left(v\right)$ of a vertex $v$ of $G$ is the distance between $v$ and a vertex of $S_i$ closest to $v$. The strati-eccentricity $se\left(v\right)$ of $v$ is $max\{{\rho }_{X_i}\left(v\right)\mid 1\le i\le k\}$. The minimum strati-eccentricity over all vertices...

The signed distance-$k$-domination number of a graph is a certain variant of the signed domination number. If $v$ is a vertex of a graph $G$, the open $k$-neighborhood of $v$, denoted by $N_k\left(v\right)$, is the set $N_k\left(v\right)=\{u\mid u\ne v$ and $d(u,v)\le k\}$. $N_k\left[v\right]=N_k\left(v\right)\cup \left\{v\right\}$ is the closed $k$-neighborhood of $v$. A function $fV\to \{-1,1\}$ is a signed distance-$k$-dominating function of $G$, if for every vertex $v\in V$, $f\left(N_k\left[v\right]\right)={\sum }_{u\in N_k\left[v\right]}f\left(u\right)\ge 1$. The signed distance-$k$-domination number, denoted by ${\gamma }_{k,s}\left(G\right)$, is the minimum weight of a signed distance-$k$-dominating function on $G$. The values of ${\gamma }_{2,s}\left(G\right)$ are found for graphs...

A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number $\chi {*}_r\left(G\right)$ of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that $\chi {*}_r\left(Pₙ\right)<3log₂n$ for n ≥ 2....

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$,...