Let \(T_n\) be the complete binary tree of height \(n\) considered as the Hasse-diagram of a poset with its root \(1_n\) as the maximum element. For a tree or forest \(T\), we count the embeddings of \(T\) into \(T_n\) as posets by the functions \(A(n;T) = |\{S \subseteq T_n : 1_n \in S, S \cong T\}|\), and \(B(n;T) = |\{S \subseteq T_n : 1_n \notin S, S \cong T\}|\). Here we summarize what we know about the ratio \(A(n;T)/B(n;T)\), in case of \(T\) being a chain or an antichain.

In this paper, the concept of clique number of uniform hypergraph is defined and its relationship with circular chromatic number and clique number is studied. For every positive integer \(k, p\) and \(q\), \(2q \leq p\) we construct a \(k\)-uniform hypergraph with small clique number whose circular chromatic number is equal to \(\frac{p}{q}\). We define the concept and study the properties of \(c\)-perfect \(k\)-uniform hypergraphs.

Given a connected graph \(G\) and a subset \(S\) of vertices, the Steiner distance of \(S\) in \(G\) is the minimum number of edges in a tree in \(G\) that contains all of \(S\). Given a positive integer \(m\), let \(\mu_m(G)\) denote the average Steiner distance over all sets \(S\) of \(m\) vertices in \(G\). In particular, \(\mu_2(G)\) is just the average distance of \(G\), often denoted by \(\mu(G)\). Dankelmann, Oellermann, and Swart \([1]\) conjectured that if \(G\) is a connected graph of order \(n\) and \(3 \leq m \leq n\), then \(\frac{\mu_m(G)}{\mu(G)} \geq 3(\frac{m-1}{m+1})\). In this note, we disprove their conjecture by showing that

\[\lim_{m \to \infty} inf \{ \frac{\mu_m(G)}{\mu(G)} :G \text{ is connected and $n(G)\geq m$} \} = 2.\]

Given a simple graph \(G\) on \(n\) vertices, let \(\sigma_2(G)\) be the minimum sum of the degrees of any two non-adjacent vertices. The graph \(G\) is said to be connected if any two distinct vertices may be joined by a path. It is easy to see that if \(\sigma_2(G) \geq n-1\) then \(G\) is not only connected, but we can choose the connecting path to be of size at most two. Ore \([4]\) proved that if \(\sigma_2(G) \geq n+1\) we may always choose this path to cover all the vertices of \(G\). In this paper we extend these results to systems of vertex disjoint paths connecting two vertex \(k\)-sets of \(G\).

A graph with vertex set \(V\) is said to have a prime labeling if its vertices are labelled with distinct integers from \(\{1, 2, \ldots, |V|\}\) such that for each edge \(xy\), the labels assigned to \(x\) and \(y\) are relatively prime. A graph that admits a prime labeling is called a prime graph. It has been conjectured \([1]\) that when \(n\) is a prime integer and \(m < n\), the planar grid \(P_m \times P_n\) is prime. We prove the conjecture and also that \(P_n \times P_n\) is prime when \(n\) is a prime integer.

The exact values of eleven Ramsey numbers \(r(K_{l_1,n_1} , K_{l_2, n_2})\) where \(3 \leq l_1+n_1, l_2+n_2 \leq 7\) are determined, almost completing the table of all \(66\) such numbers.

In \([1]\) and \([4]\), the authors derive Fermat’s (little), Lucas’s and Wilson’s theorems, among other results, all from a single combinatorial lemma. This lemma can be derived by applying Burnside’s theorem to an action by a cyclic group of prime order. In this note, we generalize this lemma by applying Burnside’s theorem to the corresponding action by an arbitrary finite cyclic group. Although this idea is not new, by revisiting the constructions in \([1]\) and \([4]\) we derive three divisibility theorems for which the aforementioned classical theorems are, respectively, the cases of a prime divisor, and two of these generalizations are new. Throughout, \(n\) and \(p\) denote positive integers with \(p\) prime and \(\mathbb{Z}_n\) denotes the cyclic group of integers under addition modulo \(n\).

Working on the problem of finding the numbers of lattice points inside convex lattice polygons, Rabinowitz has made several conjectures dealing with convex lattice nonagons and decagons. An intensive computer search preceded a formulation of the conjectures. The main purpose of this paper is to prove some of Rabinowitz’s conjectures. Moreover, we obtain an improvement of a conjectured result and give short proofs of two known results.

Let \(k \geq 1\) be an integer and let \(G = (V, E)\) be a graph. A set \(S\) of vertices of \(G\) is \(k\)-independent if the distance between any two vertices of \(S\) is at least \(k+1\). We denote by \(\rho_k(G)\) the maximum cardinality among all \(k\)-independent sets of \(G\). Number \(\rho_k(G)\) is called the \(k\)-packing number of \(G\). Furthermore, \(S\) is defined to be \(k\)-dominating set in \(G\) if every vertex in \(V(G) – S\) is at distance at most \(k\) from some vertex in \(S\). A set \(S\) is \(k\)-independent dominating if it is both \(k\)-independent and \(k\)-dominating. The \(k\)-independent dominating number, \(i_k(G)\), is the minimum cardinality among all \(k\)-independent dominating sets of \(G\). We find the values \(i_k(G)\) and \(\rho_k(G)\) for iterated line graphs.

The maximum genus, a topological invariant of graphs, was inaugurated by Nordhaus \(et\; al\). \([16]\). In this paper, the relations between the maximum non-adjacent edge set and the upper embeddability of a graph are discussed, and the lower bounds on maximum genus of a graph in terms of its girth and maximum non-adjacent edge set are given. Furthermore, these bounds are shown to be best possible. Thus, some new results on the upper embeddability and the lower bounds on the maximum genus of graphs are given.