The achromatic number for a graph $G=(V,E)$ is the largest integer $m$ such that there is a partition of $V$ into disjoint independent sets $(V_1,\dots ,V_m)$ such that for each pair of distinct sets $V_i,V_j$, $V_i\cup V_j$ is not an independent set in $G$. In this paper, we present an $O(1)$-approximation algorithm to determine the achromatic number of circulant graphs $G(n;\pm \{1,2\})$ and $G(n;\pm \{1,2,3\})$.

Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. Let $diam(G)$ denote the diameter of $G$ and $d(u,v)$ denote the distance between the vertices $u$ and $v$ in $G$. An antipodal labeling of $G$ with diameter $d$ is a function $f$ that assigns to each vertex $u$ a positive integer $f(u)$, such that $d(u,v)+|f(u)–f(v)|\ge d$, for all $u,v\in V$. The span of an antipodal labeling $f$ is $max\{|f(u)–f(v)|:u,v\in V(G)\}$. The antipodal number for $G$, denoted by $an(G)$, is the minimum span of all antipodal labelings of $G$. Determining the antipodal number of a graph $G$ is an NP-complete problem. In this paper, we determine the antipodal number of certain graphs with diameter equal to $3$ and $4$.

A radio labeling of a connected graph $G$ is an injection $f$ from the vertices of $G$ to the natural numbers such that $d(u,v)+|f(u)–f(v)|\ge 1+\mathrm{diam}(G)$ for every pair of distinct vertices $u$ and $v$ of $G$. The radio number of $f$, denoted $rn(f)$, is the maximum number assigned to any vertex of $G$. The radio number of $G$, denoted $rn(G)$, is the minimum value of $rn(f)$ taken over all labelings $f$ of $G$. In this paper, we determine bounds for the radio number of the hexagonal mesh.

In this paper, we introduce a finite graph using group characters and discuss the basic properties of the graph.

In this paper, a fuzzy inner product on a real vector space is introduced. The notion of fuzzy inner product is defined. Some of its properties are studied.

Let $G=(V,E)$ be a simple graph. Let $S$ be a subset of $V(G)$. The toughness value of $S$, denoted by $T_S$, is defined as $\frac{|S|}{\omega (G–S)}$, where $\omega (G–S)$ denotes the number of components in $G–S$. If $S=V$, then $\omega (G–S)$ is taken to be $1$ and hence $T_{V(G)}=|V(G)|$. A partition of $V(G)$ into subsets $V_1,V_2,\dots ,V_t$ such that $T_{V_i}$, $1\le i\le t$, is a constant is called an equi-toughness partitio of $G$. The maximum cardinality of such a partition is called the equi-toughness partition number of $G$ and is denoted by $ET(G)$. The existence of $ET$-partition is guaranteed. In this paper, a study of this new parameter is initiated.

The parameter $t$ of a tree $t$-spanner of a graph is always bounded by $2\lambda$ where $\lambda$ is the diameter of the graph. In this paper, we establish a sufficient condition for graphs to have the minimum spanner at least $2\rho –1$ where $\rho$ is the radius. We also obtain a characterization for tree $3$-spanner admissible chordal graphs in terms of tree $3$-spanner admissibility of certain subgraphs.

A connected graph $G(V,E)$ is said to be $(a,d)$-antimagic if there exist positive integers $a$ and $d$ and a bijection $f:E\to \{1,2,\dots ,|E|\}$ such that the induced mapping ${\text{g}}_{\text{f}}:V\to \mathbb{N}$ defined by ${\text{g}}_{\text{f}}(v)=\sum _{\text{e}\in \text{I}(v)}\text{f(e)}$, where $\text{I}(v)=\{\text{e}\in E\mid \text{e}\text{ is incident to }v\}$, $v\in V$ is injective and ${\text{g}}_{\text{f}}(V)=\{a,a+d,a+2d,\dots ,a+(|V|-1)d\}$. In this paper, using partition, we prove that (i) the 1-sided infinite path $P_1$ is $(1,2)$-antimagic, (ii) the path $P_{2n+1}$ is $(n,1)$-antimagic, and (iii) the $(n+2,1)$-antimagic labeling is the unique $(a,d)$-antimagic labeling of $C_{2n+1}$; and the graphs $K_1+(K_1\cup K_2)$, $P_{2n}$, and $C_{2n}$ are not $(a,d)$-antimagic. For $a,d\in \mathbb{N}$, on an $(a,d)$-antimagic graph $G$, we obtain a new relation, $a+(p-1)d\le \frac{\mathrm{\Delta }(2q–\mathrm{\Delta }+1)}{2}$. Using the results on $(a,d)$-antimagic labeling of $C_{2n}$ and $C_{2n+1}$, we obtain results on the existence of $(a,d)$-arithmetic sequences of length $2n$ and $2n+1$, respectively.

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 $\mathrm{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)\ne 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^{\ast }:E\to {\mathbb{Z}}_2$ defined by $f^{\ast }(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^{\ast }}^{-1}(i)|$. We call $f$ friendly if $|v_f(1)–v_f(0)|\le 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)$.

The detour order of a graph $G$, denoted $\tau (G)$, is the order of a longest path in $G$. A partition $(A,B)$ of $V(G)$ such that $\tau (⟨A⟩)\le a$ and $\tau (⟨B⟩)\le b$ is called an $(a,b)$-partition of $G$. A graph $G$ is called $\tau$-\textit{partitionable} if $G$ has an $(a,b)$-partition for every pair $(a,b)$ of positive integers such that $a+b=\tau (G)$.

The well-known Path Partition Conjecture states that every graph is $\tau$-partitionable. Motivated by the recent result of Dunbar and Frick [6] that if every $2$-connected graph is $\tau$-partitionable, then every graph is $\tau$-partitionable, we show that the Path Partition Conjecture is true for a large family of $2$-connected graphs with certain ear-decompositions. Also, we show that a family of $2$-edge-connected graphs with certain ear-decompositions is $\tau$-partitionable.

he problem of determining the collaboration graph of co-authors of Paul Erdos is a challenging task. Here we take up this problem for the case of Rolf Nevanlinna Prize Winners. Even though the number of prize winners as of date is 7, the collaboration graph has 20 vertices and 41 edges and possesses several interesting properties. In this paper, we have obtained this graph and determined standard graph parameters for the graph as well as its complement besides probing its structural properties. Several new results were obtained.

The topological descriptor Wiener index, named after the chemist Harold Wiener, is defined as half the sum of the distances between every pair of vertices of a graph. A lot of research has been devoted to finding the Wiener index by brute force method. In this paper, we compute the Wiener index of chemical structures such as sodium chloride and benzenoid without using a distance matrix.

A graph $G(p,q)$ is said to be total edge bimagic with two common edge counts $k_1$ and $k_2$ if there exists a bijection $f:V(G)\cup E(G)\to \{1,2,\dots ,p+q\}$ such that for each edge $uv\in E(G)$, $f(u)+f(v)+f(uv)=k_1$ or $k_2$.
A total edge-bimagic graph is called super edge-bimagic if $f(V(G))=\{1,2,\dots ,p\}$. In this paper, we define new types of super edge-bimagic labeling and prove some interesting results related to super edge-bimagic labeling. Also, its relationship with cordial labeling is studied.

Trust is one of the most important means to improve the reliability of computing resources provided in a cloud environment and it plays an important role in commercial cloud environments. Trust is the estimation of the capability of a cloud resource in completing a task based on reputation, identity, behavior, and availability in the context of a distributed environment. It helps customers in the selection of appropriate resources in heterogeneous cloud infrastructure. The cloud computing depends on the following QoS parameters such as reliability, availability, scalability, security, and past behavior of the cloud resources.
This paper introduces a novel trust model to evaluate cloud resources of IaaS (Infrastructure as a Service) providers by means of Trust Resource Broker. The Trust Resource Broker selects trustworthy cloud resources based on the requirements of customers. The proposed trust model evaluates the trust value of the resources based on the identity as well as behavioral trust. The proposed model applies the QoS metrics suitable for cloud resources. The results of the experiments show that the proposed trust model selects the most reliable resources in a cloud environment.