A subset \(D\) of the vertex set \(V\) of a graph is called an open odd dominating set if each vertex in \(V\) is adjacent to an odd number of vertices in \(D\) (adjacency is irreflexive). In this paper we solve the existence and enumeration problems for odd open dominating sets (and analogously defined even open dominating sets) in the \(m \times n\) grid graph and prove some structural results for those that do exist. We use a combination of combinatorial and linear algebraic methods, with particular reliance on the sequence of Fibonacci polynomials over \({GF}(2)\).

By introducing \(4\) colour classes in projective planes with non-Fano quads, discussion of the planes of small order is simplified.

Let \(G = (V, E)\) be a \(k\)-connected graph. For \(t \geq 3\), a subset \(T \subset V\) is a \((t,k)\)-shredder if \(|T| = k\) and \(G – T\) has at least \(t\) connected components. It is known that the number of \((t,k)\)-shredders in a \(k\)-connected graph on \(n\) nodes is less than \(\frac{2n}{2t – 3}\). We show a slightly better bound for the case \(k \leq 2t – 3\).

Let \(L\) and \(R\) be two graphs. For any positive integer \(n\), the Ehrenfeucht-Fraissé game \(G_n(L, R)\) is played as follows: on the \(i\)-th move, with \(1 \leq i \leq n\), the first player chooses a vertex on either \(L\) or \(R\), and the second player responds by choosing a vertex on the other graph. Let \(l_i\) be the vertex of \(L\) chosen on the \(i^{th}\) move, and let \(r_i\) be the vertex of \(R\) chosen on the \(i^{th}\) move. The second player wins the game iff the induced subgraphs \(L\{l_1,l_2,…,l_n\}\) and \(R\{r_1,r_2,…,r_n\}\) are isomorphic under the mapping sending \(l_i\) to \(r_i\). It is known that the second player has a winning strategy if and only if the two graphs, viewed as first-order logical structures (with a binary predicate E), are indistinguishable (in the corresponding first-order theory) by sentences of quantifier depth at most \(n\). In this paper we will give the first complete description of when the second player has a winning strategy for \(L\) and \(R\) being both paths or both cycles. The results significantly improve previous partial results.

By applying the method of generating function, the purpose of this paper is to give several summations of reciprocals related to \(l-th\) power of generalized Fibonacci sequences. As applications, some identities involving Fibonacci, Lucas numbers are obtained.

Bricks are polyominoes with labelled cells. The problem whether a given set of bricks is a code is undecidable in general. We consider sets consisting of square bricks only. We have shown that in this setting, the codicity of small sets (two bricks) is decidable, but \(15\) bricks are enough to make the problem undecidable. Thus the step from words to even simple shapes changes the algorithmic properties significantly (codicity is easily decidable for words). In the present paper we are interested whether this is reflected by quantitative properties of words and bricks. We use their combinatorial properties to show that the proportion of codes among all sets is asymptotically equal to \(1\) in both cases.

Let \(G_{n,m} = C_n \times P_m\), be the cartesian product of an \(n\)-cycle \(C_n\) and a path \(P_m\) of length \(m-1\). We prove that \(\chi'(G_{n,m}) = \chi'(G_{n,m}) = 4\) if \(m \geq 3\), which implies that the list-edge-coloring conjecture (LLECC) holds for all graphs \(G_{n,m}\).

Various authors have defined statistics on Dyck paths that lead to generalizations of the Catalan numbers. Three such statistics are area, maj, and bounce. Haglund, whe introduced the bounce statistic, gave an algebraic proof that \(n(n – 1)/2+\) area — bounce and maj have the same distribution on Dyck paths of order \(n\). We give an explicit bijective proof of the same result.

We develop a new type of a vertex labeling of graphs, namely \(2n\)-cyclic blended labeling, which is a generalization of some previously known labelings. We prove that a graph with this labeling factorizes the complete graph on \(2nk\) vertices, where \(k\) is odd and \(n, k > 1\).

Let \(D = (V, E)\) be a primitive digraph. The exponent of \(D\) at a vertex \(u \in V\), denoted by \(\text{exp}_D(u)\), is defined to be the least integer \(k\) such that there is a walk of length \(k\) from \(u\) to \(v\) for each \(v \in V\). Let \(V = \{v_1,v_2,\ldots ,v_n\}\). The vertices of \(V\) can be ordered so that \(\text{exp}_D(v_{i_1}) \leq \text{exp}_D(v_{i_2}) \leq \ldots \leq \text{exp}_D(v_{i_n})\). The number \(\text{exp}_D(v_{i_k})\) is called \(k\)-exponent of \(D\), denoted by \(\text{exp}_D(k)\). In this paper, we completely characterize \(1\)-exponent set of primitive, minimally strong digraphs with \(n\) vertices.