Discrete Mathematics, Algorithms and Applications

In this paper, we generalize the concepts of (perfect) Roman and Italian dominations to (perfect) strong Roman and Roman $k$-domination for arbitrary positive integer $k$. These generalizations cover some of previous ones. After some comparison of their domination numbers, as a first study of these concepts, we study the (perfect, strong, perfect strong) Roman $k$-domination numbers of complete bipartite graphs.

Let $S_M=\{0,x,x^2,\dots ,x^n\}$ be a monogenic semigroup with zero. Here, we consider the power graph ${𝒫}({{𝒮}}_M)$ over ${{𝒮}}_M$ with vertex set ${{𝒮}}_M^{\ast }={{𝒮}}_M\backslash \{0\}$ and two distinct vertices $x^i$ and $x^j$ are adjacent if $i$ divides $j$ or $j$ divides $i$, where $1\le i,j\le n$. We compute various graph parameters of ${𝒫}({{𝒮}}_M)$ and topological indices based on distance of vertices. Finally, we compute some graph parameters of the cartesian product ${𝒫}({{𝒮}}_M^1)\square {𝒫}({{𝒮}}_M^2)$ of graphs ${𝒫}({{𝒮}}_M^1)$ and ${𝒫}({{𝒮}}_M^2)$.

Let $d(x,y)$ denote the length of a shortest path between vertices $x$ and $y$ in a graph $G$ with vertex set $V$. For a positive integer $k$, let $d_k(x,y)=min\{d(x,y),k+1\}$ and $R_k\{x,y\}=\{z\in V:d_k(x,z)\ne d_k(y,z)\}$. A set $S\subseteq V$ is a distance-k resolving set of $G$ if $S\cap R_k\{x,y\}\ne \varnothing$ for distinct $x,y\in V$. In this paper, we study the maker-breaker distance-$k$ resolving game (MB$k$RG) played on a graph $G$ by two players, Maker and Breaker, who alternately select a vertex of $G$ not yet chosen. Maker wins by selecting vertices which form a distance-$k$ resolving set of $G$, whereas Breaker wins by preventing Maker from winning. We denote by $O_{R,k}(G)$ the outcome of MB$k$RG. Let ${ℳ}$, ${ℬ}$ and ${𝒩}$, respectively, denote the outcome for which Maker, Breaker, and the first player has a winning strategy in MB$k$RG. Given a graph $G$, the parameter $O_{R,k}(G)$ is a non-decreasing function of $k$ with codomain $\{-1={ℬ},0={𝒩},1={ℳ}\}$. We exhibit pairs $G$ and $k$ such that the ordered pair $(O_{R,k}(G),O_{R,k+1}(G))$ realizes each member of the set $\{({ℬ},{𝒩}),({ℬ},{ℳ}),({𝒩},{ℳ})\}$; we provide graphs $G$ such that $O_{R,1}(G)={ℬ}$, $O_{R,2}(G)={𝒩}$ and $O_{R,k}(G)={ℳ}$ for $k\ge 3$. Moreover, we obtain some general results on MB$k$RG and study the MB$k$RG played on some graph classes.

A result of Friedman and Pippenger gives a sufficient condition on the expansion properties of a graph to contain all small trees with bounded maximum degree. In this paper, we extend the tree embedding problem of expanding graphs to the degenerate graph embedding problem, and give a sufficient condition for a graph to contain strong $2$-degenerate subgraphs with bounded maximum codegree.

Let $R$ be a commutative ring with unity. Taloukolaei and Sahebi [Von Neumann regular graphs associated with rings, Discrete Math. Algorithms Appl. 10(3) (2018) 1850029, doi:10.1142/S1793830918500295] introduced the Von Neumann regular graph $G_{Vnr+}(R)$ of a ring $R$ whose vertices are the elements of $R$ and two distinct vertices $x$ and $y$ are adjacent if and only if $x+y$ is a Von Neumann regular element of $R$. In this paper, we investigate and determine some graph theoretic properties of the line graph $L(G_{Vnr+}(R))$ associated to $G_{Vnr+}(R)$. We give some characterization results regarding the completeness, bipartiteness, traversability, diameter and girth. We also prove Beck’s conjecture for $L(G_{Vnr+}(R))$. Finally we characterize rings having the planarity, the outerplanarity and also being the ring graph of the line graphs associated to Von Neumann regular graphs $L(G_{Vnr+}(R))$ of rings.

In this paper, the $b$-coloring problem is solved for every subdivision-edge neighborhood corona of paths, cycles, stars and complete graphs. In addition, some exact values and sharp bounds are established for the $b$-chromatic number of subdivision-edge neighborhood coronas of these graphs with any other graph.

A total edge irregular $k$-labeling of a graph $G=(V,E)$, $\partial :V\cup E\to \{1,2,3,\dots ,k\}$ is a labeling of vertices and edges of $G$ in such a way that the weights of all edges are distinct. A total edge irregularity strength of graph $G$, denoted by $\mathrm{\text{tes}}(G)$ is defined as the minimum $k$ for which a graph $G$ has a totally irregular total $k$-labeling. In this paper, we define $(a,d)$-total edge irregularity labeling and provide the irregularity strength for some well-known families of graphs.

In this paper, we define the adjacency matrix of a semigraph. We give the conditions for a matrix to be semigraphical and give an algorithm to construct a semigraph from the semigraphical matrices. We derive lower and upper bounds for largest eigenvalues. We study the eigenvalues of adjacency matrix of two types of star semigraphs.

Most of our conventional tools for formal reasoning, computing, and modeling are precise, deterministic, and crisp. However, many complicated problems in the domains of economics, medicine, engineering, the environment, social science, and other disciplines demand data that is not always precise. We cannot always use traditional approaches because there are so many different types of uncertainty present in these problems. This difficulty could be caused by the parameterization tool’s insufficiency. Soft set theory, which Molodtsov presented in 1999, is a generic mathematical approach for handling uncertain data. Many researchers are currently using soft set theory to solve problems involving decision-making. The concept of soft graphs is used to provide a parameterized point of view for graphs. The topic of graph products has received a lot of interest in graph theory. It is a binary operation on graphs with numerous combinatorial uses. On soft graphs, we can define product operations in a manner similar to how graph products are defined. The co-normal product, the restricted co-normal product, the modular product, and the restricted modular product of soft graphs are all introduced in this study. We prove that these products of soft graphs are again soft graphs and derive methods for computing their vertex count, edge count, and the sum of part degrees.

In this paper, we apply the $m$-polar cubic structures on BCI-algebras. We first present the ideas of $m$-polar cubic $p$-ideals, $m$-polar cubic $q$-ideals and $m$-polar cubic $a$-ideals in BCI-algebras. Then we prove that $m$-polar cubic $p$($q$ and $a$)-ideals are $m$-polar cubic ideals, but the converse assertion is not true, and an example is provided in this support. We define the conditions under which $m$-polar cubic ideals coincide with $m$-polar cubic $p$($q$ and $a$)-ideals. The associated properties of $m$-polar cubic $p$-ideals, $m$-polar cubic $q$-ideals, and $m$-polar cubic $a$-ideals are also examined. Furthermore, we consider $m$-polar cubic $p$($q$ and $a$)-ideals in terms of $p$($q$ and $a$)-ideals of BCI-algebras.

In this paper, we present an efficient algorithm, namely Orienting and Final Circles (OFC)-Delaunay Triangulation, for constructing the Delaunay triangulation of a finite planar point set using the idea of the Method of Orienting Curves (introduced by Phu in Zur Lösung einer regulären Aufgabenklasse der optimalen Steuerung im Groen mittels Orientierungskurven, Optimization 18(1) (1987) 65–81 and Ein konstruktives Lösungsverfahren für das Problem des Inpolygons kleinsten Umfangs von J. Steiner, Optimization 18(3) (1987) 349–359). The concepts of orienting and final circles are introduced. The Delaunay edges are determined by orienting circles and a final circle. Our algorithm has $O$($nlogn$) worst-case running time. The algorithm is implemented in Python and some numerical examples are presented.

For an undirected as well as connected graph $G=(V,E)$, a node point $w\in V(G)$ is edge-vertex dominated by an edge $e\in E(G)$ if $w$ is incident to $e$ or $w$ is incident to an adjacent edge of $e$. A set $D_{\mathrm{\text{EV}}}\underline{\subset }E$ is called an edge-vertex dominating set of $G$ if every node point of $G$ is edge-vertex dominated by at least one edge of $D_{\mathrm{\text{EV}}}$. The minimum cardinality among all edge-vertex dominating sets is the edge-vertex domination number, symbolled by ${\gamma }_{\mathrm{\text{EV}}}(G)$. Here, we propose an algorithm that runs in $O(n)$-time for determining a minimum-cardinality $D_{\mathrm{\text{EV}}}$ of interval graph with $n$ nodes. We also study some properties relating to the edge-vertex dominating set of interval graphs.

Let $G$ be a connected graph and $S$ be a minimum geodetic global dominating set of $G$. A subset $T\subseteq S$ is called a forcing subset for $S$ if $S$ is the unique minimum geodetic global dominating set containing $T$. A forcing subset for $S$ of minimum cardinality is a minimum forcing subset of $S$. The forcing geodetic global domination number of $S$, denoted by $f_{\overline{\gamma }g}(S)$, is the cardinality of a minimum forcing subset of S. The forcing geodetic global domination number of $G$, denoted by $f_{\overline{\gamma }g}(G)$, is $f_{\overline{\gamma }g}(G)=min\{f_{\overline{\gamma }g}(S)\}$, where the minimum is taken over all minimum geodetic global dominating sets $S$ in $G$. The forcing geodetic global domination number of some standard graphs are determined. Some of its general properties are studied. It is shown that for every pair of positive integers a and b with $0\le a\le b$ and $b>a+2$, there exists a connected graph $G$ such that $f_{\overline{\gamma }g}(G)=a$ and $\overline{\gamma }(G)=b$. The geodetic global domination number of join of graphs is also studied. Connected graphs of order $n\ge 2$ with geodetic global domination number 2 are characterized. It is proved that, for a connected graph $G$ with ${\overline{\gamma }}_g(G)=2$. Then $0\le f_{\overline{\gamma }g}(G)\le 1$ and characterized connected graphs for which the lower and the upper bounds are sharp.

An Italian dominating function on a graph $G=(V,E)$ is defined as a function $f:V\to \{0,1,2\}$ satisfying the condition that every vertex $u$ for which $f(u)=0$ is adjacent to at least one vertex $v$ for which $f(v)=2$ or at least two vertices $x,y$ for which $f(x)=f(y)=1$. The weight of an Italian dominating function is $w(f)={\mathrm{\Sigma }}_{v\in V}f(v)$. The Italian domination number is the minimum weight taken over all Italian dominating functions of $G$ and denoted by ${\gamma }_I(G)$. Three domination parameters related to the Italian dominating function are total Italian, restrained Italian, and total restrained Italian dominating function.

A total ((restrained) (total restrained)) Italian dominating function $f$ is an Italian dominating function if the set of vertices with positive label ((the set of vertices with label $0$), (at the same time, the set of vertices with positive label and the set of vertices with label $0$)) induces ((induces) (induce)) a subgraph with no isolated vertex. A minimum weight of any total ((restrained) (total restrained)) Italian dominating function $f$ is called a total ((restrained) (total restrained)) Italian domination number denoted by ${\gamma }_{\mathrm{\text{tI}}}(G)$, ((${\gamma }_{\mathrm{\text{rI}}}(G)$) (${\gamma }_{\mathrm{\text{trI}}}(G)$)). We initiate the study of parameters, restrained and total restrained Italian domination number of a graph $G$ and the middle graph of $G$. For the family of standard graphs, we obtain the exact value of these parameters. For arbitrary graph $G$, we obtain the sharp bounds of these parameters, and for some corona graphs, we establish the precise value of these parameters.

The concept of a modular difference set was originally motivated by the cognate notion of modular Hadamard matrices, which have been researched extensively. We initiate the study of the repetition-parameter set in a modular difference set, and we relate the repetition-parameter set to integer partitions and Diophantine equations. By example, we show how a computational study of integer partitions can improve the upper bound on the size of such repetition-parameter set. All previously known examples of modular difference sets in a direct product of groups are concerned with a product of just two groups. We present new constructions of modular difference sets in a direct product of n groups. These new constructions suggest that the size of the repetition-parameter set is intimately related to the group’s structure. A generalization of difference sets, partial difference sets, and relative difference sets, modular difference sets have been used to construct both modular symmetric designs and equiangular tight frames in finite fields.

A cyclic base ordering (CBO) of a connected graph $G$ is a cyclic ordering of $E(G)$ such that every cyclically consecutive $|V(G)|-1$ edge induces a spanning tree of $G$. The density of $G$ is defined to be $d(G)=|E(G)|/(|V(G)|-1)$; and $G$ is uniformly dense if $d(H)\le d(G)$ for every connected subgraph $H$ of $G$. It was conjectured by Kajitani, Ueno and Miyano that $G$ has a CBO if and only if $G$ is uniformly dense. In this paper, we study CBO of generalized Petersen graphs to support this conjecture, and we prove that $G(n,1)$ and $G(n,2)$ have CBO.