By a signpost system we mean an ordered pair $(W,P)$, where $W$ is a finite nonempty set, $P\subseteq W\times W\times W$ and the following statements hold: $$\text{if}(u,v,w)\in P,\text{then}(v,u,u)\in P\text{and}(v,u,w)\notin P,\text{for}\text{all}u,v,w\in W;\text{if}u\ne v,i\text{then}\text{there}\text{exists}r\in W\text{such}\text{that}(u,r,v)\in P,\text{for}\text{all}u,v\in W.$$ We say that a signpost system $(W,P)$ is smooth if the folowing statement holds for all $u,v,x,y,z\in W$: if $(u,v,x),(u,v,z),(x,y,z)\in P$, then $(u,v,y)\in P$. We say thay a signpost system $(W,P)$ is simple if the following statement holds for all $u,v,x,y\in W$: if $(u,v,x),(x,y,v)\in P$, then $(u,v,y),(x,y,u)\in P$. By the underlying graph of a signpost system $(W,P)$ we mean the graph $G$ with $V\left(G\right)=W$ and such that the following statement holds for all distinct $u,v\in W$: $u$ and $v$ are adjacent in $G$ if and only if $(u,v,v)\in P$....

In this paper we show bounds for the adjacent eccentric distance sum of graphs in terms of Wiener index, maximum degree and minimum degree. We extend some earlier results of Hua and Yu [Bounds for the Adjacent Eccentric Distance Sum, International Mathematical Forum. Vol. 7 (2O02) no. 26. 1280-1294]. The adjaceni eccentric distance sum index of the graph G is defined as [...] where ε(υ) is the eccentricity of the vertex υ, deg(υ) is the degree of the vertex υ and D(υ) = ∑u∊v(G) d (u,υ)is the sum...

We use an algebraic method to classify the generalized permutation star-graphs, and we use the classification to determine the toughness of all generalized permutation star-graphs.

In this note we show that $1$-skeletons and $2$-skeletons of $n$-pseudomanifolds with full boundary are $(n+1)$-connected graphs and $n$-connected $2$-complexes, respectively. This generalizes previous results due to Barnette and Woon.

An axiomatic characterization of the distance function of a connected graph is given in this note. The triangle inequality is not contained in this characterization.

A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ + 1) + 5...

Motivated by the conjectures in [11], we introduce the maximal chains of a cycle permutation graph, and we use the properties of maximal chains to establish the upper bounds for the toughness of cycle permutation graphs. Our results confirm two conjectures in [11].