ORIGINAL_ARTICLE
Roman game domination subdivision number of a graph
A Roman dominating function on a graph $G = (V,E)$ is a function $f : V\longrightarrow \{0, 1, 2\}$ satisfying the condition that every vertex $v$ for which $f (v) = 0$ is adjacent to at least one vertex $u$ for which $f (u) = 2$. The weight of a Roman dominating function is the value $w(f)=\sum_{v\in V}f(v)$. The Roman domination number of a graph $G$, denoted by $\gamma_R(G)$, equals the minimum weight of a Roman dominating function on G. The Roman game domination subdivision number of a graph $G$ is defined by the following game. Two players $\mathcal D$ and $\mathcal A$, $\mathcal D$ playing first, alternately mark or subdivide an edge of $G$ which is not yet marked nor subdivided. The game ends when all the edges of $G$ are marked or subdivided and results in a new graph $G'$. The purpose of $\mathcal D$ is to minimize the Roman domination number $\gamma_R(G')$ of $G'$ while $\mathcal A$ tries to maximize it. If both $\mathcal A$ and $\mathcal D$ play according to their optimal strategies, $\gamma_R(G')$ is well defined. We call this number the {\em Roman game domination subdivision number} of $G$ and denote it by $\gamma_{Rgs}(G)$. In this paper we initiate the study of the Roman game domination subdivision number of a graph and present sharp bounds on the Roman game domination subdivision number of a tree.
http://toc.ui.ac.ir/article_3341_b03cc8118595dcee034dcf7f43bede8d.pdf
2013-12-01T11:23:20
2017-12-11T11:23:20
1
12
10.22108/toc.2013.3341
Roman domination number
Roman game domination subdivision number
tree
Jafar
Amjadi
j-amjadi@azaruniv.edu
true
1
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
AUTHOR
Hossein
Karami
h.karami_math@yahoo.com
true
2
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
AUTHOR
Seyed Mahmoud
Sheikholeslami
s.m.sheikholeslami@azaruniv.edu
true
3
Azarbaijan University of Tarbiat Moallem
Azarbaijan University of Tarbiat Moallem
Azarbaijan University of Tarbiat Moallem
LEAD_AUTHOR
Lutz
Volkmann
volkm@math2.rwth-aachen.de
true
4
RWTH-Aachen University
RWTH-Aachen University
RWTH-Aachen University
AUTHOR
ORIGINAL_ARTICLE
Reciprocal degree distance of some graph operations
The reciprocal degree distance (RDD), defined for a connected graph $G$ as vertex-degree-weighted sum of the reciprocal distances, that is, $RDD(G) =\sum\limits_{u,v\in V(G)}\frac{d_G(u) + d_G(v)}{d_G(u,v)}.$ The reciprocal degree distance is a weight version of the Harary index, just as the degree distance is a weight version of the Wiener index. In this paper, we present exact formulae for the reciprocal degree distance of join, tensor product, strong product and wreath product of graphs in terms of other graph invariants including the degree distance, Harary index, the first Zagreb index and first Zagreb coindex. Finally, we apply some of our results to compute the reciprocal degree distance of fan graph, wheel graph, open fence and closed fence graphs.
http://toc.ui.ac.ir/article_3506_bfc02f2003611e70f89d3bbb16913cd1.pdf
2013-12-01T11:23:20
2017-12-11T11:23:20
13
24
10.22108/toc.2013.3506
Reciprocal degree distance
Harary index
Graph operations
Kannan
Pattabiraman
pramank@gmail.com
true
1
Annamalai University
Annamalai University
Annamalai University
LEAD_AUTHOR
M.
Vijayaragavan
mvragavan09@gmail.com
true
2
Thiruvalluvar College of Engineering and Technology
Thiruvalluvar College of Engineering and Technology
Thiruvalluvar College of Engineering and Technology
AUTHOR
ORIGINAL_ARTICLE
Graph theoretical methods to study controllability and leader selection for dead-time systems
In this article a graph theoretical approach is employed to study some specifications of dynamic systems with time delay in the inputs and states, such as structural controllability and observability. First, the zero and non-zero parameters of a proposed system have been determined, next the general structure of the system is presented by a graph which is constructed by non-zero parameters. The structural controllability and observability of the system is investigated using the corresponding graph. Our results are expressed for multi-agents systems with dead-time. As an application we find a minimum set of leaders to control a given multi-agent system.
http://toc.ui.ac.ir/article_3616_b2a99bce0bfaf49e3d546e59ee0937c0.pdf
2013-12-01T11:23:20
2017-12-11T11:23:20
25
36
10.22108/toc.2013.3616
Graph Methods
Dead-time Systems
Multi-agent systems
Structural Controllability
Majdeddin
Najafi
najafi_majd@yahoo.com
true
1
Avionics Research Institute
Avionics Research Institute
Avionics Research Institute
LEAD_AUTHOR
Farid
Shaikholeslam
sheikh@cc.iut.ac.ir
true
2
Electrical & Computer Engineering Department
Electrical & Computer Engineering Department
Electrical & Computer Engineering Department
AUTHOR
ORIGINAL_ARTICLE
Graphs cospectral with a friendship graph or its complement
Let $n$ be any positive integer and $F_n$ be the friendship (or Dutch windmill) graph with $2n+1$ vertices and $3n$ edges. Here we study graphs with the same adjacency spectrum as $F_n$. Two graphs are called cospectral if the eigenvalues multiset of their adjacency matrices are the same. Let $G$ be a graph cospectral with $F_n$. Here we prove that if $G$ has no cycle of length $4$ or $5$, then $G\cong F_n$. Moreover if $G$ is connected and planar then $G\cong F_n$. All but one of connected components of $G$ are isomorphic to $K_2$. The complement $\overline{F_n}$ of the friendship graph is determined by its adjacency eigenvalues, that is, if $\overline{F_n}$ is cospectral with a graph $H$, then $H\cong \overline{F_n}$.
http://toc.ui.ac.ir/article_3621_0bcd0f5df9a893e748683a0325f8cac6.pdf
2013-12-01T11:23:20
2017-12-11T11:23:20
37
52
10.22108/toc.2013.3621
Friendship graphs
cospectral graphs
adjacency eigenvalues
Alireza
Abdollahi
a.abdollahi@math.ui.ac.ir
true
1
University of Isfahan
University of Isfahan
University of Isfahan
LEAD_AUTHOR
Shahrooz
Janbaz
shahrooz.janbaz@sci.ui.ac.ir
true
2
University of Isfahan
University of Isfahan
University of Isfahan
AUTHOR
Mohammad Reza
Oboudi
mr.oboudi@sci.ui.ac.ir
true
3
University of Isfahan
University of Isfahan
University of Isfahan
AUTHOR
ORIGINAL_ARTICLE
Directionally $n$-signed graphs-III: the notion of symmetric balance
Let $G=(V, E)$ be a graph. By \emph{directional labeling (or d-labeling)} of an edge $x=uv$ of $G$ by an ordered $n$-tuple $(a_1,a_2,\dots,a_n)$, we mean a labeling of the edge $x$ such that we consider the label on $uv$ as $(a_1,a_2,\dots,a_n)$ in the direction from $u$ to $v$, and the label on $x$ as $(a_{n},a_{n-1},\dots,a_1)$ in the direction from $v$ to $u$. In this paper, we study graphs, called \emph{(n,d)-sigraphs}, in which every edge is $d$-labeled by an $n$-tuple $(a_1,a_2,\dots,a_n)$, where $a_k \in \{+,-\}$, for $1\leq k \leq n$. In this paper, we give different notion of balance: symmetric balance in a $(n,d)$-sigraph and obtain some characterizations.
http://toc.ui.ac.ir/article_3658_afa2e9837ed9f7e3782ebee733da0db9.pdf
2013-12-01T11:23:20
2017-12-11T11:23:20
53
62
10.22108/toc.2013.3658
Signed graphs
Directional labeling
Complementation
Balance
P.Siva Kota
Reddy
reddy_math@yahoo.com
true
1
Dept. of Mathematics, Siddaganga Institute of Technology, B.H.Road,Tumkur-572103, India.
Dept. of Mathematics, Siddaganga Institute of Technology, B.H.Road,Tumkur-572103, India.
Dept. of Mathematics, Siddaganga Institute of Technology, B.H.Road,Tumkur-572103, India.
LEAD_AUTHOR
U. K.
Misra
true
2
Berhampur University
Berhampur University
Berhampur University
AUTHOR
ORIGINAL_ARTICLE
Full friendly index sets of slender and flat cylinder graphs
Let $G=(V,E)$ be a connected simple graph. A labeling $f:V \to Z_2$ induces an edge labeling $f^*:E \to Z_2$ defined by $f^*(xy)=f(x)+f(y)$ for each $xy \in E$. For $i \in Z_2$, let $v_f(i)=|f^{-1}(i)|$ and $e_f(i)=|f^{*-1}(i)|$. A labeling $f$ is called friendly if $|v_f(1)-v_f(0)|\le 1$. The full friendly index set of $G$ consists all possible differences between the number of edges labeled by 1 and the number of edges labeled by 0. In recent years, full friendly index sets for certain graphs were studied, such as tori, grids $P_2\times P_n$, and cylinders $C_m\times P_n$ for some $n$ and $m$. In this paper we study the full friendly index sets of cylinder graphs $C_m\times P_2$ for $m\geq 3$, $C_m\times P_3$ for $m\geq 4$ and $C_3\times P_n$ for $n\geq 4$. The results in this paper complement the existing results in literature, so the full friendly index set of cylinder graphs are completely determined.
http://toc.ui.ac.ir/article_3678_3225bdc21d140f967414ef14f7247734.pdf
2013-12-01T11:23:20
2017-12-11T11:23:20
63
80
10.22108/toc.2013.3678
Full friendly index sets
friendly labeling
cylinder graphs
Wai Chee
Shiu
wcshiu@hkbu.edu.hk
true
1
Hong Kong Baptist University
Hong Kong Baptist University
Hong Kong Baptist University
LEAD_AUTHOR
Man-Ho
Ho
homanho@hkbu.edu.hk
true
2
Hong Kong Baptist University
Hong Kong Baptist University
Hong Kong Baptist University
AUTHOR