Restrained roman domination in graphs
Roushini
Pushpam
Department of Mathematics
D.B.Jain College,
Chennai 97
India
author
Sampath
Padmapriea
Department of Mathematics
Sri Sairam Engineering College
Chennai 44
India
author
text
article
2015
eng
A \textit{Roman dominating function} (RDF) on a graph $G = (V,E)$ is defined to be a function $ f:V \rightarrow \lbrace 0,1,2\rbrace$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v)=2$. A set $S \subseteq V$ is a \textit{Restrained dominating set} if every vertex not in $S$ is adjacent to a vertex in $S$ and to a vertex in $V - S$. We define a \textit{Restrained Roman dominating function} on a graph $G = (V,E)$ to be a function $f : V \rightarrow \lbrace 0,1,2 \rbrace$ satisfying the condition that every vertex $u$ for which $f(u) = 0 $ is adjacent to at least one vertex $v$ for which $f(v)=2$ and at least one vertex $w$ for which $f(w) = 0$. The \textit{weight} of a Restrained Roman dominating function is the value $f(V)= \sum _{u \in V} f(u)$. The minimum weight of a Restrained Roman dominating function on a graph $G$ is called the Restrained Roman domination number of $G$ and denoted by $\gamma_{rR}(G)$. In this paper, we initiate a study of this parameter.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
1
no.
2015
1
17
http://toc.ui.ac.ir/article_4395_4464d5648abc97e1c5cf12df1d49d67c.pdf
dx.doi.org/10.22108/toc.2015.4395
Optimal orientations of subgraphs of complete bipartite graphs
R.
Lakshmi
Assistant Professor
Department of mathematics
Annamalai University
Annamalainagar 608002
author
G.
Rajasekaran
Research Scholar,
Department of Mathematics,
Annamalai University,
Annamalainagar 608 002
author
R.
Sampathkumar
Mathematics Section,
FEAT, Annamalai University
Annamalainagar 6008002
author
text
article
2015
eng
For a graph $G,$ let $\mathscr{D}(G)$ be the set of all strong digraphs $D$ obtained by the orientations of $G.$ The orientation number of $G$ is $\stackrel{\rightarrow}{d}\!\!(G)\,=$ min $\{d(D)\,|\,D\,\in\,\mathscr{D}(G)\},$ where $d(D)$ denotes the diameter of the digraph $D.$ In this paper, we determine the orientation number for some subgraphs of complete bipartite graphs.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
1
no.
2015
19
29
http://toc.ui.ac.ir/article_4725_ab6061f1b408a4d9a9b58cff4bb6771c.pdf
dx.doi.org/10.22108/toc.2015.4725
A bound for the locating chromatic number of trees
Ali
Behtoei
Imam Khomeini International University
author
Mahdi
Anbarloei
Imam Khomeini International University
author
text
article
2015
eng
Let $f$ be a proper $k$-coloring of a connected graph $G$ and $\Pi=(V_1,V_2,\ldots,V_k)$ be an ordered partition of $V(G)$ into the resulting color classes. For a vertex $v$ of $G$, the color code of $v$ with respect to $\Pi$ is defined to be the ordered $k$-tuple $c_{{}_\Pi}(v)=(d(v,V_1),d(v,V_2),\ldots,d(v,V_k)),$ where $d(v,V_i)=\min\{d(v,x):~x\in V_i\}, 1\leq i\leq k$. If distinct vertices have distinct color codes, then $f$ is called a locating coloring. The minimum number of colors needed in a locating coloring of $G$ is the locating chromatic number of $G$, denoted by $\chi_{L}(G)$. In this paper, we study the locating chromatic numbers of trees. We provide a counter example to a theorem of Gary Chartrand et al. [G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, P. Zhang, The locating-chromatic number of a graph, Bull. Inst. Combin. Appl., 36 (2002) 89-101] about the locating chromatic number of trees. Also, we offer a new bound for the locating chromatic number of trees. Then, by constructing a special family of trees, we show that this bound is best possible.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
1
no.
2015
31
41
http://toc.ui.ac.ir/article_6024_1de06593073b82da914fe9c02657202d.pdf
dx.doi.org/10.22108/toc.2015.6024
Graphs with fixed number of pendent vertices and minimal first Zagreb index
Ivan
Gutman
University of Kragujevac
Kragujevac, Serbia
author
Muhammad
Jamil
Government College University
author
Naveed
Akhter
Government College University
author
text
article
2015
eng
The first Zagreb index $M_1$ of a graph $G$ is equal to the sum of squares of degrees of the vertices of $G$. Goubko proved that for trees with $n_1$ pendent vertices, $M_1 \geq 9\,n_1-16$. We show how this result can be extended to hold for any connected graph with cyclomatic number $\gamma \geq 0$. In addition, graphs with $n$ vertices, $n_1$ pendent vertices, cyclomatic number $\gamma$, and minimal $M_1$ are characterized. Explicit expressions for minimal $M_1$ are given for $\gamma=0,1,2$, which directly can be extended for $\gamma>2$.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
1
no.
2015
43
48
http://toc.ui.ac.ir/article_6029_3088c8b600fd6edb7a3e85ff1dd901d2.pdf
dx.doi.org/10.22108/toc.2015.6029
$k$-odd mean labeling of prism
B.
Gayathri
Periyar E.V.R. College(Autonomous)
author
K.
Amuthavalli
Roever Engineering College
author
text
article
2015
eng
A $(p,q)$ graph $G$ is said to have a $k$-odd mean labeling $(k \ge 1)$ if there exists an injection $f : V \to \{0, 1, 2, \ldots, 2k + 2q - 3\}$ such that the induced map $f^*$ defined on $E$ by $f^*(uv) = \left\lceil \frac{f(u)+f(v)}{2}\right\rceil$ is a bijection from $E$ to $\{2k - 1, 2k + 1, 2k + 3, \ldots, 2 k + 2q - 3\}$. A graph that admits $k$-odd mean labeling is called $k$-odd mean graph. In this paper, we investigate $k$-odd mean labeling of prism $C_m \times P_n$.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
1
no.
2015
49
56
http://toc.ui.ac.ir/article_5388_c3d1298da0efeb3c0c28f5a89756531d.pdf
dx.doi.org/10.22108/toc.2015.5388
Note on the skew energy of oriented graphs
Jun
He
School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu, Sichuan, 611731, PR China
author
Ting-Zhu
Huang
School of Mathematical Sciences,
University of Electronic Science and Technology of China,
Chengdu, Sichuan, 611731, P.R. China
author
text
article
2015
eng
The skew energy of oriented graphs is defined as the sum of the norms of all the eigenvalues of the skew adjacency matrix. In this note, we obtain some upper bounds for the skew energy of any oriented graphs, which improve the known upper bound obtained by Adiga et al.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
1
no.
2015
57
61
http://toc.ui.ac.ir/article_6117_67b546232db1fead989a7b5928ccfacc.pdf
dx.doi.org/10.22108/toc.2015.6117