Whitney’s Broken-cycle Theorem states the chromatic polynomial of a graph as a sum over special edge subsets. We give a definition of cycles in hypergraphs that preserves the statement of the theorem there

For a digraph $D$, the niche hypergraph $N\mathscr{H}\left(D\right)$ of $D$ is the hypergraph having the same set of vertices as $D$ and the set of hyperedges $E\left(N\mathscr{H}\right(D\left)\right)=\{e\subseteq V(D):|e|\ge 2$ and there exists a vertex $v$ such that $e=N_D^{-}\left(v\right)$ or $e=N_D^{+}\left(v\right)\}$. A digraph is said to be acyclic if it has no directed cycle as a subdigraph. For a given hypergraph $\mathscr{H}$, the niche number $\widehat{n}\left(\mathscr{H}\right)$ is the smallest integer such that $\mathscr{H}$ together with $\widehat{n}\left(\mathscr{H}\right)$ isolated vertices is the niche hypergraph of an acyclic digraph. C. Garske, M. Sonntag and H. M. Teichert (2016) conjectured that for a linear hypercycle...

We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to $K_{n/2,n/2}$.

In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin B, and a list L of n rectangular items, each item with a class value in {1,...,C}. The problem is to pack a subset of L into B, maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item a, items with higher class values can not block a. We present a (4 + ϵ)-approximation algorithm when the bin is a square. We also present (3 + ϵ)-approximation...

The problem of finding minimal vertex number of graphs with a given automorphism group is addressed in this article for the case of cyclic groups. This problem was considered earlier by other authors. We give a construction of an undirected graph having $4n+6$ vertices and automorphism group cyclic of order $4n$, $n\ge 1$. As a special case we get graphs with $2^k+6$ vertices and cyclic automorphism groups of order $2^k$. It can revive interest in related problems.

We prove that every vertex v of a tournament T belongs to at least $maxmin\delta ⁺\left(T\right),2\delta ⁺\left(T\right)-d{⁺}_T\left(v\right)+1,min\delta ¯\left(T\right),2\delta ¯\left(T\right)-d{¯}_T\left(v\right)+1$ arc-disjoint cycles, where δ⁺(T) (or δ¯(T)) is the minimum out-degree (resp. minimum in-degree) of T, and $d{⁺}_T\left(v\right)$ (or $d{¯}_T\left(v\right)$) is the out-degree (resp. in-degree) of v.

Si precisano alcuni risultati del lavoro accennato nel titolo.

Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.

Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an edge-disjoint placement of two copies of G into Kₙ. We prove that with the same condition on size of G we have actually (with few exceptions) a careful packing of G, that is an edge-disjoint placement of two copies of G into Kₙ∖Cₙ.