We discuss a branch of Ramsey theory concerning vertex Folkman numbers and how computer algorithms have been used to compute a new Folkman number. We write \( G \rightarrow (a_1, \ldots, a_k)^v \) if for every vertex \( k \)-coloring of an undirected simple graph \( G \), a monochromatic \( K_{a_i} \) is forced in color \( i \in \{1, \ldots, k\} \). The vertex Folkman number is defined as\(F_v(a_1, \ldots, a_k; p) = \text{min}\{|V(G)| : G \rightarrow (a_1, \ldots, a_k)^v \wedge K_p \nsubseteq G\}.\) Folkman showed in 1970 that this number exists for \( p > \text{max}\{a_1, \ldots, a_k\} \). Let \( m = 1 + \sum_{i=1}^k (a_i – 1) \) and \( a = \text{max}\{a_1, \ldots, a_k\} \), then \(F_v(a_1, \ldots, a_k; p) = m \text{ for } p > m,\) and \(F_v(a_1, \ldots, a_k; p) = a + m \text{ for } p = m.\)For \( p < m \) the situation is more difficult and much less is known. We show here that, for a case of \( p = m – 1 \), \( F_v(2, 2, 3; 4) = 14 \).

By analogy with Stirling numbers, tri-restricted numbers of the second kind count the number of partitions of a given set into a given number of parts, each part being restricted to at most three elements. Tri-restricted numbers of the first kind are then defined as elements of the matrix inverse to the matrix of tri-restricted numbers of the second kind. A new recurrence relation for the tri-restricted numbers of the second kind is presented, with a combinatorial proof. In answer to a problem that has remained open for several years, it is then shown by determinantal techniques that the tri-restricted numbers of the first kind also satisfy a recurrence relation. This relation is used to obtain a reciprocity theorem connecting the two kinds of tri-restricted number.

A strong \( k \)-edge-coloring of a graph \( G \) is an assignment of \( k \) colors to the edges of \( G \) in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of \( G \), are assigned different colors. The strong chromatic index of \( G \) is the smallest number \( k \) for which \( G \) has a strong \( k \)-edge-coloring. A Halin graph is a planar graph consisting of a tree with no vertex of degree two and a cycle connecting the leaves of the tree. A caterpillar is a tree such that the removal of the leaves becomes a path. In this paper, we show that the strong chromatic index of cubic Halin graph is at most 9. That is, every cubic Halin graph is edge-decomposable into at most 9 induced matchings. Also, we study the strong chromatic index of a cubic Halin graph whose characteristic tree is a caterpillar.

Let \( G \) be a graph of order \( n(G) \), minimum degree \( \delta(G) \), diameter \( d_m(G) \), and let \( \bar{G} \) be the complement of the graph \( G \). A vertex set \( D \) is called a dominating set of \( G \), if each vertex not in \( D \) has at least one neighbor in \( D \). The domination number \( \gamma(G) \) equals the minimum cardinality of a dominating set of \( G \).
In this article we show the inequalities

1. \( \gamma(G) \leq \left\lfloor \frac{n(G)}{3} \right\rfloor, \text{ if } \delta(G) \geq 7, \)
2. \( \gamma(G) + \gamma(\bar{G}) \leq \left\lfloor \frac{n(G)}{3} \right\rfloor + 2, \text{ if } \delta(G), \delta(\bar{G}) \geq 7, \text{ and} \)
3. \( \gamma(G) \leq \left\lceil \frac{n(G)}{4} \right\rceil + 1, \text{ if } \text{dm}(G) = 2. \)

Using the concept of connectivity, we present some related upper bounds for the domination number of graphs with \( \text{dm}(G) = 2 \) and \( \text{dm}(G) = 3 \).

We prove in this note that certain caterpillars with diameter 4 or 5 do not factorize complete graphs. This together with results by Kovarova [2,3] and Kubesa [5] gives the complete characterization of the caterpillars with diameter 4 that factorize the complete graph \( K_{2n} \). For diameter 5, we again complement results by Kovarova [4] and Kubesa [6-9] to give the complete characterization for certain class of caterpillars.

High-performance computers have been in great demand for applications in different areas. The increase in the processing power of processors cannot solely satisfy our demand. Parallel computers are made to overcome this technology limitation. In the last decade, research topics on parallel computer using network-connected multicomputer have been studied extensively. A cost-efficient high-speed multicomputer system was built using the SCSI bus for the network connection, and it has been shown that it can reduce the communication overheads and hence increase the overall performance [5]. In order to build highly scalable multiple computers based on this design, we have to take into consideration of different network topologies. Since SCSI bus [2,3] possesses some unique properties, it induces some interesting properties on the design of the network topology. In this paper, we evaluate the performance of the large scale SCSI networks with linear and mesh structures.

The degree set of a finite simple graph \( G \) is the set of distinct degrees of vertices of \( G \). For any given finite set \( \mathcal{D} \) of positive integers, we determine all positive integers \( n \) such that \( \mathcal{D} \) is the degree set of some simple graph with \( n \) vertices. This extends a theorem of Kapoor, Polimeni \(\& Wall (1977)\) which shows that the least such \( n \) is \( 1 + \max(\mathcal{D}) \).

Every labeling of the vertices of a graph with distinct natural numbers induces a natural labeling of its edges: the label of an edge \( (x,y) \) is the absolute value of the difference of the labels of \( x \) and \( y \). By analogy with graceful labelings, we say that a labeling of the vertices of a graph of order \( n \) is minimally \( k \)-equitable if the vertices are labelled with \( 1, 2, \ldots, n \) and in the induced labeling of its edges every label either occurs exactly \( k \) times or does not occur at all. For \( m \geq 3 \), let \( C_m’ \) (denoted also in the literature by \( C_m \circ K_1 \) and called a corona graph) be a graph with \( 2m \) vertices such that there is a partition of them into sets \( U \) and \( V \) of cardinality \( m \), with the property that \( U \) spans a cycle, \( V \) is independent and the edges joining \( U \) to \( V \) form a matching. Let \( \mathcal{P} \) be the set of all pairs \( (m, k) \) of positive integers such that \( k \) is a proper divisor of \( 2m \) (i.e., a divisor different from \( 2m \) and \( 1 \)) and \( k \) is odd if \( m \) is odd. We show that \( C_m’ \) is minimally \( k \)-equitable if and only if \( (m,k) \in \mathcal{P} \).

We show that the number of points at distance \( i \) from a given point \( x \) in a dense near polygon only depends on \( i \) and not on the point \( x \). We give a number of easy corollaries of this result. Subsequently, we look to the case of dense near polygons \( S \) with an order in which there are two possibilities for \( t_Q \), where \( Q \) is a quad of \( S \), and three possibilities for \( (t_H, v_H) \), where \( H \) is a hex of \( S \). Using the above-mentioned results, we will show that the number of quads of each type through a point is constant. We will also show that the number of hexes of each type through a point is constant if a certain matrix is nonsingular. If each hex is a regular near hexagon, a glued near hexagon or a product near hexagon, then that matrix turns out to be nonsingular in all but one of the eight possible cases. For the exceptional case, however, we provide an example of a near polygon that does not have a constant number of hexes of each type through each point.

In the Euclidean plane, let \( A \), \( B \), \( C \) be noncollinear points and \( T \) be the union of the lines \( AB \), \( BC \), \( CA \). It is shown that there is a point \( P \) such that if \( \tilde{T} \) is the image of \( T \) by any nonrotating uniform expansion about \( P \), then \( T \cap \tilde{T} \) is generally a six-point set that lies on a circle.