The crossing number of a graph \(G\) is the smallest number of pairwise crossings of edges among all the drawings of \(G\) in the plane. The pancake graph is an important network topological structure for interconnecting processors in parallel computers. In this paper, we prove the exact crossing number of the pancake graph \(P_4\) is six.

A planar graph is called \(C_4\)-free if it has no cycles of length four. Let \(f(n,C_4)\) denote the maximum size of a \(C_4\)-free planar graph with order \(n\). In this paper, it is shown that \(f(n,C_4) = \left\lfloor \frac{15}{7}(n-2) \right\rfloor – \mu\) for \(n \geq 30\), where \(\mu = 1\) if \(n \equiv 3 \pmod{7}\) or \(n = 32, 33, 37\), and \(\mu = 0\) otherwise.

The Harary spectral radius \(\rho(G)\) of a graph \(G\) is the largest eigenvalue of the Harary matrix \(RD(G)\). In this paper, we determine graphs with the largest Harary spectral radius in four classes of simple connected graphs with \(n\) vertices: with given matching number, vertex connectivity, edge connectivity, and chromatic number, respectively.

We consider the relationship between the minimum degree \(\delta(G\) of a graph and the complexity of recognizing if a graph is \(T\)-tenacious. Let \(T \geq 1\) be a rational number. We first show that if \(\delta(G) \geq \frac{Tn}{T+1}\) then \(G\) is \(T\)-tenacious. On the other hand, for any fixed \(\epsilon > 0\), we show that it is NP-hard to determine if \(G\) is \(T\)-tenacious, even for the class of graphs with \(\delta(G) \geq (\frac{T}{T+1} – \epsilon)n\).

Let \(G\) be a finite group and let \(S\) be a nonempty subset of \(G\). For any positive integer \(k\), let \(S^k\) be the subset product given by the set \(\{s_1 \cdots s_k \mid s_1, \ldots, s_k \in S\}\). If there exists a positive integer \(n\) such that \(S^n = G\), then \(S\) is said to be exhaustive. Let \(e(S)\) denote the smallest positive integer \(n\), if it exists, such that \(S^n = G\). We call \(e(S)\) the exhaustion number of the set \(S\). If \(S^n \neq G\) for any positive integer \(n\), then \(S\) is said to be non-exhaustive. In this paper, we obtain some properties of exhaustive and non-exhaustive subsets of finite groups.

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