The matching energy of a graph was introduced by Gutman and Wagner in \(2012\) and defined as the sum of the absolute values of zeros of its matching polynomial. In this paper, we completely determine the graph with minimum matching energy in tricyclic graphs with given girth and without \(K_4\)-subdivision.

In this paper, we define and study the Gaussian Fibonacci and Gaussian Lucas \(p\)-numbers. We give generating functions, Binet formulas, explicit formulas, matrix representations, and sums of Gaussian Fibonacci \(p\)-numbers by matrix methods. For \(p = 1\), these Gaussian Fibonacci and Gaussian Lucas \(p\)-numbers reduce to the Gaussian Fibonacci and the Gaussian Lucas numbers.

Let \(G\) be a graph of order \(n\) and let \(Q(G, x) = \det(xI – Q(G)) = \sum_{i=0}^{n}(-1)^i\zeta_i(G)x^{n-i}\) be the characteristic polynomial of the signless Laplacian matrix of \(G\). We show that the Lollipop graph, \(L_{n,3}\), has the maximal \(Q\)-coefficients, among all unicyclic graphs of order \(n\) except \(C_n\). Moreover, we determine graphs with minimal \(Q\)-coefficients, among all unicyclic graphs of order \(n\).

Let \(G\) be a graph with \(n\) vertices, \(\mathcal{G}(G)\) the subdivision graph of \(G\). \(V(G)\) denotes the set of original vertices of \(G\). The generalized subdivision corona vertex graph of \(G\) and \(H_1, H_2, \ldots, H_n\) is the graph obtained from \(\mathcal{G}(G)\) and \(H_1, H_2, \ldots, H_n\) by joining the \(i\)th vertex of \(V(G)\) to every vertex of \(H_i\). In this paper, we determine the Laplacian (respectively, the signless Laplacian) characteristic polynomial of the generalized subdivision corona vertex graph. As an application, we construct infinitely many pairs of cospectral graphs.

In the paper, we show that the orientable genus of the generalized Petersen graph \(P(km, m)\) is at least \( \frac{km}{4} – \frac{m}{2}-\frac{km}{4m-4}+1\) if \(m\geq 4\) and \(k \geq 3\). We determine the orientable genera of \(P(3m, m)\), \(P(4k, 4)\), \(P(4m, m)\) if \(m \geq 4\), \(P(6m, m)\) if \(m \equiv 0 \pmod{2}\) and \(m \geq 6\), and so on.

Assume that \(\mu_1, \mu_2, \ldots, \mu_n\) are the eigenvalues of the Laplacian matrix of a graph \(G\). The Laplacian Estrada index of \(G\), denoted by \(LEE(G)\), is defined as \(LEE(G) = \sum_{i=1}^{n} e^{\mu_i}\). In this note, we give an upper bound on \(LEE(G)\) in terms of chromatic number and characterize the corresponding extremal graph.

In this note, we provide a combinatorial proof of a recent formula for the total number of peaks and valleys (either strict or weak) within the set of all compositions of a positive integer into a fixed number of parts.

The adjacent vertex distinguishing total chromatic number \(\chi_{at}(G)\) of a graph \(G\) is the smallest integer \(k\) for which \(G\) admits a proper \(k\)-total coloring such that no pair of adjacent vertices are incident to the same set of colors. Snarks are connected bridgeless cubic graphs with chromatic index \(4\). In this paper, we show that \(\chi_{at}(G) = 5\) for two infinite subfamilies of snarks, i.e., the Loupekhine snark and Blanusa snark of first and second kind. In addition, we give an adjacent vertex distinguishing total coloring using \(5\) colors for Watkins snark and Szekeres snark, respectively.

Let \(G\) be a tricyclic graph. Tricyclic graphs are connected graphs in which the number of edges equals the number of vertices plus two. In this paper, we determine graphs with the largest signless Laplacian spectral radius among all the tricyclic graphs with \(n\) vertices and diameter \(d\).

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].

For any vertex \(x\) in a connected graph \(G\) of order \(n \geq 2\), a set \(S \subseteq V(G)\) is a \(z\)-detour monophonic set of \(G\) if each vertex \(v \in V(G)\) lies on a \(x-y\) detour monophonic path for some element \(y \in S\). The minimum cardinality of a \(x\)-detour monophonic set of \(G\) is the \(x\)-detour monophonic number of \(G\), denoted by \(dm_z(G)\). An \(x\)-detour monophonic set \(S_x\) of \(G\) is called a minimal \(x\)-detour monophonic set if no proper subset of \(S_x\) is an \(x\)-detour monophonic set. The upper \(x\)-detour monophonic number of \(G\), denoted by \(dm^+_x(G)\), is defined as the maximum cardinality of a minimal \(x\)-detour monophonic set of \(G\). We determine bounds for it and find the same for some special classes of graphs. For positive integers \(r, d,\) and \(k\) with \(2 \leq r \leq d\) and \(k \geq 2\), there exists a connected graph \(G\) with monophonic radius \(r\), monophonic diameter \(d\), and upper \(z\)-detour monophonic number \(k\) for some vertex \(x\) in \(G\). Also, it is shown that for positive integers \(j, k, l,\) and \(n\) with \(2 \leq j \leq k \leq l \leq n – 7\), there exists a connected graph \(G\) of order \(n\) with \(dm_x(G) = j\), \(dm^+_x(G) = l\), and a minimal \(x\)-detour monophonic set of cardinality \(k\).

Many authors define certain generalizations of the usual Fibonacci, Pell, and Lucas numbers by matrix methods and then obtain the Binet formulas and combinatorial representations of the generalizations of these number sequences. In this article, we firstly define and study the generalized Gaussian Fibonacci numbers and then find the matrix representation of the generalized Gaussian Fibonacci numbers and prove some theorems by these matrix representations.

Given two sets \(A, B \subset \mathbb{F}_q\), of elements of the finite field \(\mathbb{F}_q\), of \(q\) elements, Shparlinski (2008) showed that the product set \(\mathcal{AB} = \{ab \mid a \in \mathcal{A}, b \in \mathcal{B}\}\) contains an arithmetic progression of length \(k \geq 3\) provided that \(k

3\) is the characteristic of \(\mathbb{F}\), and \(|\mathcal{A}||\mathcal{B}| \geq 2q^{2-1/(k-1)}\). In this paper, we recover Shparlinski’s result for the case of 3-term arithmetic progressions via spectra of product graphs over finite fields. We also illustrate our method in the setting of residue rings. Let \(m\) be a large integer and \(\mathbb{Z}/m\mathbb{Z}\) be the ring of residues mod \(m\). For any two sets \(\mathcal{A}, \mathcal{B} \subset \mathbb{Z}/m\mathbb{Z}\) of cardinality \[|\mathcal{A}||\mathcal{B}| > m(\frac{r(m)m}{r(m)^{\frac{1}{2}} + 1})\], the product set \(\mathcal{AB}\) contains a \(3\)-term arithmetic progression, where \(r(m)\) is the smallest prime divisor of \(m\) and \(r(m)\) is the number of divisors of \(m\). The spectral proofs presented in this paper avoid the use of character and exponential sums, the usual tool to deal with problems of this kind.

A proper edge-coloring of a graph \(G\) with colors \(1, \ldots, t\) is called an interval \(t\)-coloring if the colors of edges incident to any vertex of \(G\) form an interval of integers. A graph \(G\) is interval colorable if it has an interval \(t\)-coloring for some positive integer \(t\). For an interval colorable graph \(G\), the least value of \(t\) for which \(G\) has an interval \(t\)-coloring is denoted by \(w(G)\). A graph \(G\) is outerplanar if it can be embedded in the plane so that all its vertices lie on the same (unbounded) face. In this paper, we show that if \(G\) is a 2-connected outerplanar graph with \(\Delta(G) = 3\), then \(G\) is interval colorable and \[ w(G) = \begin{cases} 3, & \text{if } |V(G)| \text{ is even}, \\ 4, & \text{if } |V(G)| \text{ is odd}. \end{cases} \]
We also give a negative answer to the question of Axenovich on the outerplanar triangulations.

In this paper, we characterize all finite abelian groups with isomorphic intersection graphs. This solves a conjecture proposed by \(B\).Zelinka.

This paper devotes to solving the following conjecture proposed by Gvozdjak: “An \((a, b; n)\)-graceful labeling of \(P_n\) exists if and only if the integers \(a, b, n\) satisfy (1) \(b – a\) has the same parity as \(n(n + 1)/2\); (2) \(0 < |b – a| \leq (n + 1)/2\) and (3) \(n/2 \leq a + b \leq 3n/2\).'' Its solving can shed some new light on solving the famous Oberwolfach problem. It is shown that the conjecture is true for every \(n\) if the conjecture is true when \(n \leq 4a + 1\) and \(a\) is a fixed value. Moreover, we prove that the conjecture is true for \(a = 0, 1, 2, 3, 4, 5, 6\).

The aim of this paper is to show that the corona \(P_n \bigodot P_m\) between two paths \(P_n\) and \(P_m\) is cordial for all \(n \geq 1\) and \(m \geq 1\). Also, we prove that except for \(n\) and \(m\) being congruent to \(2 \pmod{4}\), the corona \(C_n \bigodot C_m\) between two cycles \(C_n\) and \(C_m\) is cordial. Furthermore, we show that if \(n \equiv 2 \pmod{4}\) and \(m\) is odd, then \(C_n \bigodot C_m\) is not cordial.

In this paper, we establish some general identities involving the weighted row sums of a Riordan array and hyperharmonic numbers. From these general identities, we deduce some particular identities involving other special combinatorial sequences, such as the Stirling numbers, the ordered Bell numbers, the Fibonacci numbers, the Lucas numbers, and the binomial coefficients.

In this paper, we consider the relationship between toughness and the existence of \([a, b]\)-factors with inclusion/exclusion properties. We obtain that if \(t(G) \geq a – 1 + \frac{a – 1}{b}\) with \(b > a > 2\), where \(a, b\) are two integers, then for any two given edges \(e_1\) and \(e_2\), there exist an \([a, b]\)-factor including \(e_1, e_2\); and an \([a, b]\)-factor including \(e_1\) and excluding \(e_2\); as well as an \((a, b)\)-factor excluding \(e_1, e_2\). Furthermore, it is shown that the results are best possible in some sense.

In this paper, we will determine the NBB bases with respect to a certain standard ordering of atoms of lattices of \(321\)-\(312\)-\(231\)-avoiding permutations and of \(321\)-avoiding permutations with the weak Bruhat order. Using our expressions of NBB bases, we will calculate the Möbius numbers of these lattices. These values are shown to be related to Fibonacci polynomials.

Let \(D(G)\) denote the signless Dirichlet spectral radius of the graph \(G\) with at least a pendant vertex, and \(\pi_1\) and \(\pi_2\) be two nonincreasing unicyclic graphic degree sequences with the same frequency of number \(1\). In this paper, the signless Dirichlet spectral radius of connected graphs with a given degree sequence is studied. The results are used to prove a majorization theorem of unicyclic graphs. We prove that if \(\pi_1 \unrhd \pi_2\), then \(D(G_1) \leq D(G_2)\) with equality if and only if \(\pi_1 = \pi_2\), where \(G_1\) and \(G_2\) are the graphs with the largest signless Dirichlet spectral radius among all unicyclic graphs with degree sequences \(\pi_1\) and \(\pi_2\), respectively. Moreover, the graphs with the largest signless Dirichlet spectral radius among all unicyclic graphs with \(k\) pendant vertices are characterized.

A function \(f\) is called a graceful labeling of a graph \(G\) with \(m\) edges, if \(f\) is an injective function from \(V(G)\) to \(\{0, 1, 2, \ldots, m\}\) such that when every edge \(uv\) is assigned the edge label \(|f(u) – f(v)|\), then the resulting edge labels are distinct. A graph which admits a graceful labeling is called a graceful graph. A graceful labeling of a graph \(G\) with \(m\) edges is called an \(\alpha\)-labeling if there exists a number \(\alpha\) such that for any edge \(uv\), \(\min\{f(u), f(v)\} \leq \lambda < \max\{f(u), f(v)\}\). The characterization of graceful graphs appears to be a very difficult problem in Graph Theory. In this paper, we prove a basic structural property of graceful graphs, that every tree is a subtree of a graceful graph, an \(\alpha\)-labeled graph, and a graceful tree, and we discuss a related open problem towards settling the popular Graceful Tree Conjecture.

We use rook placements to prove Spivey’s Bell number formula and other identities related to it, in particular, some convolution identities involving Stirling numbers and relations involving Bell numbers. To cover as many special cases as possible, we work on the generalized Stirling numbers that arise from the rook model of Goldman and Haglund. An alternative combinatorial interpretation for the Type II generalized \(q\)-Stirling numbers of Remmel and Wachs is also introduced, in which the method used to obtain the earlier identities can be adapted easily.

An \(H\)-triangle is a triangle with corners in the set of vertices of a tiling of \(\mathbb{R}^2\) by regular hexagons of unit edge. Let \(b(\Delta)\) be the number of the boundary \(H\)-points of an \(H\)-triangle \(\Delta\). In [3] we made a conjecture that for any \(H\)-triangle with \(k\) interior \(H\)-points, we have \(b(\Delta) \in \{3, 4, \ldots, 3k+4, 3k+5, 3k+7\}\). In this note, we prove the conjecture is true for \(k = 4\), but not true for \(k = 5\) because \(b(\Delta)\) cannot equal \(15\).