A family \(\mathcal{F}\) of finite sets is said to have property \(B\) if there exists a set \(S\) such that \(0 < |{S} \cap F| < |F|\) for all \(F \in \mathcal{F}\). Denote by \(m_N(n)\) the least integer \(m\) for which there exists a family \(\mathcal{F}\) of \(m\) \(n\)-element subsets of a set \(V\) of size \(N\) such that \(\bigcup \mathcal{F} = V\) and which does not have property \(B\). We give constructions which yield upper bounds for \(m_N(4)\) for certain values of \(N\).

Let \(G\) be a connected graph and \(\mathcal{V}^*\) the set of all spanning trees except stars in \(G\). An edge in a spanning tree is called `inner’ if the edge is not incident to endvertices. Define an adjacency relation in \(\mathcal{V}^*\) as follows: two spanning trees \(t_1\) and \(t_2 \in \mathcal{V}^*\) are called to be adjacent if there exist inner edges \(e_i \in E(t_i)\) such that \(t_1 – e_1 = t_2 – e_2\). The resultant graph is a subgraph of the tree graph, and we call it simply a trunk graph. The purpose of this paper is to show that if a \(2\)-connected graph with at least five vertices is \(k\)-edge connected, then its trunk graph is \((k-1)\)-connected.

Let \(\tau(n)\) denote Ramanujan’s tau function. We obtain an identity that involves \(\tau(n)\) and \(\sigma(n)\), as well as some apparently new congruence properties of \(\tau(n)\) with respect to the moduli \(23\) and \(5\).

For loopless multigraphs \(G\), the total choice number is asymptotically equal to its fractional counterpart as the latter invariant tends to infinity. If \(G\) is embedded in the plane, then the edge-face and entire choice numbers exhibit the same “asymptotically good” behaviour. These results are based mainly on an analogous theorem of Kahn [5] for the list-chromatic index. Together with work of Kahn and others, our three results give a complete answer to a natural question: which of the seven invariants associated with list-colouring the nonempty subsets of \(\{V, E, F\}\) are asymptotically good?

In 1970, Behzad, Chartrand and Wall conjectured that the girth of every \(r\)-regular digraph \(G\) of order \(n\) is at most \(\left\lceil \frac{n}{r} \right\rceil\). The conjecture follows from a theorem of Menger and Dirac if \(G\) has strong connectivity \(x = r\). We show that any digraph with minimum in-degree and out-degree at least \(r\) has girth at most \(\left\lceil \frac{n}{r} \right\rceil\) if \(\kappa = r – 1\). We also find from the literature a family of counterexamples to a conjecture of Seymour.

In this paper, we give an alternative proof for the fact that the graph obtained by overlapping the cycle \(C_m\) (\(m \geq 3\)) and the complete bipartite graph \(K_{2,s}\) (\(s \geq 1\)) at an edge is uniquely determined by its chromatic polynomial. This result provides a partial solution to a question raised in [7].

Let \(G\) be a simple graph with \(n\) vertices. \(p(G,k)\) denotes the number of ways in which one can select \(k\) independent edges in \(G\) (\(k \geq 1\)). Let \(p(G,0) = 1\) for all \(G\).
The matching polynomial \(\alpha(G)\) of a graph \(G\) is given by:
\[\alpha(G) = \alpha(G,x) = \sum_{k=0}^{\left[\frac{n}{2}\right]} (-1)^k p(G,k) x^{n-2k}\]

In this article, we give the matching polynomials of the complete \(n\)-partite graph with a differential operator.

The List Edge Coloring Conjecture states that for every graph, the chromatic index equals the choice index. We prove the conjecture for outerplanar graphs with maximum degree at least five.

Cycle prefix digraphs are a class of Cayley coset graphs with many remarkable properties, such as:Symmetry Large number of nodes for a given degree and diameter Simple shortest path routing Hamiltonicity Optimal connectivity Others.
In this paper, we show that the cycle prefix digraphs, like the Kautz digraphs, contain cycles of all lengths \(l\), with \(l\) between two and \(N\), the order of the digraph, except for \(N-1\).

Let \(G\) be a cubic bipartite plane graph that has a perfect matching. If \(M\) is any perfect matching of \(G\), then \(G\) has a face that is \(M\)-alternating.If \(f\) is any face of \(G\), then there is a perfect matching \(M\) such that \(f\) is \(M\)-alternating.There is a simple algorithm for visiting all perfect matchings of \(G\) beginning at one.
There are infinitely many cubic plane graphs that have perfect matchings but whose matching transformation graphs are completely disconnected.
Several problems are proposed.