The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. The crossing numbers of G☐Cₙ for some graphs G on five and six vertices and the cycle Cₙ are also given. In this paper, we extend these results by determining crossing numbers of Cartesian products G☐Cₙ for some connected graphs G of order six with six and seven edges. In addition, we collect known results concerning crossing numbers of G☐Cₙ for graphs G on six vertices.

The He matrix, put forward by He and He in 1989, is designed as a means for uniquely representing the structure of a hexagonal system (= benzenoid graph). Observing that the He matrix is just the adjacency matrix of a pertinently weighted inner dual of the respective hexagonal system, we establish a number of its spectral properties. Afterwards, we discuss the number of eigenvalues equal to zero of the He matrix of a hexagonal system. Moreover, we obtain a relation between the number of triangles...

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.