Betweenness is a centrality measure based on shortest paths, widely used in complex network analysis. The betweenness centrality of a vertex is defined as the fraction of shortest paths that pass through that vertex over all pairs of vertices. It measures the control a vertex has over communication in the network, and can be used to identify key vertices in the network. High centrality indices indicate that a vertex can reach other vertices on relatively short paths, or that a vertex lies on a considerable fraction of shortest paths connecting pairs of other vertices. In this paper, we find the betweenness centrality of the honeycomb mesh, which has important applications in mobile networks.

Tree replacement / rewriting systems are an interesting model of computation. They are used in theorem proving, algebraic simplification, and language theory. A fundamental property of tree replacement systems is the Church-Rosser property, which expresses the fact that interconvertability of two trees can be checked by mere simplification to a common tree. In this paper, we give a learning algorithm for a subclass of the class of Church-Rosser tree replacement systems.

We show that the butterfly network and Benes network can be embedded into generalized fat trees with minimum dilation.

The crossing number of a graph \( G \) is the minimum number of crossings of its edges among the drawings of \( G \) in the plane and is denoted by \( \operatorname{cr}(G) \). In this paper, we obtain bounds for the crossing number for two different honeycomb tori, namely, the honeycomb rectangular torus and the honeycomb rhombic torus, which are obtained by adding wraparound edges to honeycomb meshes.

In cellular radio communication systems, the concept of maximum packing is used for dynamic channel assignment. An \( H \)-packing of a graph \( G \) is a set of vertex-disjoint subgraphs of \( G \), each of which is isomorphic to a fixed graph \( H \). The maximum \( H \)-packing problem is to find the maximum number of vertex-disjoint copies of \( H \) in \( G \), called the packing number, denoted by \( \lambda(G, H) \). In this paper, we determine the maximum \( H \)-packing number of hexagonal networks when \( H \) is isomorphic to \( P_6 \) as well as \( K_{1,3} \).

A kernel in a directed graph \( D(V, E) \) is a set \( S \) of vertices of \( D \) such that no two vertices in \( S \) are adjacent and for every vertex \( u \) in \( V \setminus S \), there is a vertex \( v \) in \( S \) such that \( (\overrightarrow{u, v}) \) is an arc of \( D \). The problem of existence of a kernel is NP-complete for a general digraph. In this paper, we introduce the acyclic kernel problem for an undirected graph \( G \) and solve it in polynomial time for certain cycle-related graphs.

A kernel in a directed graph \( D(V, E) \) is a set \( S \) of vertices of \( D \) such that no two vertices in \( S \) are adjacent and for every vertex \( u \) in \( V \setminus S \), there is a vertex \( v \) in \( S \) such that \( (u, v) \) is an arc of \( D \). The problem of existence of a kernel is NP-complete for a general digraph. In this paper, we solve the strong kernel problem of an oriented biregular graph in polynomial time.

String-token Petri net, which is a variation of coloured Petri net, has been introduced in [1] by requiring the tokens to be labeled by strings. Languages in regular and linear families, which are two basic classes in the Chomsky hierarchy, are generated by these Petri nets [2]. An extension called array-token Petri net, introduced in [5] by labeling tokens by arrays, generates picture languages. Properties related to generative power of array-token Petri net are considered in [3]. In this paper, application of array-token Petri net to generate English alphabetic letters treated as rectangular arrays is examined.

Given a graph \( G = (V, E) \), a set \( W \subseteq V \) is said to be a resolving set if for each pair of distinct vertices \( u, v \in V \), there is a vertex \( x \) in \( W \) such that \( d(u, x) \neq d(v, x) \). The resolving number of \( G \) is the minimum cardinality of all resolving sets. In this paper, a condition is imposed on resolving sets and a conditional resolving parameter is studied for grid-based networks.

Let \( G = (V, E) \) be a graph. A vertex labeling \( f: V \to \mathbb{Z}_2 \) induces an edge labeling \( f^*: E \to \mathbb{Z}_2 \) defined by \( f^*(xy) = f(x) + f(y) \) for each \( xy \in E \). For each \( i \in \mathbb{Z}_2 \), define \( v_f(i) = |f^{-1}(i)| \) and \( e_f(i) = |{f^*}^{-1}(i)| \). We call \( f \) friendly if \( |v_f(1) – v_f(0)| \leq 1 \). The full friendly index set of \( G \) is the set of all possible values of \( e_f(1) – e_f(0) \), where \( f \) is a friendly labeling. In this paper, we study the full friendly index set of the wheel \( W_n \), the tensor product of paths \( P_2 \) and \( P_n \), i.e., \( P_2 \otimes P_n \), and the double star \( D(m, n) \).