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.

An \(n \times n\) sign pattern \(A\) is a spectrally arbitrary pattern if for any given real monic polynomial \(f(x)\) of degree \(n\), there is a real matrix \(B \in Q(A)\) having characteristic polynomial \(f(x)\). In this paper, we give two new classes of \(n \times n\) spectrally arbitrary sign patterns which are generalizations of the pattern \(W_{n}(k)\) defined in [T. Britz, J.J. McDonald, D.D. Olesky, P. van den Driessche, Minimal spectrally arbitrary sign patterns, SIAM Journal on Matrix Analysis and Applications, \(26(2004), 257-271]\).

We show that the power subgroups \(M^{6k}\) (\(k > 1\)) of the Modular group \(M = \text{PSL}(2, \mathbb{Z})\) are subgroups of the groups \(M'(6k, 6k)\). Here, the groups \(M'(6k, 6k)\) (\(k > 1\)) are subgroups of the commutator subgroup \(M’\) of \(M\) of index \(36k^2\) in \(M’\).

Let \(G\) be a simple graph. The double vertex graph \(U_2(G)\) of \(G\) is the graph whose vertex set consists of all \(2\)-subsets of \(V(G)\) such that two distinct vertices \(\{x,y\}\) and \(\{u,v\}\) are adjacent if and only if \(|\{x,y\} \cap \{u,v\}| = 1\) and if \(x = u\), then \(y\) and \(v\) are adjacent in \(G\). In this paper, we consider the exponents and primitivity relationships between a simple graph and its double vertex graph. A sharp upper bound on exponents of double vertex graphs of primitive simple graphs and the characterization of extremal graphs are obtained.