Transactions on Combinatorics
Volume:4 Issue: 2, Jun 2015

A 2-emph{rainbow dominating function} (2RDF) on a graph $G=(V, E)$ is a function $f$ from the vertex set $V$ to the set of all subsets of the set ${1,2}$ such that for any vertex $vin V$ with $f(v)=emptyset$ the condition $bigcup_{uin N(v)}f(u)={1,2}$ is fulfilled. A 2RDF $f$ is independent (I2RDF) if no two vertices assigned nonempty sets are adjacent. The emph{weight} of a 2RDF $f$ is the value $omega(f)=sum_{vin V}|f (v)|$. The 2-emph{rainbow domination number} $gamma_{r2}(G)$ (respectively, the emph{independent $2$-rainbow domination number} $i_{r2}(G)$) is the minimum weight of a 2RDF (respectively, I2RDF) on $G$. We say that $gamma_{r2}(G)$ is strongly equal to $i_{r2}(G)$ and denote by $gamma_{r2}(G)equiv i_{r2}(G)$, if every 2RDF on $G$ of minimum weight is an I2RDF. In this paper we characterize all unicyclic graphs $G$ with $gamma_{r2}(G)equiv i_{r2}(G)$.

Given a graph $G$, let $G^sigma$ be an oriented graph of $G$ with the orientation $sigma$ and skew-adjacency matrix $S(G^sigma)$. Then the spectrum of $S(G^sigma)$ consisting of all the eigenvalues of $S(G^sigma)$ is called the skew-spectrum of $G^sigma$, denoted by $Sp(G^sigma)$. The skew energy of the oriented graph $G^sigma$, denoted by $mathcal{E}_S(G^sigma)$, is defined as the sum of the norms of all the eigenvalues of $S(G^sigma)$. In this paper, we give orientations of the Kronecker product $Hotimes G$ and the strong product $Hast G$ of $H$ and $G$ where $H$ is a bipartite graph and $G$ is an arbitrary graph. Then we determine the skew-spectra of the resultant oriented graphs. As applications, we construct new families of oriented graphs with optimum skew energy. Moreover, we consider the skew energy of the orientation of the lexicographic product $H[G]$ of a bipartite graph $H$ and a graph $G$.

Let $A = (a_{i,j})_{1 leq i,j leq n}$ be an $n times n$ matrix where $n geq 2$. Let $dt(A)$, its second immanant be the immanant corresponding to the partition $lambda_2 = 2,1^{n-2}$. Let $G$ be a connected graph with blocks $B_1, B_2, ldots B_p$ and with $q$-exponential distance matrix $ED_G$. We given an explicit formula for $dt(ED_G)$ which shows that $dt(ED_G)$ is independent of the manner in which the blocks are connected. Our result is similar in form to the result of Graham, Hoffman and Hosoya and in spirit to that of Bapat, Lal and Pati who show that $det ED_T$ where $T$ is a tree is independent of the structure of $T$ and only its number of vertices. Our result extends more generally to a product distance matrix associated to a connected graph $G$. Similar results are shown for the $q$-analogue of $T$''s laplacian and a suitably defined matrix for arbitrary connected graphs.

The zero-divisor graph of a commutative ring R with respect to nilpotent elements is a simple undirected graph $Gamma_N^*(R)$ with vertex set Z_N(R)*, and two vertices x and y are adjacent if and only if xy is nilpotent and xy is nonzero, where Z_N(R)={x in R: xy is nilpotent, for some y in R^*}. In this paper, we investigate the basic properties of $Gamma_N^*(R)$. We discuss when it will be Eulerian and Hamiltonian. We further determine the genus of $Gamma_N^*(R)$.

The paper presents lower and upper bounds on the number of parity check digits required for a linear code that detects solid bursts of length $b$ or less and simultaneously any $e$ or less random errors. An example of such a code is also provided. Further, codes capable of detecting and simultaneously correcting such errors have also been dealt with.

Given a graph $G$, the total dominator coloring problem seeks a proper coloring of $G$ with the additional property that every vertex in the graph is adjacent to all vertices of a color class. We seek to minimize the number of color classes. We initiate to study this problem on several classes of graphs, as well as finding general bounds and characterizations. We also compare the total dominator chromatic number of a graph with the chromatic number and the total domination number of it.