Public Key Cryptosystems (PKC) based on formal language theory and semi groups have been of interest and study. A PKC based on free group has been presented in [7]. Subsequently, another PKC using free partially commutative monoids and groups is studied in [1]. In this paper, we propose a PKC for chain cade pictures that uses a finitely presented group for encryption and free group for decryption. Also, we present another PKC for line pictures in the hexagonal grid, which uses a finitely presented group for encryption and finitely presented free partially commutative group for decryption.

Let \( G = (V, E) \) be a connected graph. A subset \( A \) of \( V \) is called an asteroidal set if for any three vertices \( u,v,w \) in \( A \), there exists a \( u \)-\( v \) path in \( G \) that avoids the neighbourhood of \( w \). The asteroidal chromatic number \( \chi_a \) of \( G \) is the minimum order of a partition of \( V \) into asteroidal sets. In this paper we initiate a study of this parameter. We determine the value of \( \chi_a \) for several classes of graphs, obtain sharp bounds, and Nordhaus-Gaddum type results.

Many approaches to drawing graphs in the plane can be formulated and solved as mathematical programming problems. Here, we consider only drawings of a graph where each edge is drawn as a straight-line segment, and we wish to minimize the number of edge crossings over all such drawings. Some formulations of this problem are presented that lead very naturally to other unsolved problems, some solutions, and some new open problems associated with drawing nonplanar graphs in the plane.

In this paper we introduce right angle path and layer of an array. We construct Kolakoski array and study some combinatorial proper-ties of Kolakoski array. Also we obtain recurrence relation for layers and special elements.

An \({eternal \;1-secure}\) set of a graph \(G = (V, E)\) is defined as a set \(S_0 \subseteq V\) that can defend against any sequence of single-vertex attacks by means of single guard shifts along edges of \(G\). That is, for any \(k\) and any sequence \(v_1, v_2, \ldots, v_k\) of vertices, there exists a sequence of guards \(u_1, u_2, \ldots, u_k\) with \(u_i \in S_{i-1}\) and either \(u_i = v_i\) or \(u_iv_i \in E\), such that each set \(S_i = (S_{i-1} -\{u_i\}) \cup \{v_i\}\) is dominating. It follows that each \(S_i\) can be chosen to be an eternal 1-secure set. The \({eternal \;1-security\; number}\), denoted by \(\sigma_1(G)\), is defined as the minimum cardinality of an eternal 1-secure set. This parameter was introduced by Burger et al. [3] using the notation \(\gamma_\infty\). The \({eternal \;m-security}\) number \(\sigma_m(G)\) is defined as the minimum number of guards to handle an arbitrary sequence of single attacks using multiple-guard shifts. A suitable placement of the guards is called an \({eternal\; m-secure}\) set. It was observed that \(\gamma(G) \leq \sigma_m(G) \leq \beta(G)\). In this paper, we obtain specific values of \(\sigma_m(G)\) for certain classes of graphs, namely circulant graphs, generalized Petersen graphs, binary trees, and caterpillars.

Let \( G \) be a simple graph, and let \( p \) be a positive integer. A subset \( D \subseteq V(G) \) is a \( p \)-\({dominating \;set}\) of the graph \( G \) if every vertex \( v \in V(G) – D \) is adjacent to at least \( p \) vertices of \( D \). The \( p \)-\({domination\; number}\) \( \gamma_p(G) \) is the minimum cardinality among the \( p \)-dominating sets of \( G \). Note that the \( 1 \)-domination number \( \gamma_1(G) \) is the usual \({domination\; number}\) \( \gamma(G) \).
In \(1985\), Fink and Jacobson showed that for every graph \(G\) with \(n\) vertices and \(m\) edges the inequality \(y\),\(\gamma_p(G) \geq n — m/p\) holds. In this paper we present a generalization of this theorem and analyze the \(2\)-domination number \(\gamma_2\) in cactus graphs \(G\) with respect on its relation to the matching number \(\alpha_0\) and the number of odd or rather even cycles in \(G\). Further we show that \(\gamma_2(G) \geq \alpha(G)\) for the cactus graphs \(G\) with at most one even cycle and characterize those which
fulfill \(\gamma_2(G) = \alpha(G)\) or rather \(\gamma_2(G) = \alpha(G) +1\).

We introduce a \( k \)-response set as a set of vertices where responders can be placed so that given any set of \( k \) emergencies, these responders can respond, one per emergency, where each responder covers its own vertex and its neighbors. A weak \( k \)-response set does not have to worry about emergencies at the vertices of the set. We define \( R_k \) and \( r_k \) as the minimum cardinality of such sets. We provide bounds on these parameters and discuss connections with domination invariants. For example, for a graph \( G \) of order \( n \) and minimum degree at least \( 2 \), \( R_2(G) \leq \frac{2n}{3} \), while \( r_2(G) \leq \frac{n}{2} \) provided \( G \) is also connected and not \( K_3 \). We also provide bounds for trees \( T \) of order \( n \). We observe that there are, for each \( k \), trees for which \( r_k(T) \leq \frac{n}{2} \), but that the minimum \( R_k(T) \) appears to grow with \( k \); a novel computer algorithm is used to show that \( R_3(T) > \frac{n}{2} \). As expected, these parameters are NP-hard to compute, and we provide a linear-time algorithm for trees for fixed \( k \).

Suppose \( 2n \) voters vote sequentially for one of two candidates. For how many such sequences does one candidate have strictly more votes than the other at each stage of the voting? The answer is \( \binom{2n}{n} \) and, while easy enough to prove using generating functions, for example, only three combinatorial proofs exist, due to Kleitman, Gessel, and Callan. In this paper, we present two new bijective proofs.

In [10], Fink and Jacobson gave a generalization of the concepts of domination and independence in graphs which extends only partially the well-known inequality chain \( \gamma(G) \leq i(G) \leq \beta(G) \leq \Gamma(G) \) between the usual parameters of domination and independence. If a \( k \)-independent set is defined as a subset of vertices inducing in \( G \) a subgraph of maximum degree less than \( k \), we introduce the property which makes a \( k \)-independent set maximal. This leads us to the notion of a \( k \)-star-forming set. The corresponding parameters \( sf_k(G) \) and \( \text{SF}_k(G) \) satisfy \( sf_k(G) \leq i_k(G) \leq \beta_k(G) \leq \text{SF}_k(G) \) where \( i_k(G) \) and \( \beta_k(G) \) are respectively the minimum and the maximum cardinality of a maximal \( k \)-independent set. We initiate the study of \( sf_k(G) \) and \( \text{SF}_k(G) \) and give some results in particular classes of graphs such as trees, chordal graphs, and \( K_{1,r} \)-free graphs.

If \( D \) is a digraph, \( \delta \) its minimum degree, and \( \lambda \) its edge-connectivity, then \( \lambda \leq \delta \). A digraph \( D \) is called super-edge-connected or super-\( \lambda \) if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree. Clearly, if \( D \) is super-\( \lambda \), then \( \lambda = \delta \). A digraph without any directed cycle of length \( 2 \) is called an oriented graph. Sufficient conditions for digraphs to be super-edge-connected were given by several authors. However, closely related results for oriented graphs have received little attention until recently. In this paper, we will present some degree sequence conditions for oriented graphs as well as for oriented bipartite graphs to be super-edge-connected.