2013
2
4
4
80
Roman game domination subdivision number of a graph
2
2
A Roman dominating function on a graph $G = (V,E)$ is a function $f : Vlongrightarrow {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_{vin 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.
1

1
12


Jafar
Amjadi
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
Iran
jamjadi@azaruniv.edu


Hossein
Karami
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
Iran
h.karami_math@yahoo.com


Seyed Mahmoud
Sheikholeslami
Azarbaijan University of Tarbiat Moallem
Azarbaijan University of Tarbiat Moallem
Iran
s.m.sheikholeslami@azaruniv.edu


Lutz
Volkmann
RWTHAachen University
RWTHAachen University
Germany
volkm@math2.rwthaachen.de
Roman domination number
Roman game domination subdivision number
tree
[M. Atapour, A. Khodkar and S. M. Sheikholeslami (2010). Trees
whose Roman domination subdivision number is 2. Util. Math.. 82, 227240## E. W. Chambers, B. Kinnersley, N. Prince and D. B. West (2009). Extremal
problems for Roman domination. SIAM J. Discrete Math.. 23, 15751586## E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi and S. T. Hedetniemi (2004). Roman domination in graphs. Discrete Math.. 278, 1122## E. J. Cockayne, P. J. P. Grobler, W. R. Gr"{u}ndlingh, J. Munganga and J. H. van Vuuren (2005). Protection of a graph. Util. Math.. 67, 1932## O. Favaron, H. Karami and S. M. Sheikholeslami Game
domination subdivision number of a graph. J. Comb. Optim., (to appear). ## O. Favaron, H. Karami and S. M. Sheikholeslami (2009). On the Roman
domination number in graphs. Discrete Math.. 309, 34473451## T. W. Haynes, S. T. Hedetniemi and P. J. Slater (1998). Fundamentals of Domination in graphs. Marcel Dekker, Inc.,
New York. ## M. A. Henning (2002). A characterization of Roman trees. Discuss. Math.
Graph Theory. 22, 325334## N. Jafari Rad and L. Volkmann (2011). Roman domination perfect graphs. An. Stiint. Univ. Ovidius Constanta Ser. Mat.. 19, 167174## C. S. ReVelle and K. E. Rosing (2000). Defendens imperium romanum: a
classical problem in military strategy. Amer. Math. Monthly. 107, 585594## I. Stewart (1999). Defend the roman empire. Sci. Amer.. 281 (6) , 136139## L. Volkmann (2008). A characterization of bipartite graphs with independence number
half their order. Australas. J. Combin.. 41, 219222## D. B. West (2000). Introduction to Graph Theory. PrenticeHall, Inc.. ## ]
Reciprocal degree distance of some graph operations
2
2
The reciprocal degree distance (RDD), defined for a connected graph $G$ as vertexdegreeweighted sum of the reciprocal distances, that is, $RDD(G) =sumlimits_{u,vin 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.
1

13
24


Kannan
Pattabiraman
Annamalai University
Annamalai University
India
pramank@gmail.com


M.
Vijayaragavan
Thiruvalluvar College of Engineering and Technology
Thiruvalluvar College of Engineering and
India
mvragavan09@gmail.com
Reciprocal degree distance
Harary index
Graph operations
[N. Alon and E. Lubetzky (2007). Independent set in tensor graph powers. J. Graph Theory. 54, 7387## A. M. Assaf (1990). Modified group divisible designs. Ars Combin.. 29, 1320## B. Bresar, W. Imrich, S. Klavv{z}ar and B. Zmazek (2005). Hypercubes as direct products. SIAM J. Discrete Math.. 18, 778786## K. C. Das, B. Zhou and N. Trinajsti'c (2009). Bounds on Harary index. J. Math. Chem.. 46, 13771393## A. A. Dobrynin and A. A. Kochetova (1994). Degree distance of a graph: a degree analogue of the Wiener index. J. Chem. Inf. Comput. Sci.. 34, 10821086## J. Devillers, A. T. Balaban and Eds. (1999). Topological indices and related descriptors in QSAR and QSPR. Gordon and Breach, Amsterdam, The Netherlands. ## L. Feng and A. Ilic (2010). Zagreb, Harary and hyperWiener indices of graphs with a given matching number. Appl. Math. Lett.. 23, 943948## I. Gutman (1994). Selected properties of the Schultz molecular topological index. J. Chem. Inf. Comput. Sci.. 34, 10871089## I. Gutman and O. E. Polansky (1986). Mathematical Concepts in Organic Chemistry. SpringerVerlag, Berlin. ## M. Hoji, Z. Luo and E. Vumar (2010). Wiener and vertex PI indices of kronecker products of graphs. Discrete Appl. Math.. 158, 18481855## H. Hua and S. Zhang (2012). On the reciprocal degree distance of graphs. Discrete Appl. Math.. 160, 11521163## W. Imrich and S. Klavzar (2000). Product graphs: Structure and Recognition. John Wiley, New York. ## O. Ivanciuc and T. S. Balaban (1993). Reciprocal distance matrix, related local vertex invariants and topological indices. J. Math. Chem.. 12, 309318## M. H. Khalifeh, H. YouseriAzari and A. R. Ashrafi (2008). Vertex and edge PI indices of Cartesian product of graphs. Discrete Appl. Math.. 156, 17801789## B. Lucic, A. Milicevic, S. Nikolic and N. Trinajstic (2002). Harary indextwelve years later. Croat. Chem. Acta. 75, 847868## A. Mamut and E. Vumar (2008). Vertex vulnerability parameters of Kronecker products of complete graphs. Inform. Process. Lett.. 106, 258262## K. Pattabiraman and P. Paulraja (2012). On some topological indices of the tensor product of graphs. Discrete Appl. Math.. 160, 267279## K. Pattabiraman and P. Paulraja (2012). Wiener and vertex PI indices of the strong product of graphs. Discuss. Math. Graph Thoery. 32, 749769## K. Pattabiraman and P. Paulraja (2011). Wiener index of the tensor product of a path and a cycle. Discuss. Math. Graph Thoery. 31, 737751## D. Plavsic, S. Nikolic, N. Trinajstic and Z. Mihalic (1993). On the Harary index for the characterization of chemical graphs. J. Math. Chem.. 12, 235250## K. Xu and K. C. Das (2011). On Harary index of graphs. Discrete. Appl. Math.. 159, 16311640## H. YousefiAzari, M. H. Khalifeh and A. R. Ashrafi (2011). Calculating the edge Wiener and edge Szeged indices of graphs. J. Comput. Appl. Math.. 235, 48664870## B. Zhou, Z. Du and N. Trinajstic (2008). Harary index of landscape graphs. Int. J. Chem. Model.. 1, 3544## B. Zhou, X. Cai and N. Trinajstic (2008). On the Harary index. J. Math. Chem.. 44, 611618## ]
Graph theoretical methods to study controllability and leader selection for deadtime systems
2
2
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 nonzero parameters of a proposed system have been determined, next the general structure of the system is presented by a graph which is constructed by nonzero parameters. The structural controllability and observability of the system is investigated using the corresponding graph. Our results are expressed for multiagents systems with deadtime. As an application we find a minimum set of leaders to control a given multiagent system.
1

25
36


Majdeddin
Najafi
Avionics Research Institute
Avionics Research Institute
Iran
najafi_majd@yahoo.com


Farid
Shaikholeslam
Electrical & Computer Engineering Department
Electrical & Computer Engineering Department
Iran
sheikh@cc.iut.ac.ir
Graph Methods
Deadtime Systems
MultiAgent Systems
Structural Controllability
[A. Rahmani, M. Ji, M. Mesbahi and M. Egerstedt (2009). Controllability of multiagent systems from a graphtheoretic perspective. SIAM J. Control Optim.. 48 (1) , 162186## R. OlfatiSaber and R. M. Murray (2004). Consensus problems in networks of agents with switching topology and timedelays. IEEE Trans. Automat. Control. 49 (9) , 15201533## Y. G. Sun, L. Wang and G. Xie (2008). Average consensus in networks of dynamic agents with switching topologies and multiple timevarying delays. Systems Control Lett.. 57 (2) , 175183## F. Xiao and L. Wang (2008). Asynchronous consensus in continuoustime multiagent systems with switching topology and timevarying delays. IEEE Trans. Automat. Control. 53 (8) , 18041816## J. Qin, H. Gao and W. X. Zheng (2011). Secondorder consensus for multiagent systems with switching topology and communication delay. Systems Control Lett.. 60 (6) , 390397## R. Ghabcheloo, A. P. Aguiar, A. Pascoal, C. Silvestre, I. Kaminer and J. Hespanha (2009). Coordinated pathfollowing in the presence of communication losses and time delays. SIAM J. Control Optim.. 48 (1) , 234265## J. Guo, Z. Lin, M. Cao and H. Yan (2010). Adaptive control schemes for mobile robot formations with triangularised structures. Control Theory & Applications, IET. 4 (9) , 18171827## B. Yun, B. M. Chen, K. Y. Lum and T. H. Lee A leaderfollower formation flight control scheme for UAV helicopters. Proceeding of Automation and Logistics, ICAL 2008. IEEE International Conference on. , 3944## S. Khosravi, M. Jahangir and H. Afkhami (2012). Adaptive fuzzy SMCbased formation design for swarm of unknown timedelayed robots. Nonlinear Dynam.. 69 (4) , 18251835## M. Mesbahi and F. Y. Hadaegh (2001). Formation flying control of multiple spacecraft via graphs, matrix inequalities, and switching. Journal of Guidance, Control, and Dynamics. 24 (2) , 369377## C. P. Fall (2002). Computational cell biology. SpringerVerlag, New York. 20## Y. Y. Liu, J. J. Slotine and A. L. Barabasi (2011). Controllability of complex networks. Nature. 473 (7346) , 167173## J. M. Dion, C. Commault and J. Van Der Woude (2003). Generic properties and control of linear structured systems: a survey. Automatica J. IFAC. 39 (7) , 11251144## Z. Ji, Zi. Wang, H. Lin and Zh. Wang (2010). Controllability of multiagent systems with timedelay in state and switching topology. Internat. J. Control. 83 (2) , 371386## D. Cvetkovic, P. Rowlinson, Z. Stanic and M. G. Yoon (2011). Controllable graphs. Bull. Cl. Sci. Math. Nat. Sci. Math.. 143 (36) , 8188## S. Jafari, A. Ajorlou and A. G. Aghdam (2011). Leader selection in multiagent systems subject to partial failure. Proceeding of American Control Conference (ACC). , 53305335## A. Clark, L. Bushnell and R. Poovendran (2012). On leader selection for performance and controllability in multiagent systems. Proceeding of Decision and Control (CDC), IEEE 51st Annual Conference on. , 8693## M. A. Rahimian and A. G. Aghdam (2013). Structural controllability of multiagent networks: Robustness against simultaneous failures. Automatica, In press. ## M. Ji, A. Muhammad and M. Egerstedt (2006). Leaderbased multiagent coordination: Controllability and optimal control. Proceeding of American Control Conference. , 612## C. T. Chen (1998). Linear system theory and design. Oxford University Press, Inc.. ## ]
Graphs cospectral with a friendship graph or its complement
2
2
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 $Gcong F_n$. Moreover if $G$ is connected and planar then $Gcong 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 $Hcong overline{F_n}$.
1

37
52


Alireza
Abdollahi
University of Isfahan
University of Isfahan
Iran
a.abdollahi@math.ui.ac.ir


Shahrooz
Janbaz
University of Isfahan
University of Isfahan
Iran
shahrooz.janbaz@sci.ui.ac.ir


Mohammad Reza
Oboudi
University of Isfahan
University of Isfahan
Iran
mr.oboudi@sci.ui.ac.ir
Friendship graphs
cospectral graphs
adjacency eigenvalues
Directionally $n$signed graphsIII: the notion of symmetric balance
2
2
Let $G=(V, E)$ be a graph. By emph{directional labeling (or dlabeling)} 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_{n1},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 $1leq k leq n$. In this paper, we give different notion of balance: symmetric balance in a $(n,d)$sigraph and obtain some characterizations.
1

53
62


P.Siva Kota
Reddy
Dept. of Mathematics, Siddaganga Institute of Technology, B.H.Road,Tumkur572103, India.
Dept. of Mathematics, Siddaganga Institute
India
reddy_math@yahoo.com


U. K.
Misra
Berhampur University
Berhampur University
Iran
Signed graphs
Directional labeling
Complementation
Balance
[B. D. Acharya and M. Acharya (1986). New algebraic models of a social system. Indian J. of Pure and Appl. Math.. 17 (2) , 152168## J. Edmonds and E. L. Johnson (1970). Matching: a wellsolved class of integral linear programs. in:
Richard Guy et al., eds., Combinatorial Structures and Their Applications (Proc. Calgary Int. Conf., Calgary, 1969), Gordon and Breach, New York. ## F. Harary (1969). Graph Theory. AddisonWesley Publishing Co.. , 8992## F. Harary (195354). On the notion of balance of a signed graph. Michigan Math. J.. 2, 143146## F. Harary (1955). On local balance and $N$balance in signed graphs. Michigan Math. J.. 3, 3741## F. Harary, R. Norman and D. Cartwright (1965). Structural models: An introduction to the theory of directed graphs. Jon Wiley, New York. ## R. Rangarajan, M. S. Subramanya and P. Siva Kota Reddy (2010). The Hline signed graph of a signed graph. International J.
Math. Combin.. 2, 3743## R. Rangarajan and P. Siva Kota Reddy (2010). The edge C_4 signed graph of a signed graph. Southeast Asian
Bulletin of Mathematics. 34 (6) , 10771082## R. Rangarajan, M. S. Subramanya and P. Siva Kota Reddy (2012). Neighborhood signed graphs. Southeast
Asian Bulletin of Mathematics. 36 (3) , 389397## E. Sampathkumar, P. Siva Kota Reddy and M. S. Subramanya (2008). (3,d)sigraph and its applications. Advn. Stud. Contemp. Math.. 17 (1) , 5767## E. Sampathkumar, P. Siva Kota Reddy and M. S.
Subramanya (2010). (4,d)sigraph and its applications. Advn. Stud. Contemp. Math.. 20 (1) , 115124## E. Sampathkumar, P. Siva Kota Reddy, and M. S. Subramanya (2010). Directionally $n$signed
graphs, in: B.D. Acharya et al., eds.. Advances in Discrete Mathematics and Applications:
Mysore, 2008 (Proc. Int. Conf. Discrete Math., ICDM2008), Ramanujan, Ramanujan,
Math. Soc. Lect. Notes Ser., Ramanujan Mathematical Society, Mysore, India. 13, 153160## E. Sampathkumar, P. Siva Kota Reddy, and M. S. Subramanya (2009). Directionally $n$signed
graphsII. Int. J. Math. Combin.. 4, 8998## P. Siva Kota Reddy and M. S. Subramanya (2009). Signed graph equation L^k(S) sim overline{S}. International J.
Math. Combin.. 4, 8488## P. Siva Kota Reddy, S. Vijay and V. Lokesha (2009). n^{th} Power signed graphs. Proceedings of the Jangjeon
Math. Soc.. 12 (3) , 307313## P. Siva Kota Reddy, S. Vijay and H. C. Savithri (2010). A note on path sidigraphs. International J.
Math. Combin.. 1, 4246## P. Siva Kota Reddy, S. Vijay and V. Lokesha (2010). n^{th} Power signed graphsII. International J.
Math. Combin.. 1, 7479## P. Siva Kota Reddy and S. Vijay (2010). Total minimal dominating signed
graph. International J. Math. Combin.. 3, 1116## P. Siva Kota Reddy and K. V. Madhusudhan (2010). Negation switching equivalence in signed graphs. International J. Math. Combin.. 3, 8590## P. Siva Kota Reddy (2010). tPath sigraphs. Tamsui Oxford
J. of Math. Sciences. 26 (4) , 433441## P. Siva Kota Reddy, E. Sampathkumar and M. S. Subramanya (2010). Commonedge signed graph of a signed
graph. J. Indones. Math. Soc.. 16 (2) , 105112## P. Siva Kota Reddy, B. Prashanth and Kavita. S. Permi (2011). A note on antipodal signed graphs. International J. Math. Combin.. 1, 107112## P. Siva Kota Reddy and B. Prashanth (2012). The common minimal dominating signed graph. Trans. Comb.. 1 (3) , 3946## P. Siva Kota Reddy and B. Prashanth (2012). mathcal{S}Antipodal signed graphs. Tamsui Oxf. J. Inf. Math. Sci.. 28 (2) , 165174## P. Siva Kota Reddy, B. Prashanth, and T. R. Vasanth Kumar (2011). Antipodal
signed directed graphs. Advn. Stud. Contemp. Math.. 21 (4) , 355360## P. Siva Kota Reddy and U. K. Misra (2012). Common minimal equitable dominating signed graphs. Notes on Number Theory and Discrete Mathematics. 18 (4) , 4046## P. Siva Kota Reddy and S. Vijay (2012). The super line signed graph $mathcal{L}_r(S)$ of a signed graph. Southeast Asian Bulletin of Mathematics. 36 (6) , 875882## P. Siva Kota Reddy, K. R. Rajanna and Kavita S Permi (2013). The common minimal common neighborhood dominating signed
graphs. Trans. Comb.. 2 (1) , 18## P. Siva Kota Reddy and U. K. Misra (2013). The equitable associate signed graphs. Bull. Int. Math. Virtual Inst.. 3 (1) , 1520## P. Siva Kota Reddy and U. K. Misra (2013). Graphoidal signed graphs. Advn. Stud. Contemp. Math.. 23 (3) , 451460## T. Zaslavsky (1982). Signed graphs. Discrete Appl. Math.. 4 (1) , 4774## T. Zaslavsky (2012). A mathematical bibliography of signed and gain graphs and its allied areas. Electron. J. Combin., Dynamic Surveys in Combinatorics (1998), no. DS8. Eighth ed.. ## ]
Full friendly index sets of slender and flat cylinder graphs
2
2
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_2times P_n$, and cylinders $C_mtimes P_n$ for some $n$ and $m$. In this paper we study the full friendly index sets of cylinder graphs $C_mtimes P_2$ for $mgeq 3$, $C_mtimes P_3$ for $mgeq 4$ and $C_3times P_n$ for $ngeq 4$. The results in this paper complement the existing results in literature, so the full friendly index set of cylinder graphs are completely determined.
1

63
80


Wai Chee
Shiu
Hong Kong Baptist University
Hong Kong Baptist University
Hong Kong
wcshiu@hkbu.edu.hk


ManHo
Ho
Hong Kong Baptist University
Hong Kong Baptist University
Hong Kong
homanho@hkbu.edu.hk
Full friendly index sets
friendly labeling
cylinder graphs
[J. A. Bondy and U. S. R. Murty (2008). Graph Theory. Graduate Texts in Mathematics, Springer, New York. 244## G. Chartrand, S.M. Lee and P. Zhang (2006). Uniformly cordial graphs. Discrete Math.. 306, 726737## H. Kwong, S.M. Lee and H. K. Ng (2008). On friendly index sets of $2$regular
graphs. Discrete Math.. 308, 55225532## H. Kwong and S.M. Lee (2008). On friendly index sets of generalized books. J. Combin. Math. Combin. Comput.. 66, 4358## S.M. Lee and H. K. Ng (2008). On friendly index sets of bipartite graphs. Ars
Combin.. 86, 257271## E. Salehi and S.M. Lee (2006). On friendly index sets of trees. Congr. Numer.. 178, 173183## W. C. Shiu and H. Kwong (2008). Full friendly index sets of {P}_2times{P}_n. Discrete Math.. 308, 36883693## W. C. Shiu and M. H. Ling (2007). Extreme friendly indices of {$C_mtimes C_n$}. Congr. Numer.. 188, 175182## W. C. Shiu and M. H. Ling (2010). Full friendly index sets of {C}artesian products
of two cycles. Acta Math. Sin. (Engl. Ser.). 26, 12331244## W. C. Shiu and F. S. Wong (2009). W. C. Shiu and F. S. Wong. Congr. Numer.. 197, 6575## W. C. Shiu and F. S. Wong (2012). Full friendly index sets of cylinder graphs. Australas. J. Combin.. 52, 141162## ]