Discrete Mathematics, Algorithms and Applications

The concept of network is predominantly used in several applications of computer communication networks. It is also a fact that the dominating set acts as a virtual backbone in a communication network. These networks are vulnerable to breakdown due to various causes, including traffic congestion. In such an environment, it is necessary to regulate the traffic so that these vulnerabilities could be reasonably controlled. Motivated by this, $k$-part degree restricted domination is defined as follows. For a positive integer $k$, a dominating set $D$ of a graph $G$ is said to be a $k$-part degree restricted dominating set ($k$-DRD set) if for all $u\in D$, there exists a set $C_u\subseteq N(u)\cap (V-D)$ such that $\left|C_u\right|\le \lceil \frac{d(u)}{k}\rceil$ and ${\bigcup }_{u\in D}{C}_u=V-D$. The minimum cardinality of a $k$-DRD set of a graph $G$ is called the $k$-part degree restricted domination number of $G$ and is denoted by ${\gamma }_{\frac{d}{k}}(G)$. In this paper, we present a polynomial time reduction that proves the NP-completeness of the $k$-part degree restricted domination problem for bipartite graphs, chordal graphs, undirected path graphs, chordal bipartite graphs, circle graphs, planar graphs and split graphs. We propose a polynomial time algorithm to compute a minimum $k$-DRD set of a tree and minimal $k$-DRD set of a graph.

This work investigates distributed transmission scheduling in wireless networks. Due to interference constraints, “neighboring links” cannot be simultaneously activated, otherwise transmissions will fail. Here, we consider any binary model of interference. We use the model described by Bui et al. in [L. X. Bui, S. Sanghavi and R. Srikant, Distributed link scheduling with constant overhead, IEEE/ACM Trans. Netw. 17(5) (2009) 1467–1480; S. Sanghavi, L. Bui and R. Srikant, Distributed link scheduling with constant overhead, in Proc. ACM Sigmetrics (San Diego, CA, USA, 2007), pp. 313–324.]. We assume that time is slotted and during each slot there are two phases: one control phase in which a link scheduling algorithm determines a set of non-interfering links to be activated, and a data phase in which data is sent through these links. We assume random arrivals on each link during each slot, so that a queue is associated to each link. Since nodes do not have a global knowledge of the queues sizes, our aim (like in [L. X. Bui, S. Sanghavi and R. Srikant, Distributed link scheduling with constant overhead, IEEE/ACM Trans. Netw. 17(5) (2009) 1467–1480; S. Sanghavi, L. Bui and R. Srikant, Distributed link scheduling with constant overhead, in Proc. ACM Sigmetrics (San Diego, CA, USA, 2007), pp. 313–324.]) is to design a distributed link scheduling algorithm. To be efficient, the control phase should be as short as possible; this is done by exchanging control messages during a constant number of mini-slots (constant overhead). In this paper, we design the first fully distributed local algorithm with the following properties: it works for any arbitrary binary interference model; it has a constant overhead (independent of the size of the network and the values of the queues), and it does not require any knowledge of the queue-lengths. We prove that this algorithm gives a maximal set of active links, where for any non-active link there exists at least one active link in its interference set. We also establish sufficient conditions for stability under general Markovian assumptions. Finally, the performance of our algorithm (throughput, stability) is investigated and compared via simulations to that of previously proposed schemes.

The unit graph of a ring $R$ is the simple graph, denoted by $G(R)$, whose vertex set is $R$, and in which two distinct vertices $x$ and $y$ are adjacent if and only if $x+y$ is a unit of $R$. In this paper, we completely determine the domination number of $G({\mathbb{Z}}_n)$ when $n$ has exactly three prime divisors.

Let $R$ be a commutative ring with identity, and let $Z(R)$ be the set of zero-divisors of $R$. The annihilator graph of $R$ is defined as the graph $\mathrm{\text{AG}}(R)$ with the vertex set $Z{(R)}^{\ast }=Z(R)\setminus \{0\}$, and two distinct vertices $x$ and $y$ are adjacent if and only if ${\mathrm{\text{ann}}}_R(xy)\ne {\mathrm{\text{ann}}}_R(x)\cup {\mathrm{\text{ann}}}_R(y)$. In this paper, we study the perfectness of annihilator graphs of a vast range of rings. Indeed, it is shown that if $R$ is reduced with finitely many minimal primes or nonreduced, then $\mathrm{\text{AG}}(R)$ is perfect.

For a simple connected graph $G$ of order $n$ having distance Laplacian eigenvalues ${\rho }_1^L\ge {\rho }_2^L\ge \cdots \ge {\rho }_n^L$, the distance Laplacian energy $\mathrm{\text{DLE}}(G)$ is defined as $\mathrm{\text{DLE}}(G)={\sum }_{i=1}^n|{\rho }_i^L-\frac{2W(G)}{n}|$, where $W(G)$ is the Wiener index of $G$. We obtain the distance Laplacian spectrum of the joined union of graphs $G_1,G_2,\dots ,G_n$ in terms of their distance Laplacian spectrum and the spectrum of an auxiliary matrix. As application, we obtain the distance Laplacian spectrum of the lexicographic product of graphs. We study the distance Laplacian energy of connected graphs with given chromatic number $\chi$. We show that among all connected graphs with chromatic number $\chi$ the complete $\chi$-partite graph has the minimum distance Laplacian energy. Further, we discuss the distribution of distance Laplacian eigenvalues around average transmission degree $\frac{2W(G)}{n}$.

Let $G=(V,E)$ be a graph. A subset $S\subseteq V$ of vertices is a dominating set if every vertex in $V-S$ is adjacent to at least one vertex of $S$. The domination number is the minimum cardinality of a dominating set. Let $u,v\in V$. Then, $u$ strongly dominates $v$ and $v$ weakly dominates $u$ if (i) $uv\in E$ and (ii) $degu\ge degv$. A subset $D$ of $V$ is a strong (weak) dominating set of $G$ if every vertex in $V-D$ is strongly (weakly) dominated by at least one vertex in $D$. The strong (weak) domination number of $G$ is the minimum cardinality of a strong (weak) dominating set. A set $D\subseteq V$ is an independent (or stable) set if no two vertices of $D$ are adjacent. The independent domination number of $G$ (independent strong domination number, independent weak domination number, respectively) is the minimum size of an independent dominating set (independent strong dominating set, independent weak dominating set, respectively) of $G$. In this paper, mathematical models are developed for the problems of independent domination and independent strong (weak) domination of a graph. Then test problems are solved by the GAMS software, the optima and execution times are implemented. To the best of our knowledge, this is the first mathematical programming formulations for the problems, and computational results show that the proposed models are capable of finding optimal solutions within a reasonable amount of time.

Let $p$ be a prime such that $p\ne 3$. The algebraic structures of all cyclic and negacyclic codes of length $3p^s$ over the finite commutative chain ring $R:={𝔽}_{p^m}+u{𝔽}_{p^m}(u^2=0)$ are obtained that the conditions depend on the factorization of polynomial $x^2+x+1$ over $R$. Therefore, we classify the structures of cyclic and negacyclic codes of length $3p^s$ over $R$ into 2 cases, i.e., $p^m\equiv 1(mod3)$ and $p^m\equiv 2(mod3)$. From that we obtain the number of all cyclic and negacyclic codes of length $3p^s$ over $R$. After that, we give some situations for such cyclic and negacyclic codes are self-dual codes.

Let $G=(V,E)$ be a simple connected graph of order $p$ and size $q$. A decomposition of a graph $G$ is a collection of edge-disjoint subgraphs $G_1,G_2,\dots ,G_n$ of $G$ such that every edge of $G$ belongs to exactly one $G_i,(1\le i\le n)$. The decomposition $\pi =\{G_1,G_2,\dots ,G_n\}(n\ge 2)$ of a connected graph $G$ is said to be an edge geodetic self-decomposition if $g_e(G_i)=g_e(G)$ for all $i(1\le i\le n)$. Some general properties satisfied by this concept are studied.

Let $G$ be a simple and undirected graph with vertex set $V$. A set $D\subseteq V$ is called a dominating set of $G$, if every vertex in $V\setminus D$ is adjacent to at least one vertex in $D$. The minimum cardinality of a dominating set of $G$ is called the domination number of $G$, denoted by $\gamma (G)$. A dominating set $D$ of $G$ is called isolate dominating, if the induced subgraph $G[D]$ of $G$ contains at least one isolated vertex. The minimum cardinality of an isolate dominating set of $G$ is called the isolate domination number of $G$, denoted by ${\gamma }_0(G)$. In this paper, we show that for every proper interval graph $G$, ${\gamma }_0(G)=\gamma (G)$. Moreover, we provide a constructive characterization for trees with equal domination number and isolate domination number. These solve part of an open problem posed by Hamid and Balamurugan [Isolate domination in graphs, Arab J. Math. Sci. 22(2) (2016) 232–241].

Let $G$ be a connected simple graph. A set $S\subseteq V(G)$ is a doubly connected dominating set if it is dominating and both $〈S〉$ and $〈V(G)\setminus S〉$ are connected. A nonempty subset $S$ of the vertex set $V(G)$ is a clique in $G$ if the graph $〈S〉$ induced by $S$ is complete. A clique dominating set $S$ of $G$ is a clique doubly connected dominating set if $S$ is a doubly connected dominating set of $G$. The clique doubly connected domination number of $G$, denoted by ${\gamma }_{\mathrm{\text{cld}}}(G)$, is the smallest cardinality of a clique doubly connected dominating set $S$ of $G$. In this paper, we give the characterization of the clique doubly connected dominating set and the clique doubly connected domination number in the join (and lexicographic product) of two graphs.

We study a maximization problem for geometric network design. Given a set of $n$ compact neighborhoods in ${ℝ}^d$, select a point in each neighborhood, so that the longest spanning tree on these points (as vertices) has maximum length. Here, we give an approximation algorithm with ratio $0.511$, which represents the first, albeit small, improvement beyond $1/2$. While we suspect that the problem is NP-hard already in the plane, this issue remains open.

In this paper, we investigate the upper and lower bounds for the sum of domination number of a graph and its total graph and characterize the extremal graphs.

In this paper, we study the time-bounded adaptive information coverage problem with myopic feedback (TBAIC) under a variant of the independent cascade (IC) model. In practical applications, time or deadline is a critical factor to evaluate the effectiveness of a strategy. Along this line, with considering deadline $T$, we sequentially select $k$ ($k<T$) nodes as seed nodes, one at a time step, from a social network, and after a seed is selected at step $t$, it reveals the set of its activated neighbors, which will be valuable information for selecting subsequent seeds. On the other hand, during information propagation, if an active node fails to activate its neighbors, though not become active, those neighbors will know the information and may become active at a later step, we name them as covered nodes. In terms of information coverage, those covered nodes also make contributions. Therefore, our problem aims to choose a policy to maximize the expected cumulative number of both active and covered nodes throughout the time within deadline. We prove that our problem is adaptive monotone and adaptive submodular, which guarantees the adaptive greedy policy with myopic feedback to achieve an approximation ratio of $(1-1/e)$. Additionally, we propose two algorithms to speed up the greedy policy.

Locating the source of diffusion in complex networks is an exciting but challenging task. It is critical for preventing and controlling the epidemic risks. Source localization has been studied under many feasible models. In this paper, we discuss the localization problem in Kayak paddle graphs $\mathrm{\text{KP}}(l,m,n)$ for $l,m\ge 3$ and $n\ge 2$ by computing edge version of metric and double metric dimensions.

The $t$-pebbling number, $f_t(G)$, of a connected graph $G$, is the smallest positive integer such that from every placement of $f_t(G)$ pebbles, $t$ pebbles can be moved to any specified target vertex by a sequence of pebbling moves, each move taking two pebbles off a vertex and placing one on an adjacent vertex. A graph $G$ satisfies the $2t$-pebbling property if $2t$ pebbles can be moved to any specified vertex when the total starting number of pebbles is $2f_t(G)-q+1$, where $q$ is the number of vertices with at least one pebble. We show that the cycle $C_{2n}$ satisfies the $2t$-pebbling property. Herscovici conjectured that for any connected graphs $G$ and $H$, $f_{st}(G\times H)\le f_s(G)f_t(H)$. We prove Herscovici’s conjecture is true, when $G$ is an even cycle and for variety of graphs $H$ which satisfy the $2t$-pebbling property.