The distance \( d(u, v) \) between a pair of vertices \( u \) and \( v \) in a connected graph \( G \) is the length of a shortest path joining them. A vertex \( v \) of a connected graph \( G \) is an eccentric vertex of a vertex \( u \) if \( v \) is a vertex at greatest distance from \( u \); while \( v \) is an eccentric vertex of \( G \) if \( v \) is an eccentric vertex of some vertex of \( G \). A vertex \( v \) of \( G \) is a boundary vertex of a vertex \( u \) if \( d(u,w) \leq d(u,v) \) for each neighbour \( w \) of \( v \). A vertex \( v \) is a boundary vertex of \( G \) if \( v \) is a boundary vertex of some vertex of \( G \). It is easy to see that for a vertex \( u \), its eccentric vertices are boundary vertices for \( u \); but not conversely. In this paper, we introduce a new type of eccentricity called b-eccentricity and we study its properties.
The main result: If the vertices of a connected graph are labelled by positive real numbers such that the number assigned to any vertex is half of the sum of the numbers assigned to the vertices of its neighbourhood, then each label is an integral multiple of the minimum of all labels. Using this, a result proved earlier in [7] is derived: If \(V\) is a linearly dependent subset of a root system in which all roots have the same norm, then one of the roots in \(V\) is an integral combination of the other roots in \(V\).
A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is said to be a dominating set of \(G\) if each \(v \in V – D\) is adjacent to at least one vertex of \(D\). The minimum cardinality of a dominating set of \(G\) is called the domination number of \(G\) and is denoted by \(\gamma(G)\). A dominating set \(D\) with cardinality \(\gamma(G)\) is called a \(\gamma\)-set of \(G\). Given a graph \(G\), a new graph, denoted by \(\gamma.G\) and called the \(\gamma\)-graph of \(G\), is defined as follows: \(V(\gamma.G)\) is the set of all \(\gamma\)-sets of \(G\) and two sets \(D\) and \(S\) of \(V(\gamma.G)\) are adjacent in \(\gamma.G\) if and only if \(|D \cap S| = \gamma(G) – 1\). A graph \(G\) is said to be \(\gamma\)-connected if \(\gamma.G\) is connected. A graph \(G\) is said to be a \(\gamma\)-graph if there exists a graph \(H\) such that \(\gamma-H\) is isomorphic to \(G\). In this paper, we show that trees and unicyclic graphs are \(\gamma\)-graphs. Also, we obtain a family of graphs which are not \(\gamma\)-graphs.
A Cayley graph is a graph constructed out of a group \(\Gamma\) and its generating set \(A\). In this paper, we determine the independent domination number, perfect domination number, and independent dominating sets of \(Cay(\mathbb{Z}_n, A)\), for a specified generating set \(A\) of \(\mathbb{Z}_n\).
In this paper, we introduce an online tessellation partial automaton to recognize partial array languages. We also introduce two classes of partial array languages. We also introduce two classes of partial array languages viz, Local Partial Array Languages (PAL-LOC) Recognizable Partial Array Languages (PAL-REC) and prove PAL-REC is exactly the family of partial array languages recognizable by online tessellation partial automaton.
For a connected graph \(G\) of order \(p \geq 2\), a set \(S \subseteq V(G)\) is a geodetic set of \(G\) if each vertex \(v \in V(G)\) lies on an \(x\)-\(y\) geodesic for some elements \(x\) and \(y\) in \(S\). The minimum cardinality of a geodetic set of \(G\) is defined as the geodetic number of \(G\), denoted by \(g(G)\). A geodetic set of cardinality \(g(G)\) is called a \(g\)-set of \(G\). A connected geodetic set of \(G\) is a geodetic set \(S\) such that the subgraph \(G[S]\) induced by \(S\) is connected. The minimum cardinality of a connected geodetic set of \(G\) is the connected geodetic number of \(G\) and is denoted by \(g_c(G)\). A connected geodetic set of cardinality \(g_c(G)\) is called a \(g_c\)-set of \(G\). Connected graphs of order \(p\) with connected geodetic number \(2\) or \(p\) are characterized. It is shown that for positive integers \(r,d\) and \(n \geq d+1\) with \(r \leq d \leq 2r\), there exists a connected graph \(G\) of radius \(r\), diameter \(d\) and \(g_c(G) = n\). Also, for integers \(p,d\) and \(n\) with \(2 \leq d \leq p-1\), \(d+1 \leq n \leq p\), there exists a connected graph \(G\) of order \(p\), diameter \(d\) and \(g_c(G) = n\).
For two vertices \(u\) and \(v\) in a graph \(G = (V, E)\), the \emph{detour distance} \(D(u, v)\) is the length of a longest \(u\)-\(v\) path in \(G\). A \(u\)-\(v\) path of length \(D(u,v)\) is called a \(u\)-\(v\) detour. A set \(S \subseteq V\) is called a \emph{detour set} of \(G\) if every vertex in \(G\) lies on a detour joining a pair of vertices of \(S\). The \emph{detour number} \(dn(G)\) of \(G\) is the minimum order of its detour sets, and any detour set of order \(dn(G)\) is a detour basis of \(G\). A set \(S \subseteq V\) is called a \emph{connected detour set} of \(G\) if \(S\) is a detour set of \(G\) and the subgraph \(G[S]\) induced by \(S\) is connected. The \emph{connected detour number} \(cdn(G)\) of \(G\) is the minimum order of its connected detour sets, and any connected detour set of order \(cdn(G)\) is called a \emph{connected detour basis} of \(G\). Certain general properties of these concepts are studied. The connected detour numbers of certain classes of graphs are determined. The relationship of the connected detour number with the detour diameter is discussed, and it is proved that for each triple \(D, k, p\) of integers with \(3 \leq k \leq p-D-1\) and \(D \geq 4\), there is a connected graph \(G\) of order \(p\) with detour diameter \(D\) and \(cdn(G) = k\). A connected detour set \(S\), no proper subset of which is a connected detour set, is a \emph{minimal connected detour set}. The \emph{upper connected detour number} \(cdn^+(G)\) of a graph \(G\) is the maximum cardinality of a minimal connected detour set of \(G\). It is shown that for every pair \(a, b\) of integers with \(5 \leq a \leq b\), there is a connected graph \(G\) with \(cdn(G) = a\) and \(cdn^+(G) = b\).
For two vertices \(u\) and \(v\) in a graph \(G = (V, E)\), the \emph{detour distance} \(D(u,v)\) is the length of a longest \(u\)-\(v\) path in \(G\). A \(u\)-\(v\) path of length \(D(u, v)\) is called a \(u\)-\(v\) \emph{detour}. A set \(S \subseteq V\) is called an \emph{edge detour set} if every edge in \(G\) lies on a detour joining a pair of vertices of \(S\). The \emph{edge detour number} \(dn_1(G)\) of \(G\) is the minimum order of its edge detour sets, and any edge detour set of order \(dn_1(G)\) is an \emph{edge detour basis} of \(G\). A connected graph \(G\) is called an \emph{edge detour graph} if it has an edge detour set. Certain general properties of these concepts are studied. The edge detour numbers of certain classes of graphs are determined. We show that for each pair of integers \(k\) and \(p\) with \(2 \leq k < p\), there is an edge detour graph \(G\) of order \(p\) with \(dn_1(G) = k\). An edge detour set \(S\), no proper subset of which is an edge detour set, is a \emph{minimal edge detour set}. The \emph{upper edge detour number} \(dn_1^+(G)\) of a graph \(G\) is the maximum cardinality of a minimal edge detour set of \(G\). We determine the upper edge detour numbers of certain classes of graphs. We also show that for every pair \(a, b\) of integers with \(2 \leq a \leq 6\), there is an edge detour graph \(G\) with \(dn_1(G) = a\) and \(dn_1^+(G) = b\).
An orthogonal double cover (ODC) of the complete graph \(K_n\) is a collection \(\mathcal{G} = \{G_1,G_2,\ldots,G_n\}\) of \(n\) subgraphs of \(K_n\), such that every edge of \(K_n\) belongs to exactly two of the \(G_i\)’s and every pair of \(G_i\)’s intersect in exactly one edge. If \(G_i \cong G\) for all \(i \in \{1,2,\ldots,n\}\), then \(\mathcal{G}\) is an ODC of \(K_n\) by \(G\). An ODC of \(K_n\) is \emph{cyclic} (CODC) if the cyclic group of order \(n\) is a subgroup of its automorphism group. In this paper, we find CODCs of complete graphs by the complete multipartite graphs \(K_{2,r,s}\), \(K_{1,1,r,s}\), and \(K_{1,1,1,1,r}\).
An \emph{Edge Roman dominating function} of a graph \(G = (V, E)\) is a function \(f’ : E \to \{0,1,2\}\) satisfying the condition that every edge \(x\) for which \(f'(x) = 0\) is adjacent to at least one edge \(y\) for which \(f'(y) = 2\). The \emph{weight} of an Edge Roman dominating function is the value \(f'(E) = \sum_{x\in E} f'(x)\). The minimum weight of an Edge Roman dominating function on a graph \(G\) is called the \emph{Edge Roman domination number} of \(G\). In this paper, we initiate a study of this parameter.
The energy \(E(G)\) of a graph \(G\) is the sum of the absolute values of the eigenvalues of \(G\). Two graphs \(G_1\) and \(G_2\) are said to be equienergetic if \(E(G_1) = E(G_2)\). In this paper, we outline various classes of equienergetic graphs. These results enable the construction of pairs of noncospectral equienergetic graphs of the same order and of the same size.
In this paper, fuzzy finite state automaton with unique membership transition on an input symbol (uffsa) is defined. It is proved and illustrated that for a given fuzzy finite state automaton (ffsa), there exists an equivalent uffsa. Some closure properties of fuzzy regular languages are studied.
A \((G,H)\)-multifactorization of \(\lambda K_m\) is a partition of the edge set of \(\lambda K_m\) into \(G\)-factors and \(H\)-factors with at least one \(G\)-factor and one \(H\)-factor. Atif Abueida and Theresa O’Neil have conjectured that for any integer \(n \geq 3\) and \(m \geq n\), there is a \((G_n, H_n)\)-multidecomposition of \(\lambda K_m\) where \(G_n = K_{1,n-1}\) and \(H_n = C_n\). In this paper, it is shown that the above conjecture is true for \(m=n\) when
For a path \( P_n \) of order \( n \) and for any odd integer \( k \), \( 1 \leq k \leq n – 3 \), Chartrand et al. have given an upper bound for the radio \( k \)-chromatic number of \( P_n \) as \( \frac{k^2+2k+1}{2} \). Here we improve this bound for \( \frac{n-4}{2} \leq k < \frac{2n-5}{3} \) and \( \frac{2n-5}{3} \leq k \leq n-3 \). They are \( \frac{k^2+k+4}{2} \) and \( \frac{k^2+k+2}{2} \), respectively. Also, we improve the lower bound of Kchikech et al. from \( \frac{k^2+3}{2} \) to \( \frac{k^2+5}{2} \) for odd integer \( k \), \( 3 \leq k \leq n-3 \).
In this paper, we obtain a necessary condition for the Skolem gracefulness of the disjoint union of \( k \) signed stars \( K_{1,r_i}, 1 \leq i \leq k \), which we call a \( k \)-signed star \( St(r_1,r_2,\ldots,r_k) \). We also present results on the Skolem gracefulness of the 2-signed star \( St(r_1,r_2) \).
In this paper, a definition of a variation of the standard notion of the line signed graph of a given signed graph is recalled from [14] and some fundamental results linking it to the notions of jump signed graphs [6] and adjacency signed graphs [21], especially with regard to their states of balance, consistency, and compatibility are obtained.
In this paper, we discuss how the addition of a new edge changes the irregularity strength in \( K_{m,m} \) and \( tC_4 \).
The goal of this article is to provide an overview of all the results currently known regarding the connectedness of path graphs. The proofs we present are only those that illustrate the different techniques employed in obtaining the results.
This is an expository paper addressed to readers with a small degree of familiarity with the field of graph theory and its techniques.
This paper presents some new results on permissible degree sets in polygon visibility graphs (PVGs). If the PVG has \( n \) vertices, we say it is an \( n \)-PVG. We also show some canonical construction techniques for PVGs with given degree sets.
In this paper, we present several graph theory related software systems that we have developed. These systems have been used in learning and research. The systems feature drawing and manipulation of graphs as well as execution of graph algorithms. The systems are: JGraph, a Java-based system for creating graphs and running graph algorithms; Colossus, a visibility graph system; Manohar, a system for computing graceful labelings of graphs (with special emphasis on trees); Graph Algorithm Constructor, which allows the creation of graph algorithms by drawing flow diagrams instead of writing source code. We also describe some examples in which the empirical data generated from these systems have allowed us to discover fundamental properties of graphs.
A simple acyclic graphoidal cover of a graph \( G \) is a collection \( \psi \) of paths in \( G \) such that every path in \( \psi \) has at least two vertices, every vertex of \( G \) is an internal vertex of at most one path in \( \psi \), every edge of \( G \) is in exactly one path in \( \psi \), and any two paths in \( \psi \) have at most one vertex in common. The minimum cardinality of a simple acyclic graphoidal cover of \( G \) is called the simple acyclic graphoidal covering number of \( G \) and is denoted by \( \eta_{as}(G) \). A simple acyclic graphoidal cover \( \psi \) of \( G \) with \( |\psi| = \eta_{as}(G) \) is called a minimum simple acyclic graphoidal cover of \( G \). Two minimum simple acyclic graphoidal covers \( \psi_1 \) and \( \psi_2 \) of \( G \) are said to be isomorphic if there exists an automorphism \( \alpha \) of \( G \) such that \( \psi = \{\alpha(P) : P \in \psi_1\} \). In this paper, we characterize trees, unicyclic graphs, and wheels in which any two minimum simple acyclic graphoidal covers are isomorphic.
In this paper, we study the domination number, the global domination number, the cographic domination number, the global cographic domination number, and the independent domination number of all the graph products which are non-complete extended \( p \)-sums (NEPS) of two graphs.
A sum composite labeling of a \((p,q)\) graph \( G = (V,E) \) is an injective function \( f : V(G) \to \{1,2,\dots,2p\} \) such that the function \( f^+ : E(G) \to C \) is also injective, where \( C \) denotes the set of all composite numbers and \( f^+ \) is defined by \( f^+(uv) = f(u) + f(v) \) for all \( uv \in E(G) \). A graph \( G \) is sum composite if there exists a sum composite labeling for \( G \). We give some classes of sum composite graphs and some classes of graphs which are not sum composite. We prove that it is possible to embed any graph \( G \) with a given property \( P \) in a sum composite graph which preserves the property \( P \), where \( P \) is the property of being connected, eulerian, hamiltonian, or planar. We also discuss the NP-completeness of the problem of determining the chromatic number and the clique number of sum composite graphs.
A \((p,q)\)-graph \( G \) is said to be \((k,d)\)-multiplicatively indexable if there exists an injection \( f : V(G) \to \mathbb{N} \) such that \( f^\times(E(G)) = \{k,k+d,\dots,k+(q-1)d\} \), where \( f^\times : E(G) \to \mathbb{N} \) is defined by \( f^\times(uv) = f(u)f(v) \) for every \( uv \in E(G) \). If further \( f(V(G)) = \{1,2,\dots,p\} \), then \( G \) is said to be a \((k,d)\)-strongly multiplicatively indexable graph. In this paper, we initiate a study of graphs that admit such labellings.
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.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.