Discrete Mathematics, Algorithms and Applications

Let $X$ denote a set of non-negative integers and $\mathcal{𝒫}(X)$ be its power set. An integer additive set-labeling (IASL) of a graph $G$ is an injective set-valued function $f:V(G)\to \mathcal{𝒫}(X)-\{\varnothing \}$ such that the induced function $f^{+}:E(G)\to \mathcal{𝒫}(X)-\{\varnothing \}$ is defined by $f^{+}(uv)=f(u)+f(v);\forall uv\in E(G)$, where $f(u)+f(v)$ is the sumset of $f(u)$ and $f(v)$. An IASL of a signed graph $S$ is an IASL of its underlying graph $G$ together with the signature $\sigma$ defined by $\sigma (uv)={(-1)}^{|f^{+}(uv)|};\forall uv\in E(S)$. A marking of a signed graph is an injective map $\mu :V(S)\to \{+,-\}$, defined by $\mu (v)={(-1)}^{|f(v)|}$ for all $v\in V(S)$. Switching of signed graph is the process of changing the sign of the edges in $S$ whose end vertices have different signs. In this paper, we discuss certain characteristics of the switched signed graphs of certain types of integer additive set-labeled signed graphs.

This paper presents a general framework for the study of the relations between hypergraphs and hypergroups based on approximation operators. Indeed, by a given hypergraph $\mathrm{\Gamma }$, an equivalence relation $\rho$ on the set of vertices and using the notion of lower and upper approximations, we investigate two new hyperoperations on the set of vertices. In particular, by considering certain conditions on the equivalence relation $\rho$, we obtain two related $H_v$-groups and we prove some results in this respect.

A vertex $v$ of a graph $G=(V,E)$ is said to $ve$-dominate every edge incident to $v$, as well as every edge adjacent to these incident edges. A set $S\subseteq V$ is a vertex-edge dominating set (double vertex-edge dominating set, respectively) if every edge of $E$ is $ve$-dominated by at least one vertex (at least two vertices) of $S.$ The minimum cardinality of a vertex-edge dominating set (double vertex-edge dominating set, respectively) of $G$ is the vertex-edge domination number ${\gamma }_{ve}(G)$ (the double vertex-edge domination number ${\gamma }_{dve}(G)$, respectively). In this paper, we initiate the study of double vertex-edge domination. We first show that determining the number ${\gamma }_{dve}(G)$ for bipartite graphs is NP-complete. We also prove that for every nontrivial connected graphs $G,$ ${\gamma }_{dve}(G)\ge {\gamma }_{ve}(G)+1,$ and we characterize the trees $T$ with ${\gamma }_{dve}(T)={\gamma }_{ve}(T)+1$ or ${\gamma }_{dve}(T)={\gamma }_{ve}(T)+2.$ Finally, we provide two lower bounds on the double ve-domination number of trees and unicycle graphs in terms of the order $n,$ the number of leaves and support vertices, and we characterize the trees attaining the lower bound.

A distance compatible set labeling (dcsl) of a connected graph $G$ is an injective set assignment $f:V(G)\to 2^X,$ $X$ being a non-empty ground set, such that the corresponding induced function $f^{\oplus }:E(G)\to 2^X\setminus \{\varphi \}$ given by $f^{\oplus }(uv)=f(u)\oplus f(v)$ satisfies $|f^{\oplus }(uv)|=k_{(u,v)}^f{d}_G(u,v)$ for every pair of distinct vertices $u,v\in V(G),$ where $d_G(u,v)$ denotes the path distance between $u$ and $v$ and $k_{(u,v)}^f$ is a constant, not necessarily an integer, depending on the pair of vertices $u,v$ chosen. A dcsl $f$ of $G$ is $k$-uniform if all the constants of proportionality with respect to $f$ are equal to $k,$ and if $G$ admits such a dcsl then $G$ is called a $k$-uniform dcsl graph. The family ${ℱ}$ is well-graded family, if there is a tight path between any two of its distinct sets. A learning graph is an ${ℱ}$-induced graph of a learning space. In this paper, we initiate a study on subgraphs of 1-uniform graphs which lead to the study of Knowledge Structures, Learning Spaces and Union-closed conjecture using graph theory techniques.

The linear $2$-arboricity ${\mathrm{\text{la}}}_2(G)$ of a graph $G$ is the least integer $k$ such that $G$ can be partitioned into $k$ edge-disjoint forests, whose components are paths of length at most 2. In this paper, we study the linear $2$-arboricity of sparse graphs, and prove the following results: (1) let $G$ be a 2-degenerate graph, we have ${\mathrm{\text{la}}}_2(G)\le \lceil \frac{\mathrm{\Delta }(G)}{2}\rceil +2$; (2) if $\mathrm{\text{mad}}(G)<4$, then ${\mathrm{\text{la}}}_2(G)\le \lceil \frac{\mathrm{\Delta }(G)+1}{2}\rceil +4$; (3) if $\mathrm{\text{mad}}(G)<\frac{7}{2}$, then ${\mathrm{\text{la}}}_2(G)\le \lceil \frac{\mathrm{\Delta }(G)+1}{2}\rceil +3$; (4) if $\mathrm{\text{mad}}(G)<3$, then ${\mathrm{\text{la}}}_2(G)\le \lceil \frac{\mathrm{\Delta }(G)+1}{2}\rceil +3$; (5) if $\mathrm{\text{mad}}(G)<5$, then ${\mathrm{\text{la}}}_2(G)\le \lceil \frac{\mathrm{\Delta }(G)+1}{2}\rceil +10$.

Let $H$ be a connected $r$-uniform hypergraph. The unique positive eigenvector $x={(x_1,x_2,\dots ,x_n)}^{\mathrm{\text{T}}}$ with $\left|\right|x|{|}_r=1$ corresponding to spectral radius $\rho (H)$ is called the principal eigenvector of $H$. In this paper, we present some lower bounds for the spectral radius $\rho (H)$ and investigate the bounds of entries of the principal eigenvector of $H$.

In this paper, we study the non-commuting graph $\mathrm{\Gamma }(M_3^{\mathrm{\text{su}}}(C_n))$ of strictly upper triangular $3\times 3$ matrices over an $n$-element chain $C_n$. We prove that $\mathrm{\Gamma }(M_3^{\mathrm{\text{su}}}(C_n))$ is a compact graph. From $\mathrm{\Gamma }(M_3^{\mathrm{\text{su}}}(C_n))$, we construct a poset $P$. We further prove that $P\oplus 1$ is a dismantlable lattice and its zero-divisor graph is isomorphic to $\mathrm{\Gamma }(M_3^{\mathrm{\text{su}}}(C_n))$. Lastly, we prove that $\mathrm{\Gamma }(M_3^{\mathrm{\text{su}}}(C_n))$ is a perfect graph.

A total Roman dominating function (TRDF) on a graph $G$ is a function $f:V(G)\to \{0,1,2\}$ satisfying the conditions (i) every vertex $u$ for which $f(u)=0$ is adjacent at least one vertex $v$ for which $f(v)=2$ and (ii) the subgraph of $G$ induced by the set of all vertices of positive weight has no isolated vertex. The weight of a TRDF is the sum of its function values over all vertices. A total Roman dominating function $f$ is called a global total Roman dominating function (GTRDF) if $f$ is also a TRDF of the complement $\overline{G}$ of $G$. The global total Roman domination number of $G$ is the minimum weight of a GTRDF on $G$. In this paper, we initiate the study of global total Roman domination number and investigate its basic properties. In particular, we relate the global total Roman domination and the total Roman domination and the global Roman domination number.

Byte correcting perfect codes are developed to correct burst errors within bytes. If a code is byte correcting code and we say that the code is $b$-burst correcting, meaning that it corrects a single burst of length $b$ or less within a byte.

A byte correcting code is such that if $S_i(H)$; $S_i(H)=\{h_i:1\le i\le {\beta }_i\}$ denote the set of syndromes obtained from the $i$th-byte of the parity check matrix $H$ and $S_j(H)$; $S_j(H)=\{h_j:1\le j\le {\beta }_j\}$ denote the set of syndromes obtained from the $j$th-byte of the parity check matrix $H$ then $S_i(H)\cap S_j(H)=\varphi$.

In an $(n,k)$ code, if there are $m$ bytes of size $\beta$, then $n=m\beta$. Byte correcting codes are preferred where information stored in all bytes are equally important. But there are cases where some parts of the message are more important than other parts of the message, for example, if we have to transmit a message on a border location “ Shift Battalion (Bn) from Location A to Location B” then, we will focus more on the information shift, location $A$ and location $B$ i.e., bytes containing these information will be more important than others. In this situation, it is needed that during transmission these bytes should have no possibility of error. In other words, these bytes should be protected absolutely against any error. Keeping this in mind, we study burst error correcting capabilities of byte oriented codes in terms of byte protection level of each byte. If there is a byte error pattern of length $p$ in the transmission then all those bytes of the received pattern will be decoded correctly whose burst protection level is $p$ or more even though the code word may be decoded wrongly. Taking the code length $n$ to be divided into $m$ bytes with burst protection level of the $i$th-byte as $p_i$; $i=1,2,3,\dots ,m$; $p_1\ge p_2\ge p_3\ge \cdots \ge p_m$, we construct linear codes that we call byte protecting burst (BPB) codes and investigate their byte protecting capabilities in this paper.

A graph is called $H$-equicoverable if every minimal $H$-covering of it is also its minimum $H$-covering. In this paper, we consider how to characterize a graph to be $H$-equicoverable where $H$ is $P_4$. We obtained necessary and sufficient conditions for a graph contains a cycle with length greater than 3 but not contains any 3-cycles.

In this paper, we study the infinite graphs which admit a finite dominating set. The main contribution of the work is two folds: (i) characterization of infinite trees and hence infinite connected graphs with a finite dominating set, (ii) it is shown that apart from a family of graphs, all infinite graphs or their complements possess a finite dominating set. Moreover, some conditions of existence of finite dominating sets in product graphs are studied.

Coloring the vertices of a graph $G$ according to certain conditions is a random experiment and a discrete random variable $X$ is defined as the number of vertices having a particular color in the given type of coloring of $G$ and a probability mass function for this random variable can be defined accordingly. An equitable coloring of a graph $G$ is a proper coloring ${𝒞}$ of $G$ which an assignment of colors to the vertices of $G$ such that the numbers of vertices in any two color classes differ by at most one. In this paper, we extend the concepts of arithmetic mean and variance, the two major statistical parameters, to the theory of equitable graph coloring and hence determine the values of these parameters for a number of standard graphs.

We present in this paper a code for the class of unlabeled split–indifference graphs. This codification allows us to establish the exact number of elements of the class up to isomorphism. In order to obtain this result, structural properties of the class are explored, including a new approach for the characterization theorem.

We consider the maximum 1-2 matching problem in bipartite graphs. The notion of the augmenting trail for the 1-2 matching problem, which is the extension of the notion of the augmenting path for the 1-1 matching problem is introduced. The main purpose of the present paper is to prove “the augmenting trail theorem” for the 1-2 matching problem in the bipartite graph, which is an analogue of the augmenting path theorem by Bergé for the usual 1-1 matching problems.