By eliminating the win condition in the game of Connect Four and extending the board to infinite height, a rich state space of positions is obtained. We investigate the number of positions reachable on an \(n\)-column board after \(k\) color-alternating moves. For fixed \(k\) we demonstrate polynomiality, derive a partial formula for the polynomial coefficients, and precisely characterize the asymptotic behavior as \(n \to \infty\). We then turn our attention to the fixed-\(n\) case and show that, under a natural addition operation, positions reachable in an even number of moves form a monoid with a highly symmetric finite generating set; by examining certain free submonoids, we bound the exponential growth rate as \(k \to \infty\).

Sterboul’s theorem characterizes non-Kőnig–Egerváry graphs by the presence, relative to a maximum matching, of a flower or a posy. In this paper we translate that obstruction into the language of perfect flowers and the core of the graph. We introduce core-defective perfect flowers: perfect flowers whose alternating path contains a vertex at odd distance from the blossom base that does not belong to the core. We prove first that every Kőnig–Egerváry graph is core-rigid: in every perfect flower, all odd-distance vertices of the attaching path lie in the core. Conversely, if \(G\) is connected and is not an odd cycle, then \(G\) is non-Kőnig–Egerváry if and only if \(G\) contains a core-defective perfect flower. Thus, among connected graphs different from an odd cycle, the Kőnig–Egerváry graphs are exactly the graphs with no core-defective perfect flower. In the matchable case the statement strengthens: if \(G\) has a perfect matching, then being non-Kőnig–Egerváry is equivalent to the existence of a core-defective perfect flower for some maximum matching, and also equivalent to the existence of one for every maximum matching. We include examples and counterexamples showing why odd cycles, disconnected graphs, and the universal quantifier over maximum matchings require separate treatment.

In this paper, we consider the relationship between toughness and the existence of \((g,f)\)-factors with inclusion/exclusion properties. We obtain that if \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)}\) with \(b > a \geq 2\) and \(a \leq g(x) < f(x) \leq b\) where \(a\), \(b\) are two integers, then for any two given edges \(e_{1}\) and \(e_{2}\), there exists a \((g,f)\)-factor including \(e_{1}\), \(e_{2}\); and a \((g,f)\)-factor including \(e_{1}\) and excluding \(e_{2}\); as well as a \((g,f)\)-factor excluding \(e_{1}\), \(e_{2}\).

An equitable vertex \(k\)-coloring of a graph \(G\) is a proper vertex coloring with \(k\) colors such that the size of any two color classes differ by at most one. It was conjectured by Meyer in 1973 that every graph other than the complete graph \(K_n\) or an odd cycle \(C_{2m+1}\) admits an equitable vertex coloring with at most \(\Delta(G)\) colors, where \(\Delta(G)\) is the maximum degree of a vertex in graph \(G\). We show that the conjecture is true for middle graphs of some cycle-based graphs.

A questionnaire is a sequence of multiple choice questions aiming to collect data on a population. We define an abstract questionnaire as an ordered pair \((N,\mathcal{M})\), where \(N\) is a positive integer and \(\mathcal{M}=(m_0,m_1,\ldots,m_{N-1})\) is an \(N\)-tuple of positive integers, with \(m_i\), for \(i \in \mathbb{Z}_N\), as the number of possible answers to question \(i\). An abstract questionnaire may be endowed with a skip-list (which tells us which questions to skip based on the sequence of answers to the earlier questions) and a flag-set (which tells us which sequences of answers are of special interest). An FS-decision tree is a decision tree of an abstract questionnaire that also incorporates the information contained in the skip-list and flag-set. The main objective of this paper is to represent the abstract questionnaire using a directed graph, which we call an FS-decision digraph, that contains the full information of an FS-decision tree, but is in general much more concise. We present an algorithm for constructing a fully reduced FS-decision digraph, and develop the theory that supports it. In addition, we show how to generate all possible orderings of the questions in an abstract questionnaire that respect a given precedence relation.

A hypergraph \(H\) is said to be \(r\)-partite \(r\)-uniform if its vertex set \(V\) can be partitioned into non-empty sets \(V_1, V_2, \cdots, V_r\) so that every edge in the edge set \(E(H)\), consists of precisely one vertex from each set \(V_i\), \(i=1,2,\cdots,r\). It is denoted as \(H^r(V_1,V_2,\cdots,V_r)\) or \(H^r_{(n_1,n_2,\cdots,n_r)}\) if \(|V_i|=n_i\) for \(i=1,2,\cdots,r\). There exists an \(r\)-partite self-complementary \(r\)-uniform hypergraph \(H^r(V_1,V_2,\cdots,V_r)\) where \(|V_i|=n_i\) for \(i=1,2,\cdots,r\) if and only if at least one of \(n_1,n_2,\cdots,n_r\) is even. And there exists an \(r\)-partite almost self-complementary \(r\)-uniform hypergraph \(H^r(V_1, V_2,\cdots,V_r)\) where \(|V_i|=n_i\) for \(i=1,2,\cdots,r\) if and only if \(n_1,n_2,\cdots,n_r\) are odd. In this paper, we prove the existence of regular \(3\)-partite self-complementary \(3\)-uniform hypergraphs. Further we prove there does not exist a regular \(3\)-partite almost self-complementary \(3\)-uniform hypergraph.

We study the difference between the numbers of even and odd permutations in \(\mathfrak{S}_n\) having exactly \(k\) fixed points. We derive a closed formula for this quantity using four complementary approaches: exponential generating functions, a determinant representation, a combinatorial derivation based on inclusion–exclusion on cycle structures, and a factorization via the stabilizer subgroup, through restriction to the complement of the fixed-point set. The resulting expression provides a signed refinement of the classical rencontres numbers and yields a simple polynomial form for the associated signed fixed-point distribution.

Let \(L(G(k))\) be a line graph of a \(k\)-subdivided graph \(G(k)\) of any connected, simple and undirected graph \(G\). In this paper, we fixed the valency dependence invariants of \(L(G(k))\) for \(k\geq2.\) Our results are the generalization of the results proved in [1,3,8].