Let \(\sigma_k(G)\) denote the minimum degree sum of \(k\) independent vertices of a graph \(G\). A spanning tree with at most \(3\) leaves is called a spanning \(3\)-ended tree. In this paper, we prove that for any \(k\)-connected claw-free graph \(G\) with \(|G| = n\), if \(\sigma_{k+3}(G) \geq n – k\), then \(G\) contains a spanning \(3\)-ended tree.

As a promotion of the channel assignment problem, an \(L(1,1,1)\)-labeling of a graph \(G\) is an assignment of nonnegative integers to \(V(G)\) such that the difference between labels of adjacent vertices is at least \(1\), and the difference between labels of vertices that are distance two and three apart is at least \(1\). About \(10\) years ago, many mathematicians considered colorings (proper, general, total or from lists) such that vertices (all or adjacent) are distinguished either by sets or multisets or sums. In this paper, we will study \(L(1,1,1)\)-labeling-number and \(L(1,1)\)-edge-labeling-number of the edge-path-replacement. From this, we will consider the total-neighbor-distinguishing coloring and the neighbor-distinguishing coloring of the edge-multiplicity-paths-replacements, give a reference for the conjectures: \(\text{tndis-}_\Sigma(G) \leq \Delta + 3\), \(\text{ndi}_\Sigma(G) \leq \Delta + 2\), and \(\text{tndi}_S(G) \leq \Delta + 3\) for the edge-multiplicity-paths-replacements \(G(rP_k)\) with \(k \geq 3\) and \(r \geq 1\).

A \(T\)-shape tree is a tree with exactly one of its vertices having maximal degree \(3\). In this paper, we consider a class of tricyclic graphs which is obtained from a \(T\)-shape tree by attaching three identical odd cycles \(C_ks\) to three vertices of degree \(1\) of the \(T\)-shape tree, respectively, where \(k \geq 3\) is odd. It is shown that such graphs are determined by their adjacency spectrum.

In this paper, we have proved that if a contraction critical \(8\)-connected graph \(G\) has no vertices of degree \(8\), then for every vertex \(x\) of \(G\), either \(x\) is adjacent to a vertex of degree \(9\), or there are at least \(4\) vertices of degree \(9\) such that every one of them is at distance \(2\) from \(x\).

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.