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 introduce the acyclic kernel problem of an undirected graph \(G\) and solve it in polynomial time for uniform theta graphs and even quasi-uniform theta graphs.

Given a graph \( G = (V, E) \), a labeling \( \partial: V \cup E \to \{1, 2, \dots, k\} \) is called an edge irregular total \( k \)-labeling if for every pair of distinct edges \( uv \) and \( xy \), \( \partial(u) + \partial(uv) + \partial(v) \neq \partial(x) + \partial(xy) + \partial(y) \). The minimum \( k \) for which \( G \) has an edge irregular total \( k \)-labeling is called the total edge irregularity strength of \( G \). In this paper, we examine the hexagonal network, which is a well-known interconnection network, and obtain its total edge irregularity strength.

Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. In this paper, we prove that grid and cylinder are the subgraphs of certain circulant networks. Further, we present an algorithm to embed tori into certain circulant networks with dilation\(2\) and vice-versa.

Broadcasting is a fundamental information dissemination problem in a connected graph, in which one vertex called the originator disseminates one or more messages to all other vertices in the graph. \(A\)-broadcasting is a variant of broadcasting in which an informed vertex can disseminate a message to at most \(k\) uninformed vertices in one unit of time. In general, solving the broadcast problem in an arbitrary graph is NP-complete. In this paper, we obtain the \(k\)-broadcast time of the Sierpiński gasket graphs for all \(k \geq 1\).

Let \( G = (V, E) \) be a graph with vertex set \( V \) and edge set \( E \). Let \( \text{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)| \geq 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 \( \text{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.

The concept of fuzzy local \(\omega\)-language and Büchi fuzzy local \(\omega\)-language are defined in \([1,2]\). In this paper, we define Landweber fuzzy local \(\omega\)-language and study their closure properties and also give an automata characterization for it. Finally, we conclude the hierarchy among the subclasses of fuzzy regular \(\omega\)-languages.

In this paper, we have calculated the combinatorial counting relations varying over the \(3\)-vertex paths of a simple graph \(G\), by restricting our attention to \(C_3\), \(C_4\)-free 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 itself is NP-complete for a general digraph. But in this paper, we solve the strong kernel problem of certain oriented networks in polynomial time.

A double shell is defined to be two edge-disjoint shells with a common apex. In this paper, we prove that double shells (where the shell orders are \(m\) and \(2m+1\)) with exactly two pendant edges at the apex are \(k\)-graceful when \(k=2\). We extend this result to double shells of any order \(m\) and \(\ell\) (where \(m \geq 3\) and \(\ell \geq 3\)) with exactly two pendant edges at the apex.

A book consists of a line in the 3-dimensional space, called the spine, and a number of pages, each a half-plane with the spine as boundary. A book embedding \((\pi, p)\) of a graph consists of a linear ordering \(\pi\) of vertices, called the spine ordering, along the spine of a book and an assignment \(p\) of edges to pages so that edges assigned to the same page can be drawn on that page without crossing. That is, we cannot find vertices \(u, v, x, y\) with \(\pi(u) < \pi(x) < \pi(v) 2\) and \(C_n\) are given. If \(G\) is any graph, an upper bound for the page number of the Mycielski of \(G\) is given. When \(G\) and \(H\) are any two graphs with page number \(k\) and \(l\), it is proved that the amalgamation of \(G\) and \(H\) can be embedded in a \max(k, l)\) pages. Further, we remark that the amalgamation of \(G\) with itself requires the same number of pages as \(G\), irrespective of the vertices identified in the two copies of \(G\), to form an amalgamation.