Discrete Mathematics, Algorithms and Applications

In this paper, based on the outcomes from the published literature, a brief survey of domination of fuzzy graphs is presented. Discovering what has been accomplished for a particular kind of domination and staying aware of new revelations are difficult due to the huge number of papers and on the grounds that a significant number of the papers have been published in journals that are not broadly accessible. This survey is based on the papers that I could find on the domination of fuzzy graphs. For the comfort of the reader, the overview incorporates some basic definitions and techniques used to study domination of fuzzy graphs.

A set $S\subseteq V$ is called an open detour set of $G$ if for each vertex $v$ in $G$, either (1) $v$ is a detour simplicial vertex of $G$ and $v\in S$ or (2) $v$ is an internal vertex of an $x$-$y$ detour for some $x,y\in S$. An open detour set of minimum cardinality is called a minimum open detour set and this cardinality is the open detour number of $G$, denoted by $odn(G)$. Connected graphs of order $p$ with open detour number $p$ or $p-1$ are characterized. It is shown that for any two positive integers $a$ and $b$ with $b\ge 2a$, there exists a connected graph $G$ such that $dn(G)=b$ and $odn(G)=a+b$, where $dn(G)$ is the detour number of $G$. It is also shown that for every pair of positive integers $a$ and $b$ with $a\ge 4$ and $b\ge 4$, there exists a connected graph $G$ such that $og(G)=a$ and $odn(G)=b$, where $og(G)$ is the open geodetic number of $G$.

For any finite simple undirected graph $G=(V(G),E(G))$, we consider the binary relation ${\leftarrow }_G$ on the powerset ${𝒫}(V(G))$ of its vertex set given by $B{\leftarrow }_{G}A$ if ${\bigcap }_{v\in B}{N}_G(v)\supseteq {\bigcap }_{v\in A}{N}_G(v)$, where $N_G(v)$ denotes the neighborhood of a vertex $v$. We call the above relation set adiacence dependency (sa)-dependency of $G$. With the relation ${\leftarrow }_G$ we associate an intersection-closed family $C{L}_{sa}(G)$ of vertex subsets and the corresponding induced lattice $ℭ(G):=(C{L}_{sa}(G),\subseteq )$, which we call sa-lattice of $G$. Through the equality of sa-lattices, we introduce an equivalence relation ${\equiv }_{sa}$ between graphs and propose three different classifications of graphs based on such a relation. Furthermore, we determine the sa-lattice for various graph families, such as complete graphs, complete bipartite graphs, cycles and paths and, next, we study such a lattice in relation to the Cartesian and the tensor product of graphs, verifying that in most cases it is a graded lattice. Finally, we provide two algorithms, namely, the T-DI ALGORITHM and the O-F ALGORITHM, in order to provide two different computational ways to construct the sa-lattice of a graph. For the O-F ALGORITHM we also determine its computational complexity.

This paper aims to find certain bounds for the domination number of Latin square graphs, i.e., a simple graph assigned to a Latin square. In fact, we show that if $L$ is a Latin square of order $n$ and $\mathrm{\Gamma }(L)$ is the associated Latin square graph of $L$, then $\lceil \frac{n}{2}\rceil \le \gamma (\mathrm{\Gamma }(L))\le n-1$. We will investigate in which case the equalities hold. Finally, we study the domination number of Latin square graph associated to groups. In particular, we show that if $n\equiv 2(\mathrm{\text{mod}}4)$, then $\gamma (\mathrm{\Gamma }(L({\mathbb{Z}}_n)))=\frac{n}{2}$. Also, we prove that if $n\equiv 0(\mathrm{\text{mod}}4)$, then $\gamma (\mathrm{\Gamma }(L({\mathbb{Z}}_n)))\in \{\frac{n}{2},\frac{n+2}{2}\}$.

A vertex $v$ of a graph $G=(V,E)$ is said to vertex-edge dominate every edge incident to $v$, as well as every edge adjacent to these incident edges. A subset $S\subseteq V$ is a vertex-edge dominating set (ve-dominating set) if every edge of $E$ is vertex-edge dominated by at least one vertex of $S$. A vertex-edge dominating set is said to be total if its induced subgraph has no isolated vertices. The minimum cardinality of a total vertex-edge dominating set of $G$, denoted by ${\gamma }_{ve}^t(G)$, is called the total vertex-edge domination number of $G$. In this paper, we prove that for every nontrivial tree of order $n$, with $l$ leaves and $s$ support vertices we have ${\gamma }_{ve}^t(G)\ge (n-l-s+6)/4$, and we characterize extremal trees attaining the lower bound.

The purpose of this paper is to highlight the importance of planar near-rings (PNR) in the construction of balanced incomplete block designs (BIBD), then to give a new precise formula to blocks of this type of BIBD which enables us to generate useful matrices based on the incidence matrix. Moreover, we will improve the efficiency factor and determine the condition to produce a symmetric BIBD from a BIBD.

We provide upper bounds on the chromatic number of the square of graphs, which have vertex ordering characterizations. We prove that $G^2$ is $(3\mathrm{\Delta }-2)$-colorable when $G$ is a cocomparability graph, $(\mathrm{\Delta }+\mu )$-colorable when $G$ is a strongly orderable graph and $(\mathrm{\Delta }+1)$-colorable when $G$ is a dually chordal graph, where $\mathrm{\Delta }(G)$ is the maximum degree and $\mu (G)$ = max$\{|N_G(x)\cap N_G(y)|:x,y\in V(G)\}$ is the multiplicity of the graph $G$. This improves the currently known upper bounds on the chromatic number of squares of graphs from these classes.

Let $G=(V,E)$ be a graph. A signed graph is an ordered pair $\mathrm{\Sigma }=(G,\sigma )$ where $G=(V,E)$ is a graph called the underlying graph of $\mathrm{\Sigma }$ and $\sigma :E\to \{+,-\}$ is a function called a signature or signing function. Motivated by the innovative paper of B. D. Acharya on domination in signed graphs, we consider another way of defining the concept of domination in signed graphs which looks more natural and has applications in social science. A subset $S$ of $V$ is called a dominating set of $\mathrm{\Sigma }$ if $|N^{+}(v)\cap S|>|N^{-}(v)\cap S|$ for all $v\in V-S$. The domination number of $\mathrm{\Sigma }$, denoted by ${\gamma }_s(\mathrm{\Sigma })$, is the minimum cardinality of a dominating set of $\mathrm{\Sigma }$. Also, a dominating set $S$ of $\mathrm{\Sigma }$ with $\left|S\right|={\gamma }_s$ is called a ${\gamma }_s$-set of $\mathrm{\Sigma }$. In this paper, we initiate a study on this parameter.

Let $\mathrm{\Psi }=\mathrm{\Psi }(𝕍,𝔼)$ be an undirected (i.e., all the edges are bidirectional), simple (i.e., no loops and multiple edges are allowed), and connected (i.e., between every pair of nodes, there exists a path) graph. Let $d_{\mathrm{\Psi }}({\varrho }_i,{\varrho }_j)$ denotes the number of edges in the shortest path or geodesic distance between two vertices ${\varrho }_i,{\varrho }_j\in 𝕍$. The metric dimension (or the location number) of some families of plane graphs have been obtained in [M. Imran, S. A. Bokhary and A. Q. Baig, Families of rotationally-symmetric plane graphs with constant metric dimension, Southeast Asian Bull. Math. 36 (2012) 663–675] and an open problem regarding these graphs was raised that: Characterize those families of plane graphs $\mathrm{\Phi }$ which are obtained from the graph $\mathrm{\Psi }$ by adding new edges in $\mathrm{\Psi }$ such that $\beta (\mathrm{\Psi })=\beta (\mathrm{\Phi })$ and $𝕍(\mathrm{\Phi })=𝕍(\mathrm{\Psi })$. In this paper, by answering this problem, we characterize some families of plane graphs ${\mathrm{\Gamma }}_n$, which possesses the radial symmetry and has a constant metric dimension. We also prove that some families of plane graphs which are obtained from the plane graphs, ${\mathrm{\Gamma }}_n$ by the addition of new edges in ${\mathrm{\Gamma }}_n$ have the same metric dimension and vertices set as ${\mathrm{\Gamma }}_n$, and only 3 nodes appropriately selected are sufficient to resolve all the nodes of these families of plane graphs.

Domination is an emerging field in graph theory and many domination parameters were introduced in the meanwhile for different real time situations. Minimum domination number of a graph can be identified by converting the problem into linear programming problem (LPP). In this paper, LPP formulation for strong domination number, restrained domination number and strong restrained domination were developed. MATLAB program was coded to find the values of these parameters. The chain relations among these parameters are tried in four different types of network topologies. Simulation for these four parameters under four network topologies were conducted and it was noticed that in three network types, ${\gamma }_r\le {\gamma }_s$ whereas, in the other one, ${\gamma }_s\le {\gamma }_r$. An improved upper bound for restrained domination number was approximated by using the probabilistic method.

A set $S\subseteq V$ of vertices in a graph $G=(V,E)$ is called a dominating set if every vertex in $V-S$ is adjacent to a vertex in $S$. An independent transversal dominating set in a graph $G$ is a dominating set which intersects every maximum independent set of $G$. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of $G$ denoted by ${\gamma }_{\mathrm{\text{it}}}(G)$. In this paper, we characterize those trees whose independent transversal domination number does not alter owing to the deletion of a vertex.

Self-Reciprocal Irreducible Monic (SRIM) and Self-Conjugate-Reciprocal Irreducible Monic (SCRIM) factors of $x^n-1$ over finite fields have become of interest due to their rich algebraic structures and wide applications. In this paper, these notions are extended to factors of $x^n+1$ over finite fields. Characterization and enumeration of SRIM and SCRIM factors of $x^n+1$ over finite fields are established. Simplification and recessive formulas for the number of such factors are given. Finally, applications in the study of complementary negacyclic codes are discussed.

The enhanced power graph ${{𝒫}}_e(G)$ of a group $G$ is a simple undirected graph with vertex set $G$ and two distinct vertices $x,y$ are adjacent if both $x$ and $y$ belongs to same cyclic subgroup of $G$. In this paper, we obtain various graph invariants viz. independence number, minimum degree and matching number of ${{𝒫}}_e(G)$, where $G$ is the dicyclic group or a class of groups of order $8n$. If $G$ is any of these groups, we prove that ${{𝒫}}_e(G)$ is perfect and then obtain its strong metric dimension.

In this paper, we study the generalized distance matrix $D_{\alpha }(G)$ assigned to simple connected graph $G$, which is the convex combinations of Tr$(G)$ and $D(G)$ and defined as

Let $k\ge 1$ be an integer, and let $G$ be a graph. A k-rainbow dominating function (or $k$RDF) of $G=(V,E)$ is a function $f$ from the vertex set $V(G)$ to the family of all subsets of $\{1,2,\dots ,k\}$ such that for very $v\in V(G)$ with $f(v)=\varnothing$, the condition ${\bigcup }_{u\in N_G(v)}f(u)=\{1,2,\dots ,k\}$ is fulfilled, where $N_G(v)$ is the open neighborhood of $v$. The weight of a $k$RDF $f$ of $G$ is the value $\omega (f)={\sum }_{v\in V(G)}|f(v)|$. A k-rainbow dominating function $f$ in a graph with no isolated vertex is called a total k-rainbow dominating function if the subgraph of $G$ induced by the set $\{v\in V(G)|f(v)\ne \varnothing \}$ has no isolated vertices. The total k-rainbow domination number of $G$, denoted by ${\gamma }_{trk}(G)$, is the minimum weight of the total $k$-rainbow dominating function on $G$. The total k-rainbow reinforcement number of $G$, denoted by $r_{trk}(G)$, is the minimum number of edges that must be added to $G$ in order to decrease the total k-rainbow domination number. In this paper, we investigate the properties of total $k$-rainbow reinforcement number in graphs. In particular, we present some sharp bounds for $r_{trk}(G)$ and we determine the total $k$-rainbow reinforcement number of some classes of graphs including paths, cycles and complete bipartite graphs.

In this paper, we use the Nelson lemma to give a new proof for the essential self-adjointness of the discrete Laplace operator acting on 3-cochains, which we are defined in our previous paper [A. Baalal and K. Hatim, The discrete Laplacian of a 3-simplicial complex (2019), https://hal.archives-ouvertes.fr/hal-02105789]. Moreover, we establish on the infimum of the essential spectrum an upper bound.