Let \(G\) be a connected multigraph with an even number of edges and suppose that the degree of each vertex of \(G\) is even. Let \((uv, G)\) denote the multiplicity of edge \((u,v)\) in \(G\). It is well known that we can obtain a halving of \(G\) into two halves \(G_1\) and \(G_2\), i.e. that \(G\) can be decomposed into multigraphs \(G_1\) and \(G_2\), where for each vertex \(v\), \(\deg(v, G_1) = \deg(v, G_2) = \frac{1}{2}\deg(v,G)\). It is also easy to see that if the edges with odd multiplicity in \(G\) induce no components with an odd number of edges, then we can obtain such a halving of \(G\) into two halves \(G_1\) and \(G_2\) that is well-spread, i.e. for each edge \((u,v)\) of \(G\), \(|\mu(uv, G_1) – \mu(uv, G_2)| \leq 1\). We show that if \(G\) is a \(\Delta\)-regular multigraph with an even number of vertices and with \(\Delta\) being even, then even if the edges with odd multiplicity in \(G\) induce components with an odd number of edges, we can still obtain a well-spread halving of \(G\) provided that we allow the addition/removal of a Hamilton cycle to/from \(G\). We give an application of this result to obtaining sports schedules such that multiple encounters between teams are well-spread throughout the season.

A fractional edge coloring of graph \(G\) is an assignment of a nonnegative weight \(w_M\) to each matching \(M\) of \(G\) such that for each edge \(e\) we have \(\sum_{M\ni e} w_M \geq 1\). The fractional edge coloring chromatic number of a graph \(G\), denoted by \(\chi’_f(G)\), is the minimum value of \(\sum_{M} w_M\) (where the minimum is over all fractional edge colorings \(w\)). It is known that for any simple graph \(G\) with maximum degree \(\Delta\), \(\Delta < \chi'_f(G) \leq \Delta+1\). And \(\chi'_f(G) = \Delta+1\) if and only if \(G\) is \(K_{2n+1}\). In this paper, we give some sufficient conditions for a graph \(G\) to have \(\chi'_f(G) = \Delta\). Furthermore, we show that the results in this paper are the best possible.

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.