Discrete Mathematics, Algorithms and Applications

An MRD code ${𝒞}(n,k,n-k+1)$ is a $k$-dimensional ${𝔽}_{q^N}$-linear subspace of the $n$-dimensional vector space ${𝔽}_{q^N}^n$ over ${𝔽}_{q^N}$ for $n\le N$. Linear codes ${{𝒞}}^{\prime }(n^{\prime },k^{\prime },d)$ (of length $n^{\prime }\ge n$, dimension $k^{\prime }\ge k$) that are obtained from MRD codes ${𝒞}(n,k,d)$ satisfying the property ${{𝒞}}^{\prime }\cap {{{𝒞}}^{\prime }}^{\perp }=\{0\}$ are defined to be LCD MRD codes. An inherent relationship between the generator G and parity-check matrices H of LCD MRD codes is observed. This in fact identifies LCD MRD codes as trivial ($G{G}^T=I$) and nontrivial ($G{G}^T\ne I$) codes. Further, two classes of LCD MRD codes of length $n\ell$ are constructed from $\ell$ (trivial and nontrivial) LCD MRD codes of length $n$. Examples are provided for demonstration of results obtained.

We address in this paper the connected $p$-median problem on complete multi-layered graphs. We first solve the corresponding 1-median problem on the underlying graph in linear time based on the structure of the induced path. For $p\ge 2$, we prove that the connected $p$-median contains at least one vertex in the layered set corresponding to the 1-median or its adjacent vertices in the induced path. Then, we develop an $O(nlogn)$ algorithm that solves the problem on a complete multi-layered graph with $n$ vertices.

In this paper, we characterize uniquely colorable graphs with equal chromatic and game chromatic numbers.

A hypergraph is given by $H=(V,E)$, where $V$ is a set of vertices and $E$ is a set of nonempty subsets of $V$, the member of $E$ is named hyperedge. So, a hypergraph is a nature generalization of a graph. A hypergraph has a complex structure, thus some researchers try to transform a hypergraph to a graph. In this paper, we define two graphs, Clique graph and Persian graph. These relations are one to one. We can find the shortest path between two vertices in a hypergraph $H$, by using the Dijkstra algorithm in graph theory on the graphs corresponding to $H$.

In this paper, we obtain explicitly the $r$-dynamic chromatic number of the direct product of a path $P_m$ with a $k$-subdivision $S_n^{\frac{1}{k}}$ of a star graph, for every positive integers $r$, $m$, $k$ and $n$. Particularly, it is obtained that $2\le {\chi }_r(P_m\times S_n^{\frac{1}{k}})\le 2n+1$.

In this paper, we want to investigate some theorems about ${𝒩}$-cubic sets in [Sh. Rashid, M. Gulistan, Y. B. Jun, S. Khan and S. Kadry, ${𝒩}$-cubic sets and aggregation operators, J. Intell. Fuzzy Syst. 37(4) (2019) 5009–5023] and while correcting these theorems, we get new results in this issue and at the end we present an application regarding decision making. First, by using some examples, we show that the conditions of some theorems in above-mentioned paper are not true in general and then we attempt to correct these theorems and proofs. Moreover, we discuss some new related results in ${𝒩}$-cubic sets. Finally, we discuss the score function and ${𝒩}$-cubic weighted average operator of ${𝒩}$-cubic sets for application in physical and different engineering regions.

The sunlet graph of order eight, denoted by $L_8,$ is the graph obtained by adding a pendant edge to each vertex of a cycle of length $4.$ We prove that the $n$-dimensional hypercube $Q_n$ can be decomposed into the copies of the graph $L_8$ if and only if $n$ is 4 or $n\ge 6.$

In this short note, we prove that the degree-three dilation of the square lattice ${\mathbb{Z}}^2$ is $1+\sqrt{2}$. This disproves a conjecture of Dumitrescu and Ghosh. We give a computer-assisted proof of a local-global property for the uncountable set of geometric graphs achieving the optimal dilation.

For a simple, undirected, connected graph $G$, a function $h:V(G)\to \{0,1,2\}$ which satisfies the following conditions is called a weakly connected Roman dominating function (WCRDF) of $G$ with weight $h(V)={\sum }_{p\in V}h(p)$. (C1). For all $q\in V$ with $h(q)=0$ there exists a vertex $r$ such that $(q,r)\in E$ and $h(r)=2$ and (C2). The graph with vertex set $V(G)$ and edge set $\{(p,z):h(p)\ge 1$ or $h(z)\ge 1$ or both$\}$ is connected. The problem of determining WCRDF of minimum weight is called minimum weakly connected Roman domination problem (MWCRDP). In this paper, we show that MWCRDP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a $2(1+𝜖)(1+ln(\mathrm{\Delta }-1))$-approximation algorithm for the MWCRDP and show that the same cannot have $(1-\delta )ln\left|V\right|$ ratio approximation algorithm for any $\delta >0$ unless $P=NP$. Next, we show that MWCRDP is APX-hard for graphs with $\mathrm{\Delta }=4$. We also show that the domination and weakly connected Roman domination problems are not equivalent in computational complexity aspects. Finally, two different integer linear programming formulations for MWCRDP are proposed.

Graphs considered here are simple, finite and undirected. A graph is denoted by $G$ and its vertex set by $V(G)$ and edge set by $E(G)$. Kulli and Janakiram introduced the concept of the strong non-split domination number of a graph [The strong non-split domination number of a graph, Int. J. Manag. Syst. 19 (2003) 2]. The concept of fair domination was introduced by Yaro Caro et al. in [Fair domination in graphs, Discrete Math. 312 (2012) 2905–2914]. This paper is an outcome of the combination of these two concepts.

In this paper, we propose a set cover game and show that any Nash equilibrium is a minimal set cover, and also a Pareto optimal solution. Then we present a distributed algorithm to realize the game. The algorithm is self-organizing in the sense that all players can make decisions by themselves simultaneously. It is local in the sense that each player makes his decision based only on information in his neighborhood. It is efficient in the sense that it converges to a minimal set cover in polynomial time when $c_{max}/c_{min}$ is upper bounded by a polynomial of the input size, where $c_{max}$ and $c_{min}$ are the maximum cost and the minimum cost of sets, respectively.

Let $G$ be a plane graph with a set of faces $F(G)$ and $\psi :V(G)\to \{1,2,\dots ,k\}$ be a (not necessarily proper) vertex $k$-coloring. $\psi$ is called polychromatic if all $k$ colors appear on the vertices of its boundary for each face (also the outer-face) $f\in F(G)$. The polychromatic number of $G$ is the largest number of colors $k$ such that $G$ admits a polychromatic $k$-coloring. In the paper, we consider a class of plane graphs ${𝒢}$ with minimum face size $g$, in each of which every pair of faces have at most $t$ common incident vertices, and show that the polychromatic number for each $G\in {𝒢}$ is at least $g-t-2$. When $g\ge 4t+4$, the result improves a known lower bound.

A total coloring of a graph G is an assignment of colors to all the elements (vertices and edges) of the graph in such a way that no two adjacent or incident elements receive the same color. The Total Chromatic Number, ${\chi }^{″}(G)$ is the minimum number of colors which need to be assigned to obtain a total coloring of the graph $G$. The Total Coloring Conjecture made independently by Behzad and Vizing claims that, $\mathrm{\Delta }(G)+1\le {\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$, where $\mathrm{\Delta }(G)$ represents the maximum degree of $G$. The lower bound is sharp, the upper bound remains to be proved. In this paper, we prove the Total Coloring Conjecture for certain classes of lexicographic product and deleted lexicographic product of graphs.

Let $G$ be a finite and simple graph with vertex set $V(G)$. Let $f$ be a function that assigns label from the set $\{0,1,2,3,4,5\}$ to the vertices of a graph $G$. For a vertex $v\in V(G)$, the active neighborhood of $v$, denoted by $\text{AN}(v)$, is the set of vertices $w\in N_G(v)$ such that $f(w)\ge 1$. A quadruple Roman dominating function (QRDF) is a function $f:V(G)\to \{0,1,2,3,4,5\}$ satisfying the condition that for any vertex $v\in V(G)$ with $f(v)<4,f(N_G[v])\ge |\text{AN}(v)|+4$. The weight of a QRDF is $\omega (f)={\mathrm{\Sigma }}_{v\in V(G)}f(v)$. The quadruple Roman domination number ${\gamma }_{[4R]}(G)$ of $G$ is the minimum weight of a QRDF on $G$. In this paper, we investigate the properties of the quadruple Roman domination number of graphs, present bounds on ${\gamma }_{[4R]}(G)$ and give exact values for some graph families. In addition, complexity results are also obtained.

Let $G$ be a graph with the vertex set $V$. A function $f:V\to \{0,1,2\}$ is called a Roman dominating function of $G$, if every vertex $v$ with $f(v)=0$ is adjacent to at least one vertex $u$ with $f(u)=2$. The weight of a Roman dominating function $f$ is equal to ${\sum }_{v\in V(G)}f(v)$. The minimum weight of a Roman dominating function of $G$ is called the Roman domination number of $G$, denoted by ${\gamma }_R(G)$. In this paper, we initiate the study of a variant of Roman dominating functions. A function $f:V(G)\to \{0,1,2\}$ is called an isolate Roman dominating function of $G$, if $f$ is a Roman dominating function and there is a vertex $v$ with $f(v)=0$ which is not adjacent to any vertex $u$ with $f(u)=0$. The minimum weight of an isolate Roman dominating function of $G$ is called the isolate Roman domination number of $G$, denoted by ${\gamma }_{IR}(G)$. We present some upper bound on the isolate Roman domination number of a graph $G$ in terms of its Roman domination number and its domination number. Moreover, we present some classes of graphs $G$ with ${\gamma }_{IR}(G)={\gamma }_R(G)$. Finally, we show that the decision problem associated with the isolate Roman dominating functions is NP-complete for bipartite graphs and chordal graphs.

The problem of characterizing the classes of plane graphs with the bounded metric dimension, edge metric dimension, and fault-tolerant metric dimension is of great interest nowadays. In this paper, we study the metric dimension, the fault-tolerant metric dimension, and the edge metric dimension of a two-fold heptagonal-nonagonal circular ladder (denoted by ${ℍ}_n^{7,9}$). We show that the metric dimension and the edge metric dimension of ${ℍ}_n^{7,9}$ are the same. We also study its fault-tolerant metric dimension and prove that the metric basis and the edge metric basis sets are independent.