A graph \(G\) is called \(H\)-equipackable if every maximal \(H\)-packing in \(G\) is also a maximum \(H\)-packing in \(G\). In 2012, \(P_k\)-equipackable paths and cycles, \(M_k\)-equipackable paths and cycles are characterized. In this paper, \(P_m \cup P_k\)-equipackable paths and cycles are characterized.

If \(X\) is a geodesic metric space and \(x_1, x_2, x_3 \in X\), a geodesic triangle \(T = \{x_1, x_2, x_3\}\) is the union of the three geodesics \([x_1x_2]\), \([x_2x_3]\) and \([x_3x_1]\) in \(X\). The space \(X\) is \(\delta\)-hyperbolic (in the Gromov sense) if any side of \(T\) is contained in a \(\delta\)-neighborhood of the union of the two other sides, for every geodesic triangle \(T\) in \(X\). The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. Regular graphs are a very interesting class of graphs with many applications. The main aim of this paper is to obtain information about the hyperbolicity constant of regular graphs. We obtain several bounds for this parameter; in particular, we prove that \(\delta(G) \leq \frac{\Delta n}{8(\Delta-1)+1}\) for any \(4\)-regular graph \(G\) with \(n\) vertices. Furthermore, we show that for each \(\Delta \geq 2\) and every possible value \(t\) of the hyperbolicity constant, there exists a \(\Delta\)-regular graph \(G\) with \(\delta(G) = t\). We also study the regular graphs \(G\) with \(\delta(G) \leq 1\), i.e., the graphs which are like trees (in the Gromov sense). Besides, we prove some inequalities involving the hyperbolicity constant and domination numbers for regular graphs.

When \(G\) and \(F\) are graphs, \(v \in V(G)\) and \(\varphi\) is an orbit of \(V(F)\) under the action of the automorphism group of \(F\), \(s(F,G,v,\varphi)\) denotes the number of induced subgraphs of \(G\) isomorphic to \(F\) such that \(v\) lies in orbit \(\theta\) of \(F\). Vertices \(v \in V(G)\) and \(w \in V(H)\) are called \(k\)-vertex subgraph equivalent (\(k\)-SE), \(2 \leq k < n = |V(G)|\), if for each graph \(F\) with \(k\) vertices and for every orbit \(\varphi\) of \(F\), \(s(F,G,v,\varphi) = s(F,H,w,\varphi)\), and they are called similar if there is an isomorphism from \(G\) to \(H\) taking \(v\) to \(w\). We prove that \(k\)-SE vertices are \((k-1)\)-SE and several parameters of \((n-1)\)-SE vertices are equal. It is also proved that in many situations, “(n-1)-SE between vertices is equivalent to their similarity'' and it is true always if and only if Ulam's Graph Reconstruction Conjecture is true.

External Difference Families \((EDFs)\) are a new type of combinatorial designs originated from cryptography. In this paper, some constructions of \(EDFs\) are presented by using Gauss sums. Several classes of \(EDFs\) and related combinatorial designs are obtained.

The crossing number problem is in the forefront of topological graph theory. At present, there are only a few results concerning crossing numbers of join of some graphs. In this paper, for the special graph \(Q\) on six vertices, we give the crossing numbers of its join with \(n\) isolated vertices, as well as with the path \(P_n\) on \(n\) vertices and with the cycle \(C_n\).

In this article, we give a generalization of the multiparameter non-central Stirling numbers of the first and second kinds, Lah numbers, and harmonic numbers. Some new combinatorial identities, new explicit formulas, and many relations between different types of Stirling numbers and generalized harmonic numbers are found. Moreover, some interesting special cases of the generalized multiparameter non-central Stirling numbers are deduced. Furthermore, a matrix representation of the results obtained is given and a computer program is written using Maple and executed for calculating \(GMPNSN-1\) and their inverse \((GMPNSN-2)\), along with some of their interesting special cases.

Suppose \(G\) is a graph. Let \(u\) be a vertex of \(G\). A vertex \(v\) is called an \(i\)-neighbor of \(u\) if \(d_G(u,v) = i\). A \(1\)-neighbor of \(u\) is simply called a neighbor of \(u\). Let \(s\) and \(t\) be two nonnegative integers. Suppose \(f\) is an assignment of nonnegative integers to the vertices of \(G\). If the following three conditions are satisfied, then \(f\) is called an \((s, t)\)-relaxed \(L(2,1)\)-labeling of \(G\): (1) for any two adjacent vertices \(u\) and \(v\) of \(G\), \(f(u) \neq f(v)\); (2) for any vertex \(u\) of \(G\), there are at most \(s\) neighbors of \(u\) receiving labels from \(\{f(u) – 1, f(u)+ 1\}\); (3) for any vertex \(u\) of \(G\), the number of \(2\)-neighbors of \(u\) assigned the label \(f(u)\) is at most \(t\). The minimum span of \((s, t)\)-relaxed \(L(2,1)\)-labelings of \(G\) is called the \((s,t)\)-relaxed \(L(2,1)\)-labeling number of \(G\), denoted by \(\lambda_{2,1}^{s,t}(G)\). It is clear that \(\lambda_{2,1}^{0,0}(G)\) is the so-called \(L(2, 1)\)-labeling number of \(G\). In this paper, the \((s, t)\)-relaxed \(L(2, 1)\)-labeling number of the hexagonal lattice is determined for each pair of two nonnegative integers \(s\) and \(t\). And this provides a series of channel assignment schemes for the corresponding channel assignment problem on the hexagonal lattice.

As an additive weight version of the Harary index, the reciprocal degree distance of a simple connected graph \(G\) is defined as \(RDD(G) = \sum\limits_{u,v \subseteq V(G)} \frac{d_G(u)+d_G(v)}{d_G(u,v)}\), where \(d_G(u)\) is the degree of \(u\) and \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G\). In this paper, we respectively characterize the extremal graphs with the maximum \(RDD\)-value among all the graphs of order \(n\) with given number of cut vertices and cut edges. In addition, an upper bound on the reciprocal degree distance in terms of the number of cut edges is provided.

In this work, linear codes over \(\mathbb{Z}_{2^s}\) are considered together with the extended Lee weight, which is defined as
\[w_L(a) = \begin{cases}
a & \text{if } a \leq 2^{s-1}, \\
2^s – x & \text{if } a > 2^{s-1}.
\end{cases}\]
The ideas used by Wilson and Yildiz are employed to obtain divisibility properties for sums involving binomial coefficients and the extended Lee weight. These results are then used to find bounds on the power of 2 that divides the number of codewords whose Lee weights fall in the same congruence class modulo \(2^e\). Comparisons are made with the results for the trivial code and the results for the homogeneous weight.

In this paper we study the Laplacian spectral radius of bicyclic graphs with given independence number and characterize the extremal graphs completely.

In this paper, we obtain some analytical expressions and give two simple formulae for the expected values of the Wiener indices of the random Phenylene and Spiro hexagonal chains.

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

The harmonic index \(H(G)\) of a graph \(G\) is defined as the sum of the weights \(\frac{2}{d_u+ d_v}\) of all edges \(uv\) of \(G\), where \(d_u\) denotes the degree of a vertex \(u\) in \(G\). We determine the \(n\)-vertex trees with the second and third maximum harmonic indices for \(n \geq 7\), the fourth maximum harmonic index for \(n \geq 10\), and fifth maximum harmonic index for $n \geq 11\), and unicyclic graphs with the second and third maximum harmonic indices for \(n \geq 5\), the fourth maximum harmonic index for \(n \geq 7\), and fifth maximum harmonic index for \(n \geq 8\), and bicyclic graphs with the maximum harmonic index for \(n \geq 6\), the second and third maximum harmonic indices for \(n \geq 7\), and fourth maximum harmonic index for \(n \geq 9\).

Graph embedding has been known as a powerful tool for implementation of parallel algorithms and simulation of different interconnection networks. In this paper, we obtain the minimum wirelength of embedding circulant networks into necklace and windmill graphs. The algorithms for obtaining the same are of \(O(2n)\)-linear time.

In this paper, a reliable symbolic computational algorithm is presented for inverting a general companion matrix by using parallel computing along with recursion. The computational cost of the algorithm is \(O(n^2)\). The algorithm is implementable to the Computer Algebra System (CAS) such as MAPLE, MATLAB, and MATHEMATICA. Three examples are presented for the sake of illustration.

Let \(K_r\) be the complete graph on \(r\) vertices in which there exists an edge between every pair of vertices, \(K_{m,n}\) be the complete bipartite graph with \(m\) vertices in one partition and \(n\) vertices in the other partition, where each vertex in one partition is adjacent to each vertex in the other partition, and \(K(n, r)\) be the complete \(r\)-partite graph \(K_{n,n,…,n}\) where each partition has \(n\) vertices. In this paper, we determine the minimum number of monochromatic stars \(K_{1,p}\), \( \forall p \geq 2\), in any \(t\)-coloring (\(t \geq 2\)) of edges of \(K_r\), \(K_{m,n}\), and \(K(n, r)\). Also, we prove that these lower bounds are sharp for all values of \(m, n, p, r\), and \(t\) by giving explicit constructions.

In this paper, we prove that if the toughness of a \(k\)-tree \(G\) is at least \(\frac{k+1}{3}\), then \(G\) is panconnected for \(k \geq 3\), or \(G\) is vertex pancyclic for \(k = 2\). This result improves a result of Broersma, Xiong, and Yoshimoto.

Since the Wiener index has been successful in the study of benzenoid systems and boiling points of alkanes, it is natural to examine this number for the study of fullerenes, most of whose cycles are hexagons. This topological index is equal to the sum of distances between all pairs of vertices of the respective graph. It was introduced in \(1947\) by one of the pioneers of this area, Harold Wiener, who realized that there are correlations between the boiling points of paraffins and the structure of the molecules. The present paper is the first attempt to compute the Wiener index of an infinite class of fullerenes. Further, we obtain a correlation between the values of the Wiener index and the boiling point of such fullerenes for the first time.

A graph is said to be symmetric if its automorphism group is transitive on its arcs. A complete classification is given of pentavalent symmetric graphs of order \(40p\) for each prime \(p\). It is shown that a connected pentavalent symmetric graph of order \(40p\) exists if and only if \(p = 3\), and up to isomorphism, there are only two such graphs.

A broadcast on a graph \(G\) is a function \(f: V \to \{0, \dots, diam(G)\}\) such that for every vertex \(v \in V(G)\), \(f(v) \leq e(v)\), where \(diam(G)\) denotes the diameter of \(G\) and \(e(v)\) denotes the eccentricity of vertex \(v\). The upper broadcast domination number of a graph is the maximum value of \(\sum_{v \in V} f(v)\) among all minimal broadcasts \(f\) for which each vertex of the graph is within distance \(f(v)\) from some vertex \(v\) having \(f(v) \geq 1\). We give a new upper bound on the upper broadcast domination number which improves a previous result of Dunbar et al. in [Broadcasts in graphs, Discrete Applied Mathematics 154 (2006) 59-75]. We also prove that the upper broadcast domination number of any grid graph \(G_{m,n} = P_m \Box P_n\) equals \(m(n – 1)\).

For a vertex \(v\) of a graph \(G\), Zhu, Li, and Deng introduced the concept of implicit degree \(id(v)\), according to the degrees of the neighbors of \(v\) and the vertices at distance \(2\) with \(v\) in \(G\). For a subset \(S \subseteq V(G)\), let \(i\Delta_2(G, S)\) denote the maximum value of the implicit degree sum of two vertices of \(S\). In this paper, we will prove: Let \(G\) be a \(2\)-connected graph on \(n \geq 3\) vertices and \(d\) be a nonnegative integer. If \(i\Delta_2(G, S) \geq d\) for each independent set \(S\) of order \(\kappa(G) + 1\), then \(G\) has a cycle of length at least \(\min\{d, n\}\).

For a nonempty graph \(G = (V(G), E(G))\), a signed cycle dominating function on \(G\) is introduced by Xu in 2009 as a function \(f : E(G) \to \{1, -1\}\) such that \(\sum_{e \in E(C)} f(e) \geq 1\) for any induced cycle \(C\) of \(G\). A set \(\{f_1, f_2, \dots, f_d\}\) of distinct signed cycle dominating functions on \(G\) with the property that \(\sum_{i=1}^{d} f_i(e) \leq 1\) for each \(e \in E(G)\), is called a signed cycle dominating family (of functions) on \(G\). The maximum number of functions in a signed cycle dominating family on \(G\) is the signed cycle domatic number of \(G\), denoted by \(d’_{sc}(G)\). In this paper, we study the signed cycle domatic numbers in graphs and present sharp bounds for \(d’_{sc}(G)\). In addition, we determine the signed cycle domatic number of some special graphs.

Using partition theoretic methods we combinatorially interpret the four Ae Rogers—Ramanujan identities of Andrews, Schilling and Wamaar.

Let \(p > 165\) be a prime and let \(G\) be a cyclic group of order \(p\). Let \(S\) be a minimal zero-sum sequence with elements over \(G\), i.e., the sum of elements in \(S\) is zero, but no proper nontrivial subsequence of \(S\) has sum zero. We call \(S\) unsplittable, if there do not exist \(g \in S\) and \(x, y \in G\) such that \(g = x + y\) and \(Sg^{-1}x y\) is also a minimal zero-sum sequence. In this paper, we determine the structure of \(S\) which is an unsplittable minimal zero-sum sequence of length \(\frac{p-1}{2}\) or \(\frac{p-3}{2}\). Furthermore, if \(S\) is a minimal zero-sum sequence with \(|S| \geq \frac{p-3}{2}\), then \(ind(S) \leq 2\).

For two given graphs \(G_1\) and \(G_2\), the Ramsey number \(R(G_1, G_2)\) is the smallest integer \(x\) such that for any graph \(G\) of order \(n\), either \(G\) contains \(G_1\) or the complement of \(G\) contains \(G_2\). In this paper, we study a large class of trees \(T\) as studied by Cockayne in [3], including paths and trees which have a vertex of degree one adjacent to a vertex of degree two, as special cases. We evaluate some \(R(T’_m, B_m)\), where \(T’_n \in \mathbb{T}\) and \(B_m\) is a book of order \(m+2\). Besides, some bounds for \(R(T’_n, B_n)\) are obtained.

Graceful labeling of graphs is used in radar codes. In this work, we introduce a new version of gracefulness, which we call edge-even graceful labeling of graphs. We establish a necessary and sufficient condition for edge-even graceful labeling of path graphs \(P_n\), cycle graphs \(C_n\), and star graphs \(K_{1,n}\). We also prove some necessary and sufficient conditions for some path and cycle-related graphs, namely, Friendship, Wheel, Double wheel, and Fan graphs.

The Hamiltonian problem is a classical problem in graph theory. Most of the research on the Hamiltonian problem is looking for sufficient conditions for a graph to be Hamiltonian. For a vertex \(v\) of a graph \(G\), Zhu, Li, and Deng introduced the concept of implicit degree \(id(v)\), according to the degrees of its neighbors and the vertices at distance \(2\) with \(v\) in \(G\). In this paper, we will prove that: Let \(G\) be a \(2\)-connected graph on \(n \geq 3\) vertices. If the maximum value of the implicit degree sums of \(2\) vertices in \(S\) is more than or equal to \(n\) for each independent set \(S\) with \(\kappa(G) + 1\) vertices, then \(G\) is Hamiltonian.

Let \((d_1, d_2, \dots, d_n)\) be a sequence of positive integers with \(n-1 \geq d_1 \geq d_2 \geq \dots \geq d_n\). We give a characterization of \((d_1, d_2, \dots, d_n)\) that is the degree sequence of a graph with cyclomatic number \(k\). This simplifies the characterization of Erdős-Gallai.

We explore new combinatorial properties of overpartitions, which are natural generalizations of integer partitions. Building on recent work, we state general combinatorial identities between standard partition, overpartition, and regular partition functions. We provide both generating function and bijective proofs. We also prove congruences for certain overpartition functions combinatorially.

Let \(G\) be a simple graph on \(n\) vertices. The Laplacian Estrada index of \(G\) is defined as \(LEE(G) = \sum_{i=1}^{n} e^{\mu_i}\), where \(\mu_1, \mu_2, \dots, \mu_n\) are the Laplacian eigenvalues of \(G\). In this paper, threshold graphs on \(n\) vertices and \(m\) edges having maximal and minimal Laplacian Estrada index are determined, respectively.

In this paper, formulas of the resistance distance for the arbitrary two-vertex resistance of \(G\), \(H = G_1 \boxdot G_2\) and \(G_1 \boxminus G_2\) in the electrical networks are obtained in a much simpler way. Furthermore, \(K_f(G_1 \boxdot G_2)\) and \(K_f(G_1 \boxminus G_2)\) can be expressed as a combination of \(K_f(G_1)\) and \(K_f(G_2)\).

Networks are important structures and appear in many different applications and settings. The vulnerability value of a communication network shows the resistance of the network after the disruption of some centers or connection lines until a communication breakdown. Centrality parameters play an important role in the field of network analysis. Numerous studies have proposed and analyzed several centrality measures. These concepts measure the importance of a node’s position in a network. In this paper, vertex residual closeness \((VRC)\) and normalized vertex residual closeness \((NVRC)\) of some splitting networks modeled by splitting graphs are obtained.

Let \(T\) be an isosceles right triangle and let \(S_1, S_2, S_3, \dots\) be the homothetic copies of a square \(S\). In this paper, we consider the parallel covering and packing of \(T\) with the sequence \(\{S_n\}\) of squares.