The eccentricity $e\left(v\right)$ of a vertex $v$ is the distance from $v$ to a vertex farthest from $v$, and $u$ is an eccentric vertex for $v$ if its distance from $v$ is $d(u,v)=e\left(v\right)$. A vertex of maximum eccentricity in a graph $G$ is called peripheral, and the set of all such vertices is the peripherian, denoted $PeriG)$. We use $Cep\left(G\right)$ to denote the set of eccentric vertices of vertices in $C\left(G\right)$. A graph $G$ is called an S-graph if $Cep\left(G\right)=Peri\left(G\right)$. In this paper we characterize S-graphs with diameters less or equal to four, give some constructions of S-graphs and...

For two vertices $u$ and $v$ in a connected graph $G$, the set $I(u,v)$ consists of all those vertices lying on a $u-v$ geodesic in $G$. For a set $S$ of vertices of $G$, the union of all sets $I(u,v)$ for $u,v\in S$ is denoted by $I\left(S\right)$. A set $S$ is convex if $I\left(S\right)=S$. The convexity number $\mathrm{c}on\left(G\right)$ is the maximum cardinality of a proper convex set in $G$. A convex set $S$ is maximum if $\left|S\right|=\mathrm{c}on\left(G\right)$. The cardinality of a maximum convex set in a graph $G$ is the convexity number of $G$. For a nontrivial connected graph $H$, a connected graph $G$ is an $H$-convex graph if $G$ contains...

In this paper the following results are proved: 1. Let $P_n$ be a path with $n$ vertices, where $n\ge 5$ and $n\ne 7,8$. Let $M$ be a matching in $P_n$. Then ${\left(P_n\right)}^4-M$ is hamiltonian-connected. 2. Let $G$ be a connected graph of order $p\ge 5$, and let $M$ be a matching in $G$. Then $G^5-M$ is hamiltonian-connected.

For a strong oriented graph D of order n and diameter d and an integer k with 1 ≤ k ≤ d, the kth power $D^k$ of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of $D^k$ if the directed distance ${}^{\to }{d}_D(u,v)$ from u to v in D is at most k. For every strong digraph D of order n ≥ 2 and every integer k ≥ ⌈n/2⌉, the digraph $D^k$ is Hamiltonian and the lower bound ⌈n/2⌉ is sharp. The digraph $D^k$ is distance-colored if each arc (u, v) of $D^k$ is assigned the color i where $i{=}^{\to }{d}_D(u,v)$. The digraph $D^k$ is Hamiltonian-colored...

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. In this paper, the exact formulae for the Harary indices of tensor product G × Km0,m1,...,mr−1 and the strong product G⊠Km0,m1,...,mr−1 , where Km0,m1,...,mr−1 is the complete multipartite graph with partite sets of sizes m0,m1, . . . ,mr−1 are obtained. Also upper bounds for the Harary indices of tensor and strong products of graphs are estabilished. Finally, the exact formula...

It is shown that for a metric space (M,d) the following are equivalent: (i) M is a complete ℝ-tree; (ii) M is hyperconvex and has unique metric segments.

For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)+2$ for every positive integer n, where ac’(Pₙ) denotes the nearly antipodal chromatic number of Pₙ. In this paper we show that $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)-n/2-⎣10/n⎦+7$ if n is even positive integer and n ≥ 10, and $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)-(n-1)/2-⎣13/n⎦+8$ if n is odd positive integer and n ≥ 13. For all even positive integers n ≥ 10 and all odd positive integers n ≥ 13, these results improve the upper bounds for nearly antipodal chromatic number of Pₙ.

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V,E_N)$ where $E_N$ = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph $N^k\left(G\right):=N\left(N(...N\left(G\right))\right)$ of G. In particular we investigate conditions for G and k such that $N^k\left(G\right)$ becomes a complete graph.

The geometry of complex networks is closely related with their structure and function. In this paper, we investigate the Gromov-hyperbolicity of the Newman-Watts model of small-world networks. It is known that asymptotic Erdős-Rényi random graphs are not hyperbolic. We show that the Newman-Watts ones built on top of them by adding lattice-induced clustering are not hyperbolic as the network size goes to infinity. Numerical simulations are provided to illustrate the effects of various parameters...

Motivated by problems in radio channel assignments, we consider radio k-labelings of graphs. For a connected graph G and an integer k ≥ 1, a linear radio k-labeling of G is an assignment f of nonnegative integers to the vertices of G such that $|f\left(x\right)-f\left(y\right)|\ge k+1-d_G(x,y)$, for any two distinct vertices x and y, where $d_G(x,y)$ is the distance between x and y in G. A cyclic k-labeling of G is defined analogously by using the cyclic metric on the labels. In both cases, we are interested in minimizing the span of the labeling. The linear...

In this note, we prove several lower bounds on the domination number of simple connected graphs. Among these are the following: the domination number is at least two-thirds of the radius of the graph, three times the domination number is at least two more than the number of cut-vertices in the graph, and the domination number of a tree is at least as large as the minimum order of a maximal matching.

It is shown that a Banach space admits an equivalent norm whose modulus of uniform convexity has power-type $p$ if and only if it is Markov $p$-convex. Counterexamples are constructed to natural questions related to isomorphic uniform convexity of metric spaces, showing in particular that tree metrics fail to have the dichotomy property.