For any vertex v and any edge e in a non-trivial connected graph G, the distance sum d(v) of v is $d\left(v\right)={\sum }_{u\in V}d(v,u)$, the vertex-to-edge distance sum d₁(v) of v is $d₁\left(v\right)={\sum }_{e\in E}d(v,e)$, the edge-to-vertex distance sum d₂(e) of e is $d₂\left(e\right)={\sum }_{v\in V}d(e,v)$ and the edge-to-edge distance sum d₃(e) of e is $d₃\left(e\right)={\sum }_{f\in E}d(e,f)$. The set M(G) of all vertices v for which d(v) is minimum is the median of G; the set M₁(G) of all vertices v for which d₁(v) is minimum is the vertex-to-edge median of G; the set M₂(G) of all edges e for which d₂(e) is minimum is the edge-to-vertex...

Guy and Harary (1967) have shown that, for $k\ge 3$, the graph $P[2k,k]$ is homeomorphic to the Möbius ladder $M_{2k}$, so that its crossing number is one; it is well known that $P[2k,2]$ is planar. Exoo, Harary and Kabell (1981) have shown hat the crossing number of $P[2k+1,2]$ is three, for $k\ge 2.$ Fiorini (1986) and Richter and Salazar (2002) have shown that $P[9,3]$ has crossing number two and that $P[3k,3]$ has crossing number $k$, provided $k\ge 4$. We extend this result by showing that $P[3k,k]$ also has crossing number $k$ for all $k\ge 4$.

Let $G$ be a connected graph of order $n\ge 3$ and let $cE\left(G\right)\to \{1,2,...,k\}$ be a coloring of the edges of $G$ (where adjacent edges may be colored the same). For each vertex $v$ of $G$, the color code of $v$ with respect to $c$ is the $k$-tuple $c\left(v\right)=(a_1,a_2,\cdots ,a_k)$, where $a_i$ is the number of edges incident with $v$ that are colored $i$ ($1\le i\le k$). The coloring $c$ is detectable if distinct vertices have distinct color codes. The detection number $det\left(G\right)$ of $G$ is the minimum positive integer $k$ for which $G$ has a detectable $k$-coloring. We establish a formula for the...

We propose the following problem. For some k ≥ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted χ’ₖ(G). Let fₖ be defined by $fₖ\left(\Delta \right)=ma{x}_{G:\Delta \left(G\right)=\Delta }{\chi }^{\text{'}}ₖ\left(G\right)$. We show that fₖ(Δ) = Θ(Δ²/k). We also discuss some open problems.