We show positivity of the Q-matrix of four kinds of graph products: direct product (Cartesian product), star product, comb product, and free product. During the discussion we give an alternative simple proof of the Markov product theorem on positive definite kernels.

Zero forcing number has recently become an interesting graph parameter studied in its own right since its introduction by the “AIM Minimum Rank–Special Graphs Work Group”, whereas metric dimension is a well-known graph parameter. We investigate the metric dimension and the zero forcing number of some line graphs by first determining the metric dimension and the zero forcing number of the line graphs of wheel graphs and the bouquet of circles. We prove that $Z\left(G\right)\le 2Z\left(L\right(G\left)\right)$ for a simple and connected graph $G$. Further,...

For a graph G = (V, E), a function f:V(G) → 1,2, ...,k is a k-ranking if f(u) = f(v) implies that every u - v path contains a vertex w such that f(w) > f(u). A k-ranking is minimal if decreasing any label violates the definition of ranking. The arank number, ${\psi }_r\left(G\right)$, of G is the maximum value of k such that G has a minimal k-ranking. We completely determine the arank number of the Cartesian product Kₙ ☐ Kₙ, and we investigate the arank number of Kₙ ☐ Kₘ where n > m.

Let G be an undirected graph with n vertices. Assume that a robot is placed on a vertex and n − 2 obstacles are placed on the other vertices. A vertex on which neither a robot nor an obstacle is placed is said to have a hole. Consider a single player game in which a robot or obstacle can be moved to adjacent vertex if it has a hole. The objective is to take the robot to a fixed destination vertex using minimum number of moves. In general, it is not necessary that the robot will take a shortest path...