Let \(S\) be a primitive non-powerful signed digraph of order \(n\). The base of a vertex \(u\), denoted by \(l_S(u)\), is the smallest positive integer \(l\) such that there is a pair of SSSD walks of length \(i\) from \(u\) to each vertex \(v \in V(S)\) for any integer \(t \geq l\). We choose to order the vertices of \(S\) in such a way that \(l_S(1) \leq l_S(2) \leq \ldots \leq l_S(n)\), and call \(l_S(k)\) the \(k\)th local base of \(S\) for \(1 \leq k \leq n\). In this work, we use PNSSD to denote the class of all primitive non-powerful signed symmetric digraphs of order \(n\) with at least one loop. Let \(l(k)\) be the largest value of \(l_S(k)\) for \(S \in\) PNSSD, and \(L(k) = \{l_S(k) | S \in PNSSD\}\). For \(n \geq 3\) and \(1 \leq k \leq n-1\), we show \(I(k) = 2n – 1\) and \(L(k) = \{2, 3, \ldots, 2n-1\}\). Further, we characterize all primitive non-powerful signed symmetric digraphs whose \(k\)th local bases attain \(I(k)\).

Let \(\mathcal{U}_n(k)\) denote the set of all unicyclic graphs on \(n\) vertices with \(k\) (\(k \geq 1\)) pendant vertices. Let \(\diamondsuit_4^k\) be the graph on \(n\) vertices obtained from \(C_4\) by attaching \(k\) paths of almost equal lengths at the same vertex. In this paper, we prove that \(\diamondsuit_4^k\) is the unique graph with the largest Laplacian spectral radius among all the graphs in \(\mathcal{U}_n(k)\), when \(n \geq k + 4\).

For graphs \(G_1, G_2, \ldots, G_m\), the Ramsey number \(R(G_1, G_2, \ldots, G_m)\) is defined to be the smallest integer \(n\) such that any \(m\)-coloring of the edges of the complete graph \(K_n\) must include a monochromatic \(G_i\) in color \(i\), for some \(i\). In this note, we establish several lower and upper bounds for some Ramsey numbers involving quadrilateral \(C_4\), including:\(R(C_4, K_9) \leq 32,
19 \leq R(C_4, C_4, K_4)\leq 22, 31 \leq R(C_4, C_4, C_4, K_4) \leq 50, 52 \leq R(C_4, K_4, K_4) \leq 72, 42 \leq R(C_4, C_4, K_3, K_5) \leq 76, 87\leq R(C_4, C_4, K_4, K_4) \leq 179.\)

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.