A graphic sequence \( \pi = (d_1, d_2, \ldots, d_n) \) is said to be potentially \( K_{1^3,4} \)-graphic if there is a realization of \( \pi \) containing \( K_{1^3,4} \) as a subgraph, where \( K_{1^3,4} \) is the \( 1 \times 1 \times 1 \times 4 \) complete 4-partite graph. In this paper, we characterize the graphic sequences potentially \( K_{1^3,4} \)-graphic and the result is simple. In addition, we apply this characterization to compute the values of \( \sigma( K_{1^3,4}, n) \).

We show, using a hybrid analysis/linear algebra argument, that the diagonal vector of an infinite symmetric matrix over \(\mathbb{Z}_{2}\) is contained in the range of the matrix. We apply this result to an extension, to the countably infinite case, of the Lights Out problem.

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 \).