Formulas for vertex eccentricity and radius for the n-fold tensor product $G={\otimes }_{i=1}ⁿG_i$ of n arbitrary simple graphs $G_i$ are derived. The center of G is characterized as the union of n+1 vertex sets of form V₁×V₂×...×Vₙ, with $V_i\subseteq V\left(G_i\right)$.

For an ordered set $W=\{w_1,w_2,...,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the ordered $k$-vector $r\left(v\right|W):=(d(v,w_1),d(v,w_2),...,d(v,w_k))$ is called the metric representation of $v$ with respect to $W$, where $d(x,y)$ is the distance between vertices $x$ and $y$. A set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. The minimum cardinality of a resolving set for $G$ is its metric dimension. In this paper, we characterize all graphs of order $n$ with metric dimension $n-3$.

In a graph G, the distance d(u, v) between a pair of vertices u and v is the length of a shortest path joining them. The eccentricity e(u) of a vertex u is the distance to a vertex farthest from u. The minimum eccentricity is called the radius, r(G), of the graph and the maximum eccentricity is called the diameter, d(G), of the graph. The super-radial graph R*(G) based on G has the vertex set as in G and two vertices u and v are adjacent in R*(G) if the distance between them in G is greater than...

As was shown in the book of Mulder [4], the interval function is an important tool for studying metric properties of connected graphs. An axiomatic characterization of the interval function of a connected graph was given by the present author in [5]. (Using the terminology of Bandelt, van de Vel and Verheul [1] and Bandelt and Chepoi [2], we may say that [5] gave a necessary and sufficient condition for a finite geometric interval space to be graphic). In the present paper, the result given in [5]...

In this paper, we show that Qkn is a divisor graph, for n = 2, 3. For n ≥ 4, we show that Qkn is a divisor graph iff k ≥ n − 1. For folded-hypercube, we get FQn is a divisor graph when n is odd. But, if n ≥ 4 is even integer, then FQn is not a divisor graph. For n ≥ 5, we show that (FQn)k is not a divisor graph, where 2 ≤ k ≤ [n/2] − 1.

We use the concept of intrinsic metrics to give a new definition for an isoperimetric constant of a graph. We use this novel isoperimetric constant to prove a Cheeger-type estimate for the bottom of the spectrum which is nontrivial even if the vertex degrees are unbounded.

Circular distance $d^{\circ }(x,y)$ between two vertices $x$, $y$ of a strongly connected directed graph $G$ is the sum $d(x,y)+d(y,x)$, where $d$ is the usual distance in digraphs. Its basic properties are studied.

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

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