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.

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well known vertex covering and dominating set problems in graphs (see SIAM J. Discrete Math. \(15(4) (2002), 519-529)\). A set \(S\) of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set \(S\) (following a set of rules for power system monitoring). The minimum cardinality of a power dominating set of a graph is its power domination number. We investigate the power domination number of a block graph.

A \((p,q)\)-graph \(G\) in which the edges are labeled \(1,2,3,\ldots,q\) so that the vertex sums are constant, is called supermagic. If the vertex sum mod \(p\) is a constant, then \(G\) is called edge-magic. We investigate the supermagic characteristic of a simple graph \(G\), and its edge-splitting extension \(SPE(G,f)\). The construction provides an abundance of new supermagic multigraphs.

The basis number of a graph \(G\) is defined to be the least integer \(k\) such that \(G\) has a \(k\)-fold basis for its cycle space. We investigate the basis number of the composition of theta graphs, a theta graph and a path, a theta graph and a cycle, a path and a theta graph, and a cycle and a theta graph.

We introduce certain types of surfaces \(M_j^n\), for \(j = 1,2,\ldots,11\) and determine their genus distributions. At the basis of joint trees introduced by Liu, we develop the surface sorting method to calculate the embedding distribution by genus.

Network reliability is an important issue in the area of distributed computing. Most of the early work in this area takes a probabilistic approach to the problem. However, sometimes it is important to incorporate subjective reliability estimates into the measure. To serve this goal, we propose the use of the weighted integrity, a measure of graph vulnerability. The weighted integrity problem is known to be NP-complete for most of the common network topologies including tree, mesh, hypercube, etc. It is known to be NP-complete even for most perfect graphs, including comparability graphs and chordal graphs. However, the computational complexity of the problem is not known for one class of perfect graphs, namely, co-comparability graphs. In this paper, we give a polynomial-time algorithm to compute the weighted integrity of interval graphs, a subclass of co-comparability graphs.