An independent set in a graph \(G\) is a subset \(I\) of the vertices such that no two vertices in \(I\) are adjacent. We say that \(I\) is a maximum independent set in \(G\) if no other independent set is larger than \(I\). In this paper, we study the problem of determining the second and third largest number of maximum independent sets among all trees and forests. Extremal graphs achieving these values are also given.

This paper is motivated by the concept of the signed \(k\)-independence problem and dedicated to the complexity of the problem on graphs. We show that the problem is linear-time solvable for any strongly chordal graph with a strong elimination ordering and polynomial-time solvable for distance-hereditary graphs. For any fixed positive integer \(k \geq 1\), we show that the signed \(k\)-independence problem on chordal graphs and bipartite planar graphs is NP-complete. Furthermore, we show that even when restricted to chordal graphs or bipartite planar graphs, the signed \(k\)-independence problem, parameterized by a positive integer \(k\) and weight \(\kappa\), is not fixed-parameter tractable.

Edge minimal Hamilton laceable bigraphs on \(2m\) vertices have at least \(\left\lfloor \frac{m+3}{6} \right\rfloor\) vertices of degree \(2\). If a bigraph is edge minimal with respect to Hamilton laceability, it is by definition edge critical, meaning the deletion of any edge will cause it to no longer be Hamilton laceable. The converse need not be true. The \(m\)-crossed prisms \([8]\) on \(4m\) vertices are edge critical for \(m \geq 2\) but not edge minimal since they are cubic. A simple modification of \(m\)-crossed prisms forms a family of “sausage” bigraphs on \(4m + 2\) vertices that are also cubic and edge critical. Both these families share the unusual property that they have exponentially many Hamilton paths between every pair of vertices in different parts. Even so, since the bigraphs are edge critical, deleting an arbitrary edge results in at least one pair having none.

In this paper, we investigate some new identities of symmetry for the Carlitz \(q\)-Bernoulli polynomials invariant under \(S_4\), which are derived from \(p\)-adic \(q\)-integrals on \(\mathbb{Z}_p\).

In this paper, we give the definition of acyclic total coloring and acyclic total chromatic number of a graph. It is proved that the acyclic total chromatic number of a planar graph \(G\) with maximum degree \(\Delta(G)\) and girth \(g\) is at most \(\Delta(G)+2\) if \(\Delta \geq 12\), or \(\Delta \geq 6\) and \(g \geq 4\), or \(\Delta = 5\) and \(g \geq 5\), or \(g \geq 6\). Moreover, if \(G\) is a series-parallel graph with \(\Delta \geq 3\) or a planar graph with \(\Delta \geq 3\) and \(g \geq 12\), then the acyclic total chromatic number of \(G\) is \(\Delta(G) + 1\).

Let \(G\) be a graph and \(\pi(G, x)\) its permanental polynomial. A vertex-deleted subgraph of \(G\) is a subgraph \(G – v\) obtained by deleting from \(G\) vertex \(v\) and all edges incident to it. In this paper, we show that the derivative of the permanental polynomial of \(G\) equals the sum of permanental polynomials of all vertex-deleted subgraphs of \(G\). Furthermore, we discuss the permanental polynomial version of Gutman’s problem [Research problem \(134\), Discrete Math. \(88 (1991) 105–106\)], and give a solution.

A semigraph G is edge complete if every pair of edges in G are adjacent. In this paper, we enumerate the non isomorphic semigraphs in one type of edge complete \((p,3)\) semigraphs without isolated vertices.

In this paper, the \(\lambda\)-number of the circular graph \(C(km, m)\) is shown to be at most \(9\) where \(m \geq 3\) and \(k \geq 2\), and the \(\lambda\)-number of the circular graph \(C(km + s, m)\) is shown to be at most \(15\) where \(m \geq 3\), \(k \geq 2\), and \(1 \leq s \leq m-1\). In particular, the \(\lambda\)-numbers of \(C(2m, m)\) and \(C(n, 2)\) are determined, which are at most \(8\). All our results indicate that Griggs and Yeh’s conjecture holds for circular graphs. The conjecture says that for any graph \(G\) with maximum degree \(\Delta \geq 2\), \(\lambda(G) \leq \Delta^2\). Also, we determine \(\lambda\)-numbers of \(C(n, 3)\), \(C(n, 4)\), and \(C(n, 5)\) if \(n \equiv 0 \pmod{7}\).

In this paper, we generalize the notion of solid bursts from classical codes equipped with Hamming metric \([14]\) to array codes endowed with RT-metric \([13]\) and obtain some bounds on the parameters of RT-metric array codes for the correction and detection of solid burst array errors.

Given a graph \(G = (V,E)\), a matching \(M\) of \(G\) is a subset of \(E\), such that every vertex of \(V\) is incident to at most one edge of \(M\). A \(k\)-matching is a matching with \(k\) edges. The total number of matchings in \(G\) is used in chemoinformatics as a structural descriptor of a molecular graph. Recently, Vesalian and Asgari (MATCH Commun. Math. Comput. Chem. \(69 (2013) 33–46\)) gave a formula for the number of \(5\)-matchings in triangular-free and \(4\)-cycle-free graphs based on the degrees of vertices and the number of vertices, edges, and \(5\)-cycles. But, many chemical graphs are not triangular-free or \(4\)-cycle-free, e.g., boron-nitrogen fullerene graphs (or BN-fullerene graphs). In this paper, we take BN-fullerene graphs into consideration and obtain formulas for the number of \(5\)-matchings based on the number of hexagons.