The crossing number of a graph \(G\) is the minimum number of pairwise intersections of edges in a drawing of \(G\). The \(n\)-dimensional locally twisted cubes \(LTQ_n\), proposed by X.F. Yang, D.J. Evans and G.M. Megson, is an important interconnection network with good topological properties and applications. In this paper, we mainly obtain an upper bound on the crossing number of \(LTQ_n\), no more than \(\frac{265}{6}4^{n-4} – (n^2 + \frac{15+(-1)^{n-1}}{6}2^{n-3}\).

Let \(G\) be an infinite geometric graph; in particular, a graph whose vertices are a countable discrete set of points on the plane, with vertices \(u, v\) adjacent if their Euclidean distance is less than 1. A “fire” begins at some finite set of vertices and spreads to all neighbors in discrete steps; in the meantime, \(f\) vertices can be deleted at each time-step. Let \(f(G)\) be the least \(f\) for which any fire on \(G\) can be stopped in finite time. We show that if \(G\) has bounded density, in the sense that no open disk of radius \(r\) contains more than \(\lambda\) vertices, then \(f(G)\) is bounded above by ceiling of a universal constant times \(\frac{\lambda}{r^2}\). Similarly, if the density of \(G\) is bounded from below in the sense that every open disk of radius \(r\) contains at least \(\beta\) vertices, then \(f(G)\) is bounded below by \(\kappa\) times the square of the floor of a universal constant times \(\frac{1}{r}\).

Let \(G\) be a graph, and let \(k \geq 2\) be an integer. A graph \(G\) is fractional independent-set-deletable \(k\)-factor-critical (in short, fractional ID-\(k\)-factor-critical) if \(G – I\) has a fractional \(k\)-factor for every independent set \(I\) of \(G\). In this paper, a Fan-type condition for fractional ID-\(k\)-factor-critical graphs is given.

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.