Discrete Mathematics, Algorithms and Applications

Assume that $n$ mobile sensors are thrown uniformly and independently at random with the uniform distribution on the unit interval. We study the expected sum over all sensors $i$ from $1$ to $n,$ where the contribution of the $i^{\mathrm{\text{th}}}$ sensor is its displacement from the current location to the anchor equidistant point $t_i=\frac{i}{n}-\frac{1}{2n},$ raised to the $a^{\mathrm{\text{th}}}$ power, when $a$ is an odd natural number.

As a consequence, we derive the following asymptotic identity. Fix $a$ positive integer. Let $X_{i:n}$ denote the $i^{\mathrm{\text{th}}}$ order statistic from a random sample of size $n$ from the Uniform$(0,1)$ population. Then

For a fixed positive integer $k$, a $k$-hop dominating set $D$ of a graph $G=(V,E)$ is a subset of $V$ such that every vertex $x\in V$ is within $k$-steps from at least one vertex $y\in D$, i.e., $d(x,y)\le k$. A $k$-hop dominating set $D$ is said to be minimal if there does not exist any $D^{\prime }\subset D$ such that $D^{\prime }$ is a $k$-hop dominating set of G. A dominating set $D$ is said to be minimum $k$-hop dominating set, if it is minimal as well as it is $k$-hop dominating set. In this paper, we present an optimal algorithm to find a minimum $k$-hop dominating set of interval graphs with $n$ vertices which runs in $O(n)$ time.

We study the log-concavity of a sequence of $p,q$-binomial coefficients located on a ray of the $p,q$-Pascal triangle for certain directions, and we establish the preserving log-concavity of linear transformations associated to $p,q$-Pascal triangle.

Etzion [T. Etzion, Perfect byte correcting codes, IEEE Trans. Inform. Theory 44 (1998) 3140–3146.] has classified byte error correcting binary codes into five different categories with respect to the size of the byte. If a code is partitioned into $m$ equal byte of size say $\beta$ then $n=m\beta$ or the size of bytes is $\frac{n}{m}$. Alternatively if bytes are of different size say, ${\beta }_1,{\beta }_2,\dots ,{\beta }_m$ then $n={\sum }_{i=1}^m{\beta }_i$. The result was further modified by Tyagi and Sethi [V. Tyagi and A. Sethi, $b_i$-Byte correcting perfect codes, Asian-Eur. J. Math. 7(1) (2014) 1–8.] and the classification of bytes was given with respect to size of the byte as well as length of the burst. We call such codes as $b_i$-byte correcting perfect codes. Our aim in this paper is to find the possibilities for the existence of $b_i$-byte correcting non-binary perfect codes.

In this paper, we have introduced the idea of restricted burst, which is the modification of the classical definition of burst. We show the existence of $b_i$-restricted burst correcting non-binary optimal codes for byte-oriented memories with different possibilities of size of the bytes ${\beta }_i$ and length of burst $b_i$ for $i=1,2,\dots ,m$.

A set $D\subseteq V$ for the graph $G=(V,E)$ is called a dominating set if any vertex $v\in V\backslash D$ has at least one neighbor in $D$. Fomin et al. [Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications, ACM Transactions on Algorithms (TALG) 5(1) (2008) 9] gave an algorithm for enumerating all minimal dominating sets with $n$ vertices in $O(1.7159^n)$ time. It is known that the number of minimal dominating sets for interval graphs and trees on $n$ vertices is at most $3^{n/3}\approx 1.4422^n$. In this paper, we introduce the domination cover number as a new criterion for evaluating the dominating sets in graphs. The domination cover number of a dominating set $D$, denoted by ${{𝒞}}_D(G)$, is the summation of the degrees of the vertices in $D$. Maximizing or minimizing this parameter among all minimal dominating sets has interesting applications in many real-world problems, such as the art gallery problem. Moreover, we investigate this concept for different graph classes and propose some algorithms for finding the domination cover number in trees and block graphs.

The aim is to provide a necessary and sufficient condition under which both a graph and its complement have (a) identical radius, (b) identical diameter, (c) identical center, and (d) identical periphery.

We consider the bin packing problem with cardinality constraints in a non-cooperative game setting. In the game, there are a set of items with sizes between 0 and 1, and a number of bins each of which has a capacity of 1. Each bin can pack at most $k$ items, for a given integer parameter $k\ge 2$. The social cost is the number of bins used in the packing. Each item tries to be packed into one of the bins so as to minimize its cost. The selfish behaviors of the items result in some kind of equilibrium, which greatly depends on the cost rule in the game. We say a cost rule encourages sharing if for an item, compared with sharing a bin with some other items, staying in a bin alone does not decrease its cost. In this paper, we first show that for any bin packing game with cardinality constraints under an encourage-sharing cost rule, the price of anarchy of it is at least $2-\frac{2}{k}$. We then propose a cost rule and show that the price of anarchy of the bin packing game under the rule is $2-\frac{2}{k}$ when $k\ge 7$.

In this paper, the notion of interval-valued intuitionistic fuzzy (IVIF) $KU$-subalgebras of $KU$-algebras are introduced and some fundamental properties are discussed. The image and the inverse image of IVIF $KU$-subalgebras are defined and how the image and the inverse image of IVIF $KU$-subalgebras in $KU$-algebras become IVIF $KU$-subalgebras are studied. Moreover, the cartesian product of IVIF $KU$-subalgebras are given.

For a group $G$ and a subset $X$ of $G$, the commuting graph of $X$, denoted by $\mathrm{\Gamma }(X)=ℭ(D(G),X)$ is the graph whose vertex set is $X$ and any two vertices $u$ and $v$ in $X$ are adjacent if and only if they commute in $G$. In this paper, certain properties of the commuting graph of generalized dihedral groups have been studied.

In this paper, we determine the unique tree that maximizes the distance spectral radius in the class of all trees in which each non-pendent vertex has degree at least $p$.

In this paper, we introduce a new complex Fibonacci matrix $H_{p,n}$ whose elements are complex Fibonacci numbers and we developed a new coding and decoding method followed from this complex Fibonacci matrix $H_{p,n}$. We establish the relations among the code matrix elements, error detection and correction for this coding theory.

We study about monotonicity of $r$-identifying codes in binary Hamming space, q-ary Lee space and incomplete hypercube. Also, we give the lower bounds for $M_{1,q}^{(\le l)}(n)$ where $M_{1,q}^{(\le l)}(n)$ is the smallest cardinality among all $r$-identifying codes in ${\mathbb{Z}}_q^n$ with respect to the Lee metric. We prove the existence of $1$-identifying code in an incomplete hypercube. Also, we give the construction techniques for $r$-identifying codes in the incomplete hypercubes in Secs. 4.1 and 4.2. Using these techniques, we give the tables (see Tables 1–6) of upper bounds for $M_{IH,r}(k)$ where $M_{IH,r}(k)$ is the smallest cardinality among all $r$-identifying codes in an incomplete hypercube with $k$ processors. Also, we give the exact values of $M_{IH,r}(k)$ for small values of $r$ and $k$ (see Sec. 4.3).

Consider a simple graph $G$ of order $n$ and size $m$ having Laplacian eigenvalues ${\mu }_1,{\mu }_2,\dots ,{\mu }_{n-1},{\mu }_n=0$. Let $S_k(G)={\sum }_{i=1}^k{\mu }_i$ be the sum of $k$ largest Laplacian eigenvalues of $G$. Brouwer conjectured that $S_k(G)\le m+\left(\genfrac{}{}{0ex}{}{k+1}{2}\right),$ for all $k=1,2,\dots ,n$. We obtain an upper bound for $S_k(G)$ in terms of the clique number $\omega$, the number of vertices $n$ and the non-negative integers $p\ge 0,r\ge 1$ associated to the structure of the graph $G$. We show that the Brouwer’s conjecture holds true for some new families of graphs. We use the same technique to prove that the Brouwer’s conjecture is true for a subclass of split graphs (It is already known that Brouwer’s conjecture holds for split graphs).