A pebbling move on a graph \(G\) consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number of a graph \(G\), denoted by \(f(G)\), is the least integer \(n\) such that, however \(n\) pebbles are located on the vertices of \(G\), we can move one pebble to any vertex by a sequence of pebbling moves. For any connected graphs \(G\) and \(H\), Graham conjectured that \(f(G \times H) \leq f(G)f(H)\). In this paper, we give the pebbling number of some graphs and prove that Graham’s conjecture holds for the middle graphs of some even cycles.

Graph embedding is an important factor to evaluate the quality of an interconnection network. It is also a powerful tool for implementation of parallel algorithms and simulation of different interconnection networks. In this paper, we compute the exact wirelength of embedding circulant networks into cycle-of-ladders.

In this paper, we characterize the extremal digraph with the maximal signless Laplacian spectral radius and the minimal distance signless Laplacian spectral radius among all simple connected digraphs with a given dichromatic number, respectively.

Given a graph \(G = (V, E)\) with no isolated vertex, a subset \(S \subseteq V\) is a total dominating set of \(G\) if every vertex in \(V\) is adjacent to a vertex in \(S\). A total dominating set \(S\) of \(G\) is a locating-total dominating set if for every pair of distinct vertices \(u\) and \(v\) in \(V – S\), we have \(N(u) \cap S \neq N(v) \cap S\), and \(S\) is a differentiating-total dominating set if for every pair of distinct vertices \(u\) and \(v\) in \(V\), we have \(N(u) \cap S \neq N(v) \cap S\). The locating-total domination number (or the differentiating-total domination number) of \(G\), denoted by \(\gamma_t^L(G)\) (or \(\gamma_t^D(G)\)), is the minimum cardinality of a locating-total dominating set (or a differentiating-total dominating set) of \(G\). In this paper, we investigate the bounds of locating and differentiating-total domination numbers of unicyclic graphs.

Motzkin posed the problem of finding the maximal density \(\mu(M)\) of sets of integers in which the differences given by a set \(M\) do not occur. The problem is already settled when \(|M| \leq 2\) or \(M\) is a finite arithmetic progression. In this paper, we determine \(\mu(M)\) when \(M\) has some other structure. For example, we determine \(\mu(M)\) when \(M\) is a finite geometric progression.

For vertices \(u, v\) in a connected graph \(G\), a \(u-v\) chordless path in \(G\) is a \(u-v\) monophonic path. The monophonic interval \(J_G[u, v]\) consists of all vertices lying on some \(u-v\) monophonic path in \(G\). For \(S \subseteq V(G)\), the set \(J_G[S]\) is the union of all sets \(J_G[u, v]\) for \(u, v \in S\). A set \(S \subseteq V(G)\) is a monophonic set of \(G\) if \(J_G[S] = V(G)\). The cardinality of a minimum monophonic set of \(G\) is the monophonic number of \(G\), denoted by \(mn(G)\). In this paper, bounds for the monophonic number of the strong product graphs are obtained, and for several classes, improved bounds and exact values are obtained.

A hypergraph is a useful tool to model complex systems and can be considered a natural generalization of graphs. In this paper, we define some operations of fuzzy hypergraphs and strong fuzzy \(r\)-uniform hypergraphs, such as Cartesian product, strong product, normal product, lexicographic product, union, and join. We prove that if a hypergraph \(H\) is formed by one of these operations, then this hypergraph is a fuzzy hypergraph or a strong fuzzy \(r\)-uniform hypergraph. Finally, we discuss an application of fuzzy hypergraphs.

Let \(p_e(n)\) be the number of ways to make change for \(n\) cents using pennies, nickels, dimes, and quarters. By manipulating the generating function for \(p_e(n)\), we prove that the sequence \(\{p_e(n) \pmod{\ell^j}\}\) is periodic for every prime power \(\ell\).

In 1972, Chvatal and Erdős showed that the graph \(G\) with independence number \(\alpha(G)\) no more than its connectivity \(\kappa(G)\) (i.e., \(\kappa(G) \geq \alpha(G)\)) is hamiltonian. In this paper, we consider a kind of Chvatal and Erdős type condition on edge-connectivity \(\lambda(G)\) and matching number (edge independence number). We show that if \(\lambda(G) \geq \alpha'(G) – 1\), then \(G\) is either supereulerian or in a well-defined family of graphs. Moreover, we weaken the condition \(\kappa(G) \geq \alpha(G) – 1\) in [11] to \(\lambda(G) \geq \alpha(G) – 1\) and obtain a similar characterization on non-supereulerian graphs. We also characterize the graph which contains a dominating closed trail under the assumption \(\lambda(G) \geq \alpha'(G) – 2\).

The coloring number \(col(G)\) of a graph \(G\) is the smallest number \(k\) for which there exists a linear ordering of the vertices of \(G\) such that each vertex is preceded by fewer than \(k\) of its neighbors. It is well known that \(\chi(G) \leq col(G)\) for any graph \(G\), where \(\chi(G)\) denotes the chromatic number of \(G\). The Randić index \(R(G)\) of a graph \(G\) is defined as the sum of the weights \(\frac{1}{\sqrt{d(u)d(v)}}\) of all edges \(uv\) of \(G\), where \(d(u)\) denotes the degree of a vertex \(u\) in \(G\). We show that \(\chi(G) \leq col(G) \leq 2R'(G) \leq R(G)\) for any connected graph \(G\) with at least one edge, and \(col(G) = 2R'(G)\) if and only if \(G\) is a complete graph with some pendent edges attaching to its same vertex, where \(R'(G)\) is a modification of Randić index, defined as the sum of the weights \(\frac{1}{\max\{d(u), d(v)\}}\) of all edges \(uv\) of \(G\). This strengthens a relation between Randić index and chromatic number by Hansen et al. [7], a relation between Randić index and coloring number by Wu et al. [17] and extends a theorem of Deng et al. [2].