A graph has the neighbour-closed-co-neighbour, or ncc property, if for each of its vertices \(x\), the subgraph induced by the neighbour set of \(x\) is isomorphic to the subgraph induced by the closed non-neighbour set of \(x\). Graphs with the ncc property were characterized in [1] by the existence of a locally \(C_4\) perfect matching \(M\): every two edges of \(M\) induce a subgraph isomorphic to \(C_4\). In the present article, we investigate variants of locally \(C_4\) perfect matchings. We consider the cases where pairs of distinct edges of the matching induce isomorphism types including \(P_4\), the paw, or the diamond. We give several characterizations of graphs with such matchings. In addition, we supply characterizations of graphs with matchings whose edges satisfy a prescribed parity condition.

In this paper we obtain some necessary conditions for the existence of balanced arrays (B-arrays) with two symbols and having strength seven. We then describe how these conditions involving the parameters of the array can be used to obtain an upper bound on the constraints of such arrays, and give some illustrative examples to this effect.

A defensive alliance in a graph \( G(V,E) \) is a set of vertices \( S \subseteq V \) such that for every vertex \( v \in S \), the closed neighborhood \( N_G[v] \) of \( v \) has at least as many vertices in \( S \) as it has in \( V – S \). An offensive alliance is a set of vertices \( S \subseteq V \), such that for every vertex \( v \) in the boundary \( \partial(S) \) of \( S \) the number of neighbors that \( v \) has in \( S \) is greater than or equal to the number of neighbors it has in \( V – S \). A subset of vertices which is both an offensive and a defensive alliance is called a powerful alliance. An alliance which is also a dominating set is called a global alliance. In this paper, we show that finding an optimal defensive (offensive, powerful) global alliance is an NP-hard problem.

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}) \).