Given a distribution of pebbles on the vertices of a connected graph \( G \), a pebbling move on \( G \) consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The \( t \)-pebbling number \( \pi_t(G) \) is the smallest positive integer such that for every distribution of \( \pi_t(G) \) pebbles and every vertex \( v \), \( t \) pebbles can be moved to \( v \). For \( t = 1 \), Graham conjectured that \( \pi_1(G \Box H) \leq \pi_1(G)\pi_1(H) \) for any connected graphs \( G \) and \( H \), where \( G \Box H \) denotes the Cartesian product of \( G \) and \( H \). Herscovici further conjectured that \( \pi_{st}(G \Box H) \leq \pi_s(G)\pi_t(H) \) for any positive integers \( s \) and \( t \). Lourdusamy [A. Lourdusamy, “\(t\)-pebbling the product of graphs”, Acta Ciencia Indica, XXXII(1)(2006), 171-176] also conjectured that \( \pi_t(C_m \Box C_n) \leq \pi_1(C_m)\pi_t(C_n) \) for cycles \( C_m \) and \( C_n \). In this paper, we show that \( \pi_{st}(C_m \Box C_n) \leq \pi_s(C_m)\pi_t(C_n) \), which confirms this conjecture due to Lourdusamy.

The enhanced hypercube is basically a hypercube with additional edges augmented, where the additional edges connect all pairs of complementary nodes in the hypercube. Taking into account the minimal routing function and the structural properties of the enhanced hypercube, \( n+1 \) internal disjoint paths from one node to other distinct \( n+1 \) nodes have been constructed in an \( n \)-dimensional enhanced hypercube. The results can be used to provide an efficient and reliable routing to avoid congestion, accelerate transmission rate, and provide alternative transmission routes in enhanced hypercube networks, thus remarkably improving the performance of the interconnect networks.

The newly introduced neighborhood matrix extends the power of adjacency and distance matrices to describe the topology of graphs. The adjacency matrix enumerates which pairs of vertices share an edge and it may be summarized by the degree sequence, a list of the adjacency matrix row sums. The distance matrix shows more information, namely the length of shortest paths between vertex pairs. We introduce and explore the neighborhood matrix, which we have found to be an analog to the distance matrix what the degree sequence is to the adjacency matrix. The neighbor matrix includes the degree sequence as its first column and the sequence of all other distances in the graph up to the graph’s diameter, enumerating the number of neighbors each vertex has at every distance present in the graph. We prove this matrix to contain eleven oft-used graph statistics and topological descriptors. We also provide insight into two applications that show potential utility of the neighbor matrix in comparing graphs and identifying topologically significant vertices in a graph.

In this paper, for the Catalan-Larcombe-French sequence \( \{P_n\}_{n\geq0} \) and the Fennessey-Larcombe-French sequence \( \{V_n\}_{n\geq0} \), we mainly discuss the log-behavior of some sequences related to \( \{P_n\}_{n\geq0} \) and \( \{V_n\}_{n\geq0} \). For example, we study the log-behavior of some sequences such as \( \{P_n^2\}_{n\geq0} \), \( \{n!nV_n\}_{n\geq1} \), \( \{n!V_n\}_{n\geq0} \), and \( \{V_n-P_n\}_{n\geq2} \). In addition, we discuss the monotonicity of some sequences involving \( \{P_n\}_{n\geq0} \) and \( \{V_n\}_{n\geq0} \).

A graph \( G \) of order \( |V(G)| \) and size \( |E(G)| \) is called edge-magic if there exists a bijection \( f : V(G) \cup E(G) \to \{1, 2, 3, \dots, |V(G)| + |E(G)|\} \) such that \( f(x) + f(xy) + f(y) \) is a constant for every edge \( xy \in E(G) \). An edge-magic graph \( G \) is said to be super if \( f(V(G)) = \{1, 2, 3, \dots, |V(G)|\} \). Furthermore, the edge-magic deficiency of a graph \( G \), denoted \( \mu(G) \), is defined as the minimum nonnegative integer \( n \) such that \( G \cup nK_1 \) is edge-magic. Similarly, the \emph{super edge-magic deficiency} of a graph \( G \), denoted \( \mu_s(G) \), is either the minimum nonnegative integer \( n \) such that \( G \cup nK_1 \) is super edge-magic or \( +\infty \) if there exists no such integer \( n \). In this paper, we investigate the (super) edge-magic deficiency of chain graphs. Based on these, we propose some open problems.

Given a large finite point set, \( P \subset \mathbb{R}^2 \), we obtain upper bounds on the number of triples of points that determine a given pair of dot products. That is, for any pair of nonzero real numbers, \( (\alpha, \beta) \), we bound the size of the set \[ \{(p, q, r) \in P \times P \times P : p \cdot q = \alpha, p \cdot r = \beta\}. \]

An explicit formula for the number of spanning trees of the lexi- cographic product GLH] of two arbitrary graphs G and H is deduced in terms of structure parameters of G and H. Some properties on the number of spanning trees of G[H] are revealed. Sharp lower and upper bounds for the number of spanning trees of lexicographic product of graphs are established. In particular, simple formulae for the number of spanning trees of the lexicographic product of some special graphs are derived, which extend some previously known results
in the literature.

For a graph \( G \), the expression \( G \overset{v}{\rightarrow} (a_1,\ldots,a_s) \) means that for any \( s \)-coloring of the vertices of \( G \), there exists \( i \in \{1,\ldots,s\} \) such that there is a monochromatic \( a_i \)-clique of color \( i \). The vertex Folkman numbers

\[ F_v(a_1,\ldots,a_s;m-1) = \min\{|V(G)|: G \overset{v}{\rightarrow} (a_1,\ldots,a_s) \text{ and } K_{m-1} \nsubseteq G\} \]

are considered, where \( m = \sum_{i=1}^s (a_i – 1) + 1 \).

With the help of a computer, we show that \( F_v(2,2,5;6) = 16 \), and then we prove

\[ F_v(a_1,\ldots,a_s;m-1) = m+9, \]

if \( \max\{a_1,\ldots,a_s\} = 5 \).

We also obtain the bounds

\[ m+9 \leq F_v(a_1,\ldots,a_s;m-1) \leq m+10, \]

if \( \max\{a_1,\ldots,a_s\} = 6 \).

The diameter of a graph can be affected by the addition or the deletion of some edges. In [3], we have studied the diameter variability of the Cartesian product of graphs. In this paper, we discuss about two fundamental products, strong and lexicographic products of graphs, whose diameter increases (decreases) by the deletion (addition) of a single edge. The problems of minimality and maximality of the product graphs with respect to its diameter are also solved. These problems are motivated by the fact that these graph products are good interconnection networks.

The concept of the skew energy of a digraph was introduced by Adiga, Balakrishnan and So in 2010. An oriented graph \( G^{\sigma} \) is a simple undirected graph \( G \) with an orientation, which assigns to each edge a direction so that \( G^{\sigma} \) becomes a directed graph. Then \( G \) is called the underlying graph of \( G^{\sigma} \). Let \( S(G^{\sigma}) \) be the skew-adjacency matrix of \( G^{\sigma} \) and \( \lambda_1, \lambda_2, \ldots, \lambda_n \) denote all the eigenvalues of \( S(G^{\sigma}) \). The skew energy of \( G^{\sigma} \) is defined as the sum of the absolute values of all eigenvalues of \( S(G^{\sigma}) \). Recently, Gong, Li and Xu determined all oriented graphs with minimal skew energy among all connected oriented graphs on \( n \) vertices with \( m \) (\( n \leq m \leq 2(n-2) \)) arcs. In this paper, we determine all oriented graphs with the second and the third minimal skew energy among all connected oriented graphs with \( n \) vertices and \( m \) (\( n \leq m < 2(n-2) \)) arcs. In particular, when the oriented graphs are unicyclic digraphs or bicyclic digraphs, the second and the third minimal skew energy is determined.