A vertex-colored path is vertex-rainbow if its internal vertices have distinct colors. For a connected graph $G$ with connectivity $\kappa (G)$ and an integer $k$ with $1\le k\le \kappa (G)$, the rainbow vertex $k$-connectivity of $G$ is the minimum number of colors required to color the vertices of $G$ such that any two vertices of $G$ are connected by $k$ internally vertex-disjoint vertex-rainbow paths. In this paper, we determine the rainbow vertex $k$-connectivities of all small cubic graphs of order $8$ or less.

For a simple graph $G=(V,E)$, a vertex labeling $\alpha :V\to \{1,2,\dots ,k\}$ is called a $k$-labeling. The weight of an edge $xy$ in $G$, denoted by $w_{\varphi }(xy)$, is the sum of the labels of end vertices $x$ and $y$, i.e., $w_{\varphi }(xy)=\varphi (x)+\varphi (y)$. A vertex $k$-labeling is defined to be an edge irregular $k$-labeling of the graph $G$ if for every two different edges $e$ and $f$ there is $w_{\varphi }(e)\ne w_{\varphi }(f)$. The minimum $k$ for which the graph $G$ has an edge irregular $k$-labeling is called the edge irregularity strength of $G$, denoted by $\mathrm{e}\mathrm{s}(G)$. In this paper, we determine the exact value for certain families of graphs with path $P_2$.

We give a $q$-analogue of some Dixon-like summation formulas obtained by Gould and Quaintance [Fibonacci Quart. 48 (2010), 56-61] and Chu [Integral Transforms Spec. Funct. 23 (2012), 251-261], respectively. For example, we prove that
$\sum _{k=0}^{2m}(-1{)}^{m-k}{q}^{(\genfrac{}{}{0ex}{}{m-k}{2})}(\genfrac{}{}{0ex}{}{2m}{k})(\genfrac{}{}{0ex}{}{x+k}{2m+r})(\genfrac{}{}{0ex}{}{x+2m-k}{2m+r})$ = $\frac{q^{m(x-m-r)}(\genfrac{}{}{0ex}{}{2m}{m})}{(\genfrac{}{}{0ex}{}{2m+r}{m})}(\genfrac{}{}{0ex}{}{x}{m+r})(\genfrac{}{}{0ex}{}{x+m}{m+r})$ where $(\genfrac{}{}{0ex}{}{x}{k})$ denotes the $q$-binomial coefficient.

A pentangulation is a simple plane graph such that each face is bounded by a cycle of length $5$. We consider two diagonal transformations in pentangulations, called $\mathcal{A}$ and $\mathcal{B}$. In this paper, we shall prove that any two pentangulations with the same number of vertices can be transformed into each other by $\mathcal{A}$ and $\mathcal{B}$. In particular, if they are not isomorphic to a special pentangulation, then we do not need $\mathcal{B}$.

The harmonic index $H(G)$ of a graph $G$ is defined as the sum of the weights of all edges $uv$ of $G$, where the weight of $uv$ is $\frac{2}{d(u)+d(v)}$, with $d(u)$ denoting the degree of the vertex $u$ in $G$. In this work, we compute the harmonic index of a graph with a cut-vertex and with more than one cut-vertex. As an application, this topological index is computed for Bethe trees and dendrimer trees. Also, the harmonic indices of Fasciagraph and a special type of trees, namely, polytree, are computed.

Let $G^{\sigma }$ be an oriented graph obtained by assigning an orientation $\sigma$ to the edge set of a simple undirected graph $G$. Let $S(G^{\sigma })$ be the skew adjacency matrix of $G^{\sigma }$. The skew energy of $G^{\sigma }$ is defined as the sum of the absolute values of all eigenvalues of $S(G^{\sigma })$. In this paper, we give the skew energy order of a family of digraphs and determine the oriented bicyclic graphs of order $n\ge 13$ with the first five largest skew energies, which extends the results of the paper [X. Shen, Y. Hou, C. Zhang, Bicyclic digraphs with extremal skew energy, Electron. J. Linear Algebra 23 (2012) 340-355].

Let $P_n$ denote the $n$-th Catalan-Larcombe-French number. Recently, the $2$-log-convexity of the Catalan-Larcombe-French sequence was proved by Sun and Wu. Moreover, they also conjectured that the quotient sequence $\{\frac{P_n}{P_{n-1}}{\}}_{n=0}^{\mathrm{\infty }}$ of the Catalan-Larcombe-French sequence is log-concave. In this paper, this conjecture is confirmed by utilizing the upper and lower bounds for $\frac{P_n}{P_{n-1}}$ and finding a middle function $f(n)$.

It is claimed in [13] that the metric dimension of the Möbius ladder $M_n$ is $3$ when $n\not\equiv 2(\mathrm{mod}8)$, but it is wrong; we give a counterexample when $n\equiv 6(\mathrm{mod}8)$. In this paper, we not only give the correct metric dimension in this case but also solve the open problem regarding the metric dimension of $M_n$ when $n\equiv 2(\mathrm{mod}8)$. Moreover, we conclude that $M_n$ has two subfamilies with constant metric dimensions.

An edge-colored graph $G$ is (strong) rainbow connected if any two vertices are connected by a (geodesic) path whose edges have distinct colors. The (strong) rainbow connection number of a connected graph $G$, denoted by $\mathrm{s}\mathrm{r}\mathrm{c}(G)$ (resp. $\mathrm{r}\mathrm{c}(G)$), is the smallest number of colors that are needed in order to make $G$ (strong) rainbow connected. The join $P_m\vee P_n$ of $P_m$ and $P_n$ is the graph consisting of $P_m\cup P_n$, and all edges between every vertex of $P_m$ and every vertex of $P_n$, where $P_m$ (resp. $P_n$) is a path of $m$ (resp. $n$) vertices. In this paper, the precise values of $\mathrm{r}\mathrm{c}(P_m\vee P_n)$ and $\mathrm{s}\mathrm{r}\mathrm{c}(P_m\vee P_n)$ are given for any positive integers $m$ and $n$.

Let $MG(i,n)$ be a connected molecular graph without multiple edges on $n$vertices whose minimum degree of vertices is $i$, where $i\le i\le 4$. One of the newest topological indices is the first Geometric-Arithmetic index. In this paper, we determine the graph with the minimum and the maximum value of the first Geometric-Arithmetic index in the family of graphs $MG(i,n)$,$l\le i\le 3$.

Two graphs are said to be Tutte-equivalent if their Tutte polynomials are equal. In this paper, we provide several different constructions for Tutte-equivalent graphs, including some that are not self-complementary but Tutte-equivalent to their complements (the Akiyama-Harary problem) and some “large” Tutte-equivalent graphs obtained from “small” Tutte-equivalent graphs by $2$-sum operations.

Let $s(n,k)=(\genfrac{}{}{0ex}{}{6k}{3k})(\genfrac{}{}{0ex}{}{3k}{k})((\genfrac{}{}{0ex}{}{3(n-k)}{n-k})/(2n-1)(\genfrac{}{}{0ex}{}{3n}{n}))$. Recently, Guo confirmed a conjecture of $Z.-W$. Sun by showing that $s(n,k)$ is an integer for $k=0,1,\dots ,n$. Let $d=(3n+2)/gcd(3n+2,2n–1)$. In this paper, we prove that $s(n,k)$ is a multiple of the odd part of $d$ for $k=0,1,\dots ,n$. Furthermore, if $gcd(k,n)=1$, then $s(n,k)$ is also a multiple of $n$. We also show that the $2$-adic order of $s(n,k)$ is at least the sum of the digits in the binary expansion of $3n$.

For any non-trivial abelian group $A$ under addition, a graph $G$ is said to be strong $A$-magic if there exists a labeling $f$ of the edges of $G$ with non-zero elements of $A$ such that the vertex labeling $f^{+}$ defined as $f^{+}(v)=\sum f(uv)$ taken over all edges $uv$ incident at $v$ is a constant, and the constant is same for all possible values of $|V(G)|$. A graph is said to be strong $A$-magic if it admits strong $A$-magic labeling. In this paper, we consider $({\mathbb{Z}}_4,+)$ as an abelian group and we prove strong ${\mathbb{Z}}_4$-magic labeling for various graphs and generalize strong ${\mathbb{Z}}_{4p}$-magic labeling for those graphs. The graphs which admit strong ${\mathbb{Z}}_{4p}$-magic labeling are called as strong ${\mathbb{Z}}_{4p}$-magic graphs.

The well-known Mantel’s Theorem states that a graph on $n$ vertices and $m$ edges contains a triangle if $m>\frac{n^2}{4}$. Nosal proved that every graph on $m$ edges contains a triangle if the spectral radius ${\lambda }_1>\sqrt{m}$, which is a spectral analog of Mantel’s Theorem. Furthermore, by using Motzkin-Straus Inequality, Nikiforov sharpened Nosal’s result and characterized the extremal graphs when the equality holds. Our first contribution in this note is to give two new proofs of the spectral concise Mantel’s Theorem due to Nikiforov (without help of Motzkin-Straus Inequality). Nikiforov also obtained some results concerning the existence of consecutive cycles and spectral radius. Second, we prove a theorem concerning the existence of consecutive even cycles and spectral radius, which slightly improves a result of Nikiforov. At last, we focus on spectral radius inequalities. Hong proved his famous bound for spectral radius. Later, Hong, Shu, and Fang generalized Hong’s bound to connected graphs with given minimum degree. By using quite different techniques, Nikiforov proved Hong et al.’s bound for general graphs independently. In this note, we prove a new spectral inequality by applying the technique of Nikiforov. Our result extends Stanley’s spectral inequality.

The alliance polynomial of a graph with order $n$ and maximum degree $\mathrm{\Delta }$ is the polynomial $A(\mathrm{\Gamma };x)=\sum _{k=-{\delta }_1}^{{\delta }_1}{A}_k(\mathrm{\Gamma })x^{n+k}$, where $A_k(G)$ is the number of exact defensive $k$-alliances in $G$. We provide an algorithm for computing the alliance polynomial. Furthermore, we obtain some properties of $A(\mathrm{\Gamma };x)$ and its coefficients. In particular, we prove that the path, cycle, complete, and star graphs are characterized by their alliance polynomials. We also show that the alliance polynomial characterizes many graphs that are not distinguished by other usual polynomials of graphs.

Let $a$, $b$, and $k$ be three nonnegative integers with $a\ge 2$ and $b\ge a(k+1)+2$. A graph $G$ is called a $k$-Hamiltonian graph if $G–U$ contains a Hamiltonian cycle for every subset $U\subseteq V(G)$ with $|U|=k$. An $[a,b]$-factor $F$ of $G$ is called a Hamiltonian $[a,b]$-factor if $F$ contains a Hamiltonian cycle. If $G–U$ has a Hamiltonian $[a,b]$-factor for every subset $U\subseteq V(G)$ with $|U|=k$, then we say that $G$ admits a $k$-Hamiltonian $[a,b]$-factor. Suppose that $G$ is a $k$-Hamiltonian graph of order $n$ with $n\ge a+k+2$. In this paper, it is proved that $G$ includes a $k$-Hamiltonian $[a,b]$-factor if $\delta (G)\ge a+k$ and $t(G)\le a-1+\frac{(a-1)(k+1)}{b-2}$.

Graph embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. An embedding $f$ of a guest graph $G$ into a host graph $H$ is a bijection on the vertices such that each edge of $G$ is mapped into a path of $H$. In this paper, we introduce a graph called the generalized book and the main results obtained are: (1) For $r\ge 3$, the minimum wirelength of embedding $r$-dimensional hypercube $Q_r$ into the generalized book $\mathrm{G}\mathrm{B}[2^{r_1},2^{r_2},2^{r_3}]$, where $r_1+r_2+r_3=r$. (2) A linear time algorithm to compute the exact wirelength of embedding hypercube into generalized book. (3) An algorithm for embedding hypercube into generalized book with dilation 3, proving that the lower bound obtained by Manuel et al. [28] is sharp.

In this paper, we present a new approach to the convolved Fibonacci numbers arising from the generating function of them and give some new and explicit identities for the convolved Fibonacci numbers.

The generalized Fibonacci cube $Q_d(f)$ is the graph obtained from the hypercube $Q_d$ by removing all vertices that contain a given binary word $f$. A binary word $f$ is called good if $Q_d(f)$ is an isometric subgraph of $Q_d$ for all $d\ge 1$, and bad otherwise. A non-extendable sequence of contiguous equal digits in a word $f$ is called a block of $f$. The question to determine the good (bad) words consisting of at most three blocks was solved by Ilié, Klavžar, and Rho. This question is further studied in the present paper. All the good (bad) words consisting of four blocks are determined completely, and all bad $2$-isometric words among consisting of at most four blocks words are found to be $1100$ and $0011$.

In this paper, we provide a construction of $\mathrm{P}\mathrm{G}(2,4)$ by a collage of $\mathrm{A}\mathrm{G}(2,3)$ and its dual $\mathrm{D}\mathrm{A}\mathrm{G}(2,3)$. Moreover, we prove that the construction is unique.

In this paper, we first present a combinatorial proof of the recurrence relation about the number of the inverse-conjugate compositions of $2n+1$, $n>1$. And then we get some counting results about the inverse-conjugate compositions for special compositions. In particular, we show that the number of the inverse-conjugate compositions of $4k+1$, $k>0$ with odd parts is $2^k$, and provide an elegant combinatorial proof. Lastly, we give a relation between the number of the inverse-conjugate odd compositions of $4k+1$ and the number of the self-inverse odd compositions of $4k+1$.

In this study, by using Jacobsthal and Jacobsthal Lucas matrix sequences, we define $k$-Jacobsthal and $k$-Jacobsthal Lucas matrix sequences depending on one parameter $k$. After that, by using two parameters $(s,t)$, we define $(s,t)$-Jacobsthal and $(s,t)$-Jacobsthal Lucas matrix sequences. And then, we establish combinatoric representations of all of these matrices.

A graph $G$ is $1$-planar if it can be embedded in the plane ${\mathbb{R}}^2$ so that each edge of $G$ is crossed by at most one other edge. In this paper, we show that each $1$-planar graph of maximum degree $\mathrm{\Delta }$ at least $7$ with neither intersecting triangles nor chordal $5$-cycles admits a proper edge coloring with $\mathrm{\Delta }$ colors.

Dirac showed that in a $(k-1)$-connected graph there is a path through each $k$ vertices. The path $k$-connectivity ${\pi }_k(G)$ of a graph $G$, which is a generalization of Dirac’s notion, was introduced by Hager in 1986. Recently, Mao introduced the concept of path $k$-edge-connectivity ${\omega }_k(G)$ of a graph $G$. Denote by $G\circ H$ the lexicographic product of two graphs $G$ and $H$. In this paper, we prove that ${\omega }_4(G\circ H)\ge {\omega }_4(G)|V(H)|$ for any two graphs $G$ and $H$. Moreover, the bound is sharp.

A graph $G=(V(G),E(G))$ is even graceful and equivalently graceful, if there exists an injection $f$ from the set of vertices $V(G)$ to $\{0,1,2,3,4,\dots ,2|E(G)|\}$ such that when each edge $uv$ is assigned the label $|f(u)–f(v)|$, the resulting edge labels are $2,4,6,\dots ,2|E(G)|$. In this work, we use even graceful labeling to give a new proof for necessary and sufficient conditions for the gracefulness of the cycle graph. We extend this technique to odd graceful and super Fibonacci graceful labelings of cycle graphs via some number theoretic concept, called a balanced set of natural numbers.

A graph is $1$-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we prove that every $1$-planar graph without $4$-cycles or adjacent $5$-vertices is $5$-colorable.

In previous researches on classification problems, there are some similar results obtained between $f$-coloring and $g_c$-coloring. In this article, the author shows that there always are coincident classification results for a regular simple graph $G$ when the $f$-core and the $g_c$-core of $G$ are same and $f(v)=g(v)$ for each vertex $v$ in the $f$-core (the $g_c$-core) of $G$. However, it is not always coincident for nonregular simple graphs under the same conditions. In addition, the author obtains some new results on the classification problem of $f$-colorings for regular graphs. Based on the coincident correlation mentioned above, new results on the classification problem of $g_c$-colorings for regular graphs are deduced.

The integrity of a graph $G=(V,E)$ is defined as $I(G)=min\{|S|+m(G-S):S\subseteq V(G)\}$, where $m(G-S)$ denotes the order of the largest component in the graph $G-S$. This is a better parameter to measure the stability of a network, as it takes into account both the amount of work done to damage the network and how badly the network is damaged. Computationally, it belongs to the class of intractable problems known as NP-hard. In this paper, we develop a heuristic algorithm to determine the integrity of a graph. Extensive computational experience on $88$ randomly generated graphs ranging from $20\mathrm{\%}$ to $90\mathrm{\%}$ densities and from $100$ to $200$ vertices has shown that the proposed algorithm is very effective.

The half of an infinite lower triangular matrix $G=(g_{n,k}{)}_{n,k\ge 0}$ is defined to be the infinite lower triangular matrix $G^{(1)}=(g_{n,k\ge 0}^{(1)})$ such that $g_{n,k}^{(1)}=g_{2n-k,n}$ for all $n\ge k\ge 0$. In this paper, we will show that if $G$ is a Riordan array, then its half $G^{(1)}$ is also a Riordan array. We use Lagrange inversion theorem to characterize the generating functions of $G^{(1)}$ in terms of the generating functions of $G$. Consequently, a tight relation between $G^{(1)}$ and the initial array $G$ is given, hence it is possible to invert the process and rebuild the original Riordan array $G$ from the array $G^{(1)}$. If the process of taking half of a Riordan array $G$ is iterated $r$ times, then we obtain a Riordan array $G^{(r)}$. The further relation between the result array $G^{(r)}$ and the initial array $G$ is also considered. Some examples and applications are presented.

A graph $G$ is list $k$-arborable if for any sets $L(v)$ of cardinality at least $k$ at its vertices, one can choose an element (color) for each vertex $v$ from its list $L(v)$ so that the subgraph induced by every color class is an acyclic graph (a forest). In the paper, it is proved that every planar graph with $5$-cycles not adjacent to $3$-cycles and $4$-cycles is list $2$-arborable.

For two vertices $u$ and $v$ in a strong digraph $D$, the strong distance between $u$ and $v$ is the minimum number of arcs of a strong subdigraph of $D$ containing $u$ and $v$. The strong eccentricity of a vertex $v$ of $D$ is the strong distance between $v$ and a vertex farthest from $v$. The strong diameter (strong radius) of $D$ is the maximum (minimum) strong eccentricity among all vertices of $D$. The lower orientable strong diameter (lower orientable strong radius), $\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)$ ($\mathrm{s}\mathrm{r}\mathrm{a}\mathrm{d}(G)$), of a 2-edge-connected graph $G$ is the minimum strong diameter (minimum strong radius) over all strong orientations of $G$. In this paper, a conjecture of Chen and Guo is disproved by proving $\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(K_3\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_3)=\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(K_3\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_4)=5$, $\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(K_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)$ is determined, $\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)$ and $\mathrm{s}\mathrm{r}\mathrm{a}\mathrm{d}(G)$ for cycle vertex multiplications are computed, and some results concerning $\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)$ are described.

The aim of this note is to present a short proof of a result of Alaeiyan et al. [Bull. Austral. Math. Soc.$77(2008)315-323;$
Proc. Indian Acad. Sci., Math. Sci. $119(2009)647-653$] concerning the non-existence of cubic semisymmetric graphs of order $8p$ or $8p^2$, where $p$ is a prime. In those two papers, the authors choose the heavy weaponry of covering techniques. Our proof relies on the analysis of the subgroup structure of the full automorphism group of the graph and the normal quotient graph theory.

Let $G$ be a graph of order $n$ with adjacency matrix $A(G)$ and diagonal degree matrix $D(G)$. The generalized characteristic polynomial of $G$ is defined to be $f_G(x,t)=det(x{I}_n–(A(G)–tD(G)))$. The $R$-graph of $G$, denoted by $R(G)$, is obtained by adding a new vertex for each edge of $G$ and joining each new vertex to both end vertices of the corresponding edge. The generalized $R$-vertex corona, denoted by $R(G)⊡{\wedge }_i^{n}H$, is the graph obtained from $R(G)$ and $H$ by joining the $i$-th vertex of $V(G)$ to every vertex of $H$. In this paper, we determine the generalized characteristic polynomial of $R(G)⊡{\wedge }_i^{n}H$. As applications, we get infinitely many pairs of generalized cospectral graphs, the number of spanning trees and Kirchhoff index of $R(G)⊡{\wedge }_i^{n}H$.

In this paper, we introduce an $O(n^2)$ time algorithm to determine the cyclic edge connectivity of a planar graph, where $n$ is the order of the planar graph. This is the first correct square time algorithm for cyclic edge connectivity of planar graphs.

Let $G=(V,E)$, with $|V|=n$, be a simple connected graph. An edge-colored graph $G$ is rainbow edge-connected if any two vertices are connected by a path whose edges are colored by distinct colors. The rainbow connection number of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow edge-connected. In this paper, we obtain tight bounds for $rc(G)$. We use our results to generalize previous results for graphs with $\delta (G)\ge 3$.

In this paper, we provide the 4-way combinatorial interpretations of some Rogers–Ramanujan type identities using partitions with “$n+t$ copies of $n$”, lattice paths, $k$-partitions, and ordinary partitions.

In this paper, we study the Fibonacci polynomials modulo $m$ such that $x^2=x+1$ and then we obtain miscellaneous properties of these sequences. Also, we extend the Fibonacci polynomials to the ring of complex numbers. We define the Fibonacci Polynomial-type orbits $F_{(a,b)}^R(x)=\{x_i\}$, where $R$ is a 2-generator ring and $(a,b)$ is a generating pair of the ring $R$. Furthermore, we obtain the periods of the Fibonacci Polynomial-type orbits $F_{(a,b)}^R(x)$ in finite 2-generator rings of order $p^2$.

A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. We show that every graph of order $n\ge 12$ and size at least$max\{\lceil \frac{3n+79}{2}\rceil ,\lfloor \frac{11n-33}{2}\rfloor \}$ contains three disjoint theta graphs. As a corollary, every graph of order $n\ge 12$ and size at least $max\{\lceil \frac{3n+79}{2}\rceil ,\lfloor \frac{11n-33}{2}\rfloor \}$ contains three disjoint cycles of even length. The lower bound on the size is sharp in general.

A simple undirected graph is said to be semisymmetric if it is regular and edge-transitive but not vertex-transitive. A semisymmetric graph must be bipartite whose automorphism group has two orbits of the same size on the vertices. One of our long-term goals is to determine all the semisymmetric graphs of order $2p^3$, for any prime $p$. All these graphs $\mathrm{\Gamma }$ with the automorphism group $Aut(\mathrm{\Gamma })$, are divided into two subclasses: (I) $Aut(\mathrm{\Gamma })$ acts unfaithfully on at least one bipart; and (II) $Aut(\mathrm{\Gamma })$ acts faithfully on both biparts. In [9],[19] and [20], a complete classification was given for Subclass (I). In this paper, a partial classification is given for Subclass (II), when $Aut(\mathrm{\Gamma })$ acts primitively on one bipart.

The notions of $L$-tree-coloring and list vertex arboricity of graphs are introduced in the paper, while a sufficient condition for a plane graph admitting an $L$-tree-coloring is given. Further, it is proved that every graph without $K_5$-minors or $K_{3,3}$-minors has list vertex arboricity at most $3$, and this upper bound is sharp.

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{N}\mathcal{P}$-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 $\le 9$ to be harmonic mean with the restriction of using the floor function of the definition, and labeling all graphs of order $\le 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\ge 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\ge 3$. The well-known Ore’s theorem states that if ${\mathrm{deg}}_G(u)+{\mathrm{deg}}_G(v)\ge 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 ${\mathrm{deg}}_G(u)+{\mathrm{deg}}_G(v)\ge n–1$ for any nonadjacent vertex pair $\{u,v\}$ of $G$, in particular. We call it the $(\ast )$ condition. We derive four graph families, ${\mathcal{H}}_i$, $1\le i\le 4$, and prove that all graphs satisfying $(\ast )$ are Hamiltonian-connected unless $G\in \bigcup _{i=1}^4{\mathcal{H}}_i$. We also establish a comprehensive theorem for $G$ satisfying $(\ast )$, which shows that $G$ is traceable, Hamiltonian, pancyclic, or Hamiltonian-connected unless $G$ belongs to different subsets of $\{{\mathcal{H}}_i|1\le i\le 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 $⟨x⟩\subseteq ⟨y⟩$ or $⟨y⟩\subseteq ⟨x⟩$. 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 $ϵ(G)$. In this paper, we prove $ϵ(G)\ge p(G)$ for any graph $G$. Especially, if $ϵ(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\to \{1,2,\dots ,|V|+|E|\}$ such that, for all subgraphs $H^{\prime }$ of $G$ isomorphic to $H$, the $H^{\prime }$-weights, $wt(H^{\prime })=\sum _{v\in V(H^{\prime })}f(v)+\sum _{e\in E(H^{\prime })}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,\dots ,|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^{\ast })$-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 $\mathrm{\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.