Advanced Search

The directed distance $d(u,v)$ from $u$ to $v$ in a strong digraph $D$ is the length of a shortest $u-v$ path in $D$. The eccentricity $e\left(v\right)$ of a vertex $v$ in $D$ is the directed distance from $v$ to a vertex furthest from $v$ in $D$. The center and periphery of a strong digraph are two well known subdigraphs induced by those vertices of minimum and maximum eccentricities, respectively. We introduce the interior and annulus of a digraph which are two induced subdigraphs involving the remaining vertices. Several results concerning...

The Traveling Salesman Problem (TSP) is still one of the most researched topics in computational mathematics, and we introduce a variant of it, namely the study of the closed k-walks in graphs. We search for a shortest closed route visiting k cities in a non complete graph without weights. This motivates the following definition. Given a set of k distinct vertices = x₁, x₂, ...,xₖ in a simple graph G, the closed k-stop-distance of set is defined to be $dₖ\left(\right)=mi{n}_{\Theta \in \left(\right)}(d(\Theta \left(x₁\right),\Theta \left(x₂\right))+d(\Theta \left(x₂\right),\Theta \left(x₃\right))+...+d(\Theta \left(xₖ\right),\Theta \left(x₁\right)))$, where () is the set of all permutations from...

Explicit formulae for the γ-min and γ-max labeling values of complete bipartite graphs are given, along with γ-labelings which achieve these extremes. A recursive formula for the γ-min labeling value of any complete multipartite is also presented.

The (directed) distance from a vertex $u$ to a vertex $v$ in a strong digraph $D$ is the length of a shortest $u$-$v$ (directed) path in $D$. The eccentricity of a vertex $v$ of $D$ is the distance from $v$ to a vertex furthest from $v$ in $D$. The radius rad$D$ is the minimum eccentricity among the vertices of $D$ and the diameter diam$D$ is the maximum eccentricity. A central vertex is a vertex with eccentricity $\mathrm{r}adD$ and the subdigraph induced by the central vertices is the center $C\left(D\right)$. For a central vertex $v$ in a strong digraph...

P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi, in Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004), 157–177, and T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, in Global defensive alliances in graphs, Electron. J. Combin. 10 (2003), introduced the defensive alliance number $a\left(G\right)$, strong defensive alliance number $\widehat{a}\left(G\right)$, and global defensive alliance number ${\gamma }_a\left(G\right)$. In this paper, we consider relationships between these parameters and the domination number $\gamma \left(G\right)$. For any positive integers...

The eccentricity of a vertex $v$ of a connected graph $G$ is the distance from $v$ to a vertex farthest from $v$ in $G$. The center of $G$ is the subgraph of $G$ induced by the vertices having minimum eccentricity. For a vertex $v$ in a 2-edge-connected graph $G$, the edge-deleted eccentricity of $v$ is defined to be the maximum eccentricity of $v$ in $G-e$ over all edges $e$ of $G$. The edge-deleted center of $G$ is the subgraph induced by those vertices of $G$ having minimum edge-deleted eccentricity. The edge-deleted central...