A model for cleaning a graph with brushes was first introduced by Messinger, Nowakowski, and Pralat in 2008. Later, they focused on the problem of determining the maximum number of brushes needed to clean a graph. This maximum number of brushes needed to clean a graph in the model is called the broom number of the graph. In this paper, we show that the broom number of a graph is equal to the size of a maximum edge-cut of the graph, and prove the \(\mathcal{NP}\)-completeness of the problem of determining the broom number of a graph. As an application, we determine the broom number exactly for the Cartesian product of two graphs.

We give more results in mean cordial and harmonic mean labelings, such as: upper bounds for the number of edges of graphs of given orders for both labelings with direct results, labeling all trees of order \(\leq 9\) to be harmonic mean with the restriction of using the floor function of the definition, and labeling all graphs of order \(\leq 5\) that are harmonic mean graphs without using the label \(q + 1\) in labeling the vertices. Also, we give mean cordial labelings for some families of graphs.

Linkage is very important in Very Large Scale Integration (VLSI) physical design. In this paper, we mainly study the relationship between minors and linkages. Thomassen conjectured that every \((2k + 2)\)-connected graph is \(k\)-linked. For \(k \geq 4\), \(K_{3k-1}\) with \(k\) disjoint edges deleted is a counterexample to this conjecture, however, it is still open for \(k = 3\). Thomas and Wollan proved that every \(6\)-connected graph on \(n\) vertices with \(5n – 14\) edges is \(3\)-linked. Hence they obtain that every \(10\)-connected graph is \(3\)-linked. Chen et al. showed that every \(6\)-connected graph with \(K_{9}^-\) as a minor is \(3\)-linked, and every \(7\)-connected graph with \(K_{9}^-\) as a minor is \((2,2k-1)\)-linked. Using a similar method, we prove that every \(8\)-connected graph with \(K_{2k+3}^-\) as a minor is \(4\)-linked, and every \((2k + 1)\)-connected graph with \(K_{2k+3}^-\) as a minor is \((2,2k – 1)\)-linked. Our results extend Chen et al.’s conclusions, improve Thomas and Wollan’s results, and moreover, they give a class of graphs that satisfy Thomassen’s conjecture for \(k = 4\).

Consider any undirected and simple graph \(G = (V, E)\), where \(V\) and \(E\) denote the vertex set and the edge set of \(G\), respectively. Let \(|G| = |V| = n \geq 3\). The well-known Ore’s theorem states that if \(\deg_G(u) + \deg_G(v) \geq n + k\) holds for each pair of nonadjacent vertices \(u\) and \(v\) of \(G\), then \(G\) is traceable for \(k = -1\), Hamiltonian for \(k = 0\), and Hamiltonian-connected for \(k = 1\). In this paper, we investigate any graph \(G\) with \(\deg_G(u) + \deg_G(v) \geq n – 1\) for any nonadjacent vertex pair \(\{u,v\}\) of \(G\), in particular. We call it the \((*)\) condition. We derive four graph families, \(\mathcal{H}_i\), \(1 \leq i \leq 4\), and prove that all graphs satisfying \((*)\) are Hamiltonian-connected unless \(G \in \bigcup_{i=1}^{4} \mathcal{H}_i\). We also establish a comprehensive theorem for \(G\) satisfying \((*)\), which shows that \(G\) is traceable, Hamiltonian, pancyclic, or Hamiltonian-connected unless \(G\) belongs to different subsets of \(\{\mathcal{H}_i | 1 \leq i \leq 4\}\), respectively.

Given a group \(G\), we define the power graph \(P(G)\) as follows: the vertices are the elements of \(G\) and two vertices \(x\) and \(y\) are joined by an edge if \(\langle x\rangle \subseteq \langle y \rangle\) or \(\langle y\rangle \subseteq \langle x \rangle\). Obviously, the power graph of any group is always connected, because the identity element of the group is adjacent to all other vertices. In the present paper, among other results, we will find the number of spanning trees of the power graph associated with specific finite groups. We also determine, up to isomorphism, the structure of a finite group \(G\) whose power graph has exactly \(n\) spanning trees, for \(n < 5^{3}\). Finally, we show that the alternating group \(A_5\) is uniquely determined by the tree-number of its power graph among all finite simple groups.

Let \(G\) be a graph of order \(n\). The number of positive eigenvalues of \(G\) is called the positive inertia index of \(G\) and denoted by \(p(G)\). The minimum number of complete multipartite subgraphs in any complete multipartite graph edge decomposition of graph \(G\), in which the edge-induced subgraph of each edge subset of the decomposition is a complete multipartite graph, is denoted by \(\epsilon(G)\). In this paper, we prove \(\epsilon(G) \geq p(G)\) for any graph \(G\). Especially, if \(\epsilon(G) = 2\), then \(p(G) = 1\). We also characterize the graph \(G\) with \(p(G) = n – 2\).

The distance spectral gap of a connected graph is defined as the difference between its first and second distance eigenvalues. In this note, the unique \(n\)-vertex trees with minimal and maximal distance spectral gaps, and the unique \(n\)-vertex unicyclic graph with minimal distance spectral gap are determined.

A simple graph \(G = (V, E)\) admits an \(H\)-covering if every edge in \(E\) belongs to at least one subgraph of \(G\) isomorphic to a given graph \(H\). An \((a, d)\)-\(H\)-antimagic labeling of \(G\) admitting an \(H\)-covering is a bijective function \(f : V \cup E \rightarrow \{1, 2, \ldots, |V| + |E|\}\) such that, for all subgraphs \(H’\) of \(G\) isomorphic to \(H\), the \(H’\)-weights, \(wt(H’) = \sum_{v \in V(H’)} f(v) + \sum_{e \in E(H’)} f(e)\), constitute an arithmetic progression with the initial term \(a\) and the common difference \(d\). Such a labeling is called super if \(f(V) = \{1, 2, \ldots, |V|\}\). In this paper, we study the existence of super \((a, d)\)-\(H\)-antimagic labelings for graph operation \(G ^ H\), where \(G\) is a (super) \((b, d^*)\)-edge-antimagic total graph and \(H\) is a connected graph of order at least \(3\).

This article proves that the square of a Halin graph \(G\) with \(\Delta(G) = 5\) has the chromatic number \(6\). This gives a positive answer to an open problem in [Y. Wang, Distance two labelling of Halin graphs, Ars Combin. 114 (2014), 331–343].

There are many rectangular arrays whose \(n^{th}\) column is the \(n\)-fold convolution of the \(0^{th}\) column in combinatorics. For this type of rectangular arrays, we prove a formula for evaluating the determinant of certain submatrices, which was conjectured by Hoggatt and Bicknell. Our result unifies the determinant evaluation of submatrices of the rectangular arrays consisting of binomial coefficients, multinomial coefficients, Fibonacci numbers, Catalan numbers, generalized Catalan and Motzkin numbers.