We consider the problem of determining the \(Q\)-integral graphs, i.e., the graphs with integral signless Laplacian spectrum. First, we determine some infinite series of such graphs having the other two spectra (the usual one and the Laplacian) integral. We also completely determine all \((2, s)\)-semiregular bipartite graphs with integral signless Laplacian spectrum. Finally, we give some results concerning \((3, 4)\) and \((3, 5)\)-semiregular bipartite graphs with the same property.

Let \(G\) be a connected graph. For any two vertices \(u\) and \(v\), let \(d(u, v)\) denote the distance between \(u\) and \(v\) in \(G\). The maximum distance between any pair of vertices is called the diameter of \(G\) and denoted by \(diam(G)\). A radio-labeling (or multi-level distance labeling) with span \(k\) for \(G\) is a function \(f\) that assigns to each vertex a label from the set \(\{0, 1, 2, \ldots, k\}\) such that the following holds for any vertices \(u\) and \(v\): \(|f(u) – f(v)| \geq diam(G) – d(u, v) + 1\). The radio number of \(G\) is the minimum span over all radio-labelings of \(G\). The square of \(G\) is a graph constructed from \(G\) by adding edges between vertices of distance two apart in \(G\). In this article, we completely determine the radio number for the square of any path.

Let \(G\) be a simple connected graph containing a perfect matching. \(G\) is said to be BM-extendable if every matching \(M\) whose induced subgraph is a bipartite graph extends to a perfect matching of \(G\). In this paper, for recognizing BM-extendable graphs, we present some conditions in terms of vertex degrees, including the degree sum conditions, the minimum degree conditions, and the Fan-type condition. Furthermore, we show that all these conditions are best possible in some sense.

Let \(u\) be an odd vertex of a bipartite graph \(B\) and suppose that \(f : V(B) \to \mathbb{N}\) is a function such that \(f(u) = \left\lceil d_B(u)/2 \right\rceil\) and \(f(v) = \left\lceil d_B(v)/2 \right\rceil + 1\) for \(v \in V(B) \setminus u\), where \(d_B(v)\) is the degree of \(v\) in \(B\). In this paper, we prove that \(B\) is \(f\)-choosable.

An arc-colored digraph \(D\) is called alternating whenever \(\{(u, v), (v, w)\} \subseteq A(D)\) implies that the color assigned to \((u, v)\) is different from the color of \((v, w)\). In arc-colored digraphs, a set of vertices \(N\) is said to be a kernel by alternating paths whenever it is an independent and dominating set by alternating directed paths (there is no alternating directed path between every pair of its vertices and for every vertex not in \(N\), there exists an alternating path from it to some vertex in \(N\)). With this new concept, we generalize the concept of kernel in digraphs. In this paper, we prove the existence of alternating kernels in possibly infinite arc-colored digraphs with some coloration properties. We also state a bilateral relation between the property of every induced subdigraph of an arc-colored digraph \(D\) of having a kernel by alternating paths and the property of every induced subdigraph of the non-colored digraph \(D\) of having a kernel, with this we enounce several sufficient conditions for \(D\) to have an alternating kernel. Previous results on kernels are generalized.

In this paper, we present a new simple linear-time algorithm for determining the number of spanning trees in the class of complement reducible graphs, also known as cographs. For a cograph \(G\) on \(n\) vertices and \(m\) edges, our algorithm computes the number of spanning trees of \(G\) in \(O(n + m)\) time and space, where the complexity of arithmetic operations is measured under the uniform cost criterion. The algorithm takes advantage of the cotree of the input cograph \(G\) and works by contracting it in a bottom-up fashion until it becomes a single node. Then, the number of spanning trees of \(G\) is computed as the product of a collection of values which are associated with the vertices of \(G\) and are updated during the contraction process. The correctness of our algorithm is established through the Kirchhoff matrix tree theorem, and also relies on structural and algorithmic properties of the class of cographs. We also extend our results to a proper superclass of cographs, namely the \(P_4\)-reducible graphs, and show that the problem of finding the number of spanning trees of a \(P_4\)-reducible graph has a linear-time solution.

This paper extends the concept of paving from finite matroids to matroids of arbitrary cardinality. Afterwards, a paving matroid of arbitrary cardinality is characterized in terms of its collection of closed sets, independent sets, and circuits, respectively.

A Hamiltonian walk in a connected graph \(G\) is a closed walk of minimum length which contains every vertex of \(G\). The Hamiltonian number \(h(G)\) of a connected graph \(G\) is the length of a Hamiltonian walk in \(G\). Let \(\mathcal{G}(n)\) be the set of all connected graphs of order \(n\), \(\mathcal{G}(n, \kappa = k)\) be the set of all graphs in \(\mathcal{G}(n)\) having connectivity \(\kappa = k\), and \(h(n,k) = \{h(G) : G \in \mathcal{G}(n, \kappa = k)\}\). We prove in this paper that for any pair of integers \(n\) and \(k\) with \(1 \leq k \leq n – 1\), there exist positive integers \(a := \min(h;n,k)) = \min\{h(G) : G \in \mathcal{G}(n, \kappa = k)\}\) and \(b := \max(h;n,k)) = \max\{h(G) : G \in \mathcal{G}(n, \kappa = k)\}\) such that \((h;n,k) = \{x \in \mathbb{Z} : a \leq x \leq b\}\). The values of \(\min(h;n,k))\) and \(\max(h(n,k))\) are obtained in all situations.

A well-known result on matchings of graphs is that the intersection of all maximal barriers is equal to the “set A” in the Gallai-Edmonds decomposition. In this paper, we give a generalization of this result to the framework of path-matchings introduced by Cunningham and Geelen. Furthermore, we present a sufficient condition for a graph to have a perfect path-matching.

This paper describes some new methods of constructing rectangular designs from balanced incomplete block (BIB) designs and Hadamard matrices. At the end of the paper, a table of rectangular designs in the range of \(r\),\(k \leq 15\) is given.