Given a connected graph G, a vertex w ∈ V (G) strongly resolves two vertices u, v ∈ V (G) if there exists some shortest u − w path containing v or some shortest v − w path containing u. A set S of vertices is a strong metric generator for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. In this paper we obtain several relationships between the strong metric dimension...

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

Let A = (aij) ∊ Mn(ℝ) be an n by n symmetric stochastic matrix. For p ∊ [1, ∞) and a metric space (X, dX), let γ(A, dpx) be the infimum over those γ ∊ (0,∞] for which every x1, . . . , xn ∊ X satisfy [...] Thus γ (A, dpx) measures the magnitude of the nonlinear spectral gap of the matrix A with respect to the kernel dpX : X × X →[0,∞). We study pairs of metric spaces (X, dX) and (Y, dY ) for which there exists Ψ: (0,∞)→(0,∞) such that γ (A, dpX) ≤Ψ (A, dpY ) for every symmetric stochastic A ∊ Mn(ℝ)...

Let G be a connected graph. Given an ordered set W = {w1, . . . , wk} ⊆ V (G) and a vertex u ∈ V (G), the representation of u with respect to W is the ordered k-tuple (d(u, w1), d(u, w2), . . . , d(u, wk)), where d(u, wi) denotes the distance between u and wi. The set W is a metric generator for G if every two different vertices of G have distinct representations. A minimum cardinality metric generator is called a metric basis of G and its cardinality is called the metric dimension of G. It is well...

For a vertex v of a connected graph G and a subset S of V(G), the distance between v and S is d(v,S) = mind(v,x)|x ∈ S. For an ordered k-partition Π = S₁,S₂,...,Sₖ of V(G), the representation of v with respect to Π is the k-vector r(v|Π) = (d(v,S₁), d(v,S₂),..., d(v,Sₖ)). The k-partition Π is a resolving partition if the k-vectors r(v|Π), v ∈ V(G), are distinct. The minimum k for which there is a resolving k-partition of V(G) is the partition dimension pd(G) of G. A resolving partition Π = S₁,S₂,...,Sₖ...

For an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the representation of $v$ with respect to $W$ is the $k$-vector $r\left(v\right|W)$ = ($d(v,w_1)$, $d(v,w_2),\cdots ,d(v,w_k))$, where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set for $G$ containing a minimum number of vertices is a basis for $G$. The dimension $dim\left(G\right)$ is the number of vertices in a basis for $G$. A resolving set $W$ of $G$ is connected if the subgraph...

For an ordered $k$-decomposition $𝒟=\{G_1,G_2,...,G_k\}$ of a connected graph $G$ and an edge $e$ of $G$, the $𝒟$-code of $e$ is the $k$-tuple $c_{𝒟}\left(e\right)$ = ($d(e,G_1),$$d(e,G_2$

We study two topological properties of the 5-ary $n$-cube $Q_n^5$. Given two arbitrary distinct nodes $x$ and $y$ in $Q_n^5$, we prove that there exists an $x$-$y$ path of every length ranging from $2n$ to $5^n-1$, where $n\ge 2$. Based on this result, we prove that $Q_n^5$ is 5-edge-pancyclic by showing that every edge in $Q_n^5$ lies on a cycle of every length ranging from $5$ to $5^n$.

We study two topological properties of the 5-ary n-cube $Q_n^5$. Given two arbitrary distinct nodes x and y in $Q_n^5$, we prove that there exists an x-y path of every length ranging from 2n to 5n - 1, where n ≥ 2. Based on this result, we prove that $Q_n^5$ is 5-edge-pancyclic by showing that every edge in $Q_n^5$ lies on a cycle of every length ranging from 5 to 5n.

A graph $G$ is degree-continuous if the degrees of every two adjacent vertices of $G$ differ by at most 1. A finite nonempty set $S$ of integers is convex if $k\in S$ for every integer $k$ with $min\left(S\right)\le k\le max\left(S\right)$. It is shown that for all integers $r>0$ and $s\ge 0$ and a convex set $S$ with $min\left(S\right)=r$ and $max\left(S\right)=r+s$, there exists a connected degree-continuous graph $G$ with the degree set $S$ and diameter $2s+2$. The minimum order of a degree-continuous graph with a prescribed degree set is studied. Furthermore, it is shown that for every graph $G$ and convex set $S$ of...

The diameter of a graph $G$ is the maximal distance between two vertices of $G$. A graph $G$ is said to be diameter-edge-invariant, if $d(G-e)=d\left(G\right)$ for all its edges, diameter-vertex-invariant, if $d(G-v)=d\left(G\right)$ for all its vertices and diameter-adding-invariant if $d(G+e)=d\left(e\right)$ for all edges of the complement of the edge set of $G$. This paper describes some properties of such graphs and gives several existence results and bounds for parameters of diameter-invariant graphs.

A set of vertices D of a graph G is a distance 2-dominating set of G if the distance between each vertex u ∊ (V (G) − D) and D is at most two. Let γ2(G) denote the size of a smallest distance 2-dominating set of G. For any permutation π of the vertex set of G, the prism of G with respect to π is the graph πG obtained from G and a copy G′ of G by joining u ∊ V(G) with v′ ∊ V(G′) if and only if v′ = π(u). If γ2(πG) = γ2(G) for any permutation π of V(G), then G is called a universal γ2-fixer. In this...