Let $G=(V,E)$ be a 3-connected planar graph, with $V=\{1,...,n\}$. Let $M=\left(m_{i,j}\right)$ be a symmetric $n\times n$ matrix with exactly one negative eigenvalue (of multiplicity 1), such that for $i,j$ with $i\ne j$, if $i$ and $j$ are adjacent then $m_{i,j}\<0$ and if $i$ and $j$ are nonadjacent then $m_{i,j}=0$, and such that $M$ has rank $n-3$. Then the null space $kerM$ of $M$ gives an embedding of $G$ in $S^2$ as follows: let $\{a,b,c\}$ be a basis of $kerM$, and for $i\in V$ let $\varphi \left(i\right):=(a_i,b_i,c_i{)}^T$; then $\varphi \left(i\right)\ne 0$, and $\psi \left(i\right):=\varphi \left(i\right)/\parallel \varphi \left(i\right)\parallel$ embeds $V$ in $S^2$ such that connecting, for any two adjacent vertices $i,j$, the points $\psi \left(i\right)$ and $\psi \left(j\right)$ by a shortest geodesic on $S^2$, gives...

We prove the structural result on normal plane maps, which applies to the vertex distance colouring of plane maps. The vertex distance-t chromatic number of a plane graph G with maximum degree Δ(G) ≤ D, D ≥ 12 is proved to be upper bounded by $6+[(2D+12)/(D-2)]({(D-1)}^{(t-1)}-1)$. This improves a recent bound $6+[(3D+3)/(D-2)]({(D-1)}^{t-1}-1)$, D ≥ 8 by Jendrol’ and Skupień, and the upper bound for distance-2 chromatic number.

A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is known that a plane graph of minimum face size 5 contains light paths and a light pentagon. In this paper we show that every plane graph of minimum face size 5 contains also a light star $K_{1,3}$ and we present a structural result concerning the existence of a pair of adjacent faces with degree-bounded vertices.

A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.