Unicyclic graphs with strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers
J.
Amjadi
Azarbaijan Shahid Madani University
author
M.
Chellali
University of Blida LAMDA-RO Laboratory
author
M.
Falahat
Azarbaijan Shahid Madani University
author
S. M.
Sheikholeslami
Azarbaijan Shahid Madani University
author
text
article
2015
eng
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 $v\in V$ with $f(v)=\emptyset$ the condition $\bigcup_{u\in N(v)}f(u)=\{1,2\}$ is fulfilled. A 2RDF $f$ is independent (I2RDF) if no two vertices assigned nonempty sets are adjacent. The weight of a 2RDF $f$ is the value $\omega(f)=\sum_{v\in V}|f (v)|$. The 2-\emph{rainbow domination number} $\gamma_{r2}(G)$ (respectively, the 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)$.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
2
no.
2015
1
11
http://toc.ui.ac.ir/article_6518_70bb50bdb82bf7fe7c4d75610adbf9cd.pdf
dx.doi.org/10.22108/toc.2015.6518
Skew-spectra and skew energy of various products of graphs
Xueliang
Li
Center for Combinatorics and LPMC-TJKLC,
Nankai University
author
Huishu
Lian
College of Science,
China University of Mining and Technology
author
text
article
2015
eng
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 $H\otimes G$ and the strong product $H\ast 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$.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
2
no.
2015
13
21
http://toc.ui.ac.ir/article_6417_49554edbea5b1672fe3293c44812de6d.pdf
dx.doi.org/10.22108/toc.2015.6417
The second immanant of some combinatorial matrices
R. B.
Bapat
Stat-Math Unit, ISI Delhi
author
Sivaramakrishnan
Sivasubramanian
Dept of Mathematics, IIT Bombay
author
text
article
2015
eng
Let $A = (a_{i,j})_{1 \leq i,j \leq n}$ be an $n \times n$ matrix where $n \geq 2$. Let $\det 2(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 give an explicit formula for $\det 2(ED_G)$ which shows that $\det 2(ED_G)$ is independent of the manner in which $G$'s 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 dependent on 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.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
2
no.
2015
23
35
http://toc.ui.ac.ir/article_6237_0e3b4c61593d783ddddf34dff3214698.pdf
dx.doi.org/10.22108/toc.2015.6237
A typical graph structure of a ring
R.
Kala
Manonmaniam Sundaranar University
author
S.
Kavitha
Manonmaniam Sundaranar University
author
text
article
2015
eng
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 $\mathcal{Z}_N(R)^*$, and two vertices $x$ and $y$ are adjacent if and only if $xy$ is nilpotent and $xy\neq 0$, where $\mathcal{Z}_N(R)=\{x\in R: xy~\text{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)$.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
2
no.
2015
37
44
http://toc.ui.ac.ir/article_6177_95c66f3ddffbab1d427f14e4b0d0e823.pdf
dx.doi.org/10.22108/toc.2015.6177
Linear codes on solid bursts and random errors
Pankaj
Das
Shivaji College (University of Delhi)
author
text
article
2015
eng
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.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
2
no.
2015
45
55
http://toc.ui.ac.ir/article_6189_9619dd1f0360d22b7a321782e90bd715.pdf
dx.doi.org/10.22108/toc.2015.6189
Total dominator chromatic number of a graph
Adel
P. Kazemi
UMA
(University of Mohaghegh Ardabili)
author
text
article
2015
eng
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.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
2
no.
2015
57
68
http://toc.ui.ac.ir/article_6171_9ef54a03e9ce8be1ddbac6d68cda24c0.pdf
dx.doi.org/10.22108/toc.2015.6171