2016
47
1
0
0
3difference cordial labeling of some cycle related graphs
2
2
Let G be a (p, q) graph. Let k be an integer with 2 ≤ k ≤ p and f from V (G) to the set {1, 2, . . . , k} be a map. For each edge uv, assign the label f(u) − f(v). The function f is called a kdifference cordial labeling of G if νf (i) − vf (j) ≤ 1 and ef (0) − ef (1) ≤ 1 where vf (x) denotes the number of vertices labelled with x (x ∈ {1, 2 . . . , k}), ef (1) and ef (0) respectively denote the number of edges labelled with 1 and not labelled with 1. A graph with a kdifference cordial labeling is called a kdifference cordial graph. In this paper we investigate the 3difference cordial labeling of wheel, helms, flower graph, sunflower graph, lotus inside a circle, closed helm, and double wheel.
1

1
10


R.
Ponraj
Department of Mathematics, Sri Paramakalyani College,Alwarkurichi627 412, India
Department of Mathematics, Sri Paramakalyani
Iran
ponrajmaths@gmail.com


M.
Maria Adaickalam
Department of Mathematics, Kamarajar Government Arts College, Surandai627859, India
Department of Mathematics, Kamarajar Government
Iran
mariaadaickalam@gmail.com
path
cycle
wheel
star
A Survey on Complexity of Integrity Parameter
2
2
Many graph theoretical parameters have been used to describe the vulnerability of communication networks, including toughness, binding number, rate of disruption, neighborconnectivity, integrity, mean integrity, edgeconnectivity vector, lconnectivity and tenacity. In this paper we discuss Integrity and its properties in vulnerability calculation. The integrity of a graph G, I(G), is defined to be min( S  +m(G − S)) where S ⊂ V (G) and m(G − S) is the maximum order of the components of G − S. Similarly the edgeintegrity of G is I′(G) := min( S  +m(G − S)) where now S ⊆ E(G). Here and through the remaining sections, by an Iset (with respect to some prescribed graph G) we will mean a set S ⊂ V (G) for which I(G) = S  +m(G − S). We define an I′set similarly. In this paper we show a lower bound on the edgeintegrity of graphs and present an algorithm for its computation.
1

11
19


Mahmood
Shabankhah
University of Tehran, College of Engineering, Department of Engineering Science
University of Tehran, College of Engineering,
Iran
shabankhah@ut.ac.ir
Integrity parameter
toughness
neighborconnectivity
mean integrity
edgeconnectivity vector
lconnectivity and tenacity
On Generalized Weak Structures
2
2
Avila and Molina [1] introduced the notion of generalized weak structures which naturally generalize minimal structures, generalized topologies and weak structures and the structures α(g),π(g),σ(g) and β(g). This work is a further investigation of generalized weak structures due to Avila and Molina. Further we introduce the structures ro(g) and rc(g) and study the properties of the structures ro(g), rc(g), and also further properties of α(g),π(g),σ(g) and β(g) due to [1].
1

21
26


R.
Jamunarani
Research Center, Department of Mathematics, Govindammal Aditanar College for Women, Tiruchendur628 215, Tamil Nadu, India
Research Center, Department of Mathematics,
Iran
jamunarani1977@gmail.com


P.
Jeyanthi
Research Center, Department of Mathematics, Govindammal Aditanar College for Women, Tiruchendur628 215, Tamil Nadu, India
Research Center, Department of Mathematics,
Iran
jeyajeyanthi@rediffmail.com


T.
Noiri
Shiokotacho Hinagu, Yatsushiroshi kumamotoken, 8695142 Japan
Shiokotacho Hinagu, Yatsushiroshi kumamotoken,
Iran
t.noiri@nifty.com
Generalized weak structure
ro(g)
rc(g)
α(g)
π(g)
σ(g)
β(g)
Online Scheduling of Jobs for Dbenevolent instances On Identical Machines
2
2
We consider online scheduling of jobs with specic release time on m identical machines. Each job has a weight and a size; the goal is maximizing total weight of completed jobs. At release time of a job it must immediately be scheduled on a machine or it will be rejected. It is also allowed during execution of a job to preempt it; however, it will be lost and only weight of completed jobs contribute on prot of the algorithm. In this paper we study Dbenevolent instances which is a wide and standard class and we give a new algorithm, that admits (2m + 4)competitive ratio. It is almost half of the previous known upper bound for this problem.
1

27
36


I.
Mohammadi
University of Tehran, Department of Algorithms and Computation.
University of Tehran, Department of Algorithms
Iran
mohammadi.iman@alumni.ut.ac.ir


Dara
Moazzami
University of Tehran, College of Engineering, Faculty of Engineering Science
University of Tehran, College of Engineering,
Iran
dmoazzami@ut.ac.ir
Online Algorithms Scheduling Identical Machine
Upper bound
Mixed cycleEsuper magic decomposition of complete bipartite graphs
2
2
An Hmagic labeling in a Hdecomposable graph G is a bijection f : V (G) ∪ E(G) → {1, 2, ..., p + q} such that for every copy H in the decomposition, ΣνεV(H) f(v) + ΣeεE(H) f(e) is constant. f is said to be HEsuper magic if f(E(G)) = {1, 2, · · · , q}. A family of subgraphs H1,H2, · · · ,Hh of G is a mixed cycledecomposition of G if every subgraph Hi is isomorphic to some cycle Ck, for k ≥ 3, E(Hi) ∩ E(Hj) = ∅ for i ≠ j and ∪hi=1E(Hi) = E(G). In this paper, we prove that K2m,2n is mixed cycleEsuper magic decomposable where m ≥ 2, n ≥ 3, with the help of the results found in [1].
1

37
52


G.
Marimuthu
Department of Mathematics, The Madura College, Madurai 625 011, Tamilnadu, India
Department of Mathematics, The Madura College,
Iran
yellowmuthu@yahoo.com;


S.
Stalin Kumar
Department of Mathematics, The American College, Madurai  625 002, Tamilnadu,India
Department of Mathematics, The American College,
Iran
sskumbas@gmail.com
Hdecomposable graph
HEsuper magic labeling
mixed cycleEsuper magic decomposable graph
Heuristic and exact algorithms for Generalized Bin Covering Problem
2
2
In this paper, we study the Generalized Bin Covering problem. For this problem an exact algorithm is introduced which can nd optimal solution for small scale instances. To nd a solution near optimal for large scale instances, a heuristic algorithm has been proposed. By computational experiments, the eciency of the heuristic algorithm is assessed.
1

53
62


S.
Jabari
University of Tehran, Department of Algorithms and Computation.
University of Tehran, Department of Algorithms
Iran
sjabari@ut.ac.ir


Dara
Moazzami
University of Tehran, College of Engineering, Faculty of Engineering Science
University of Tehran, College of Engineering,
Iran
dmoazzami@ut.ac.ir


A.
Ghodousian
University of Tehran, College of Engineering, Faculty of Engineering Science
University of Tehran, College of Engineering,
Iran
a.ghodousian@ut.ac.ir
Generalized Bin Covering Problem
heuristic algorithm
greedy algorithm
Zarankiewicz Numbers and Bipartite Ramsey Numbers
2
2
The Zarankiewicz number z(b; s) is the maximum size of a subgraph of Kb,b which does not contain Ks,s as a subgraph. The twocolor bipartite Ramsey number b(s, t) is the smallest integer b such that any coloring of the edges of Kb,b with two colors contains a Ks,s in the rst color or a Kt,t in the second color.In this work, we design and exploit a computational method for bounding and computing Zarankiewicz numbers. Using it, we obtain several new values and bounds on z(b; s) for 3≤s≤6. Our approach and new knowledge about z(b; s) permit us to improve some of the results on bipartite Ramsey numbers obtained by
1

63
78


Alex F.
Collins
Rochester Institute of Technology, School of Mathematical Sciences, Rochester, NY 14623
Rochester Institute of Technology, School
Iran
weincoll@gmail.com


Alexander W. N.
Riasanovsky
University of Pennsylvania, Department of Mathematics, Philadelphia, PA 19104, USA
University of Pennsylvania, Department of
Iran
alexneal@math.upenn.edu


John C.
Wallace
Trinity College, Department of Mathematics, Hartford, CT 06106, USA
Trinity College, Department of Mathematics,
Iran
john.wallace@trincoll.edu


Stanis law P.
Radziszowski
Rochester Institute of Technology, Department of Computer Science, Rochester, NY 14623
Rochester Institute of Technology, Department
Iran
spr@cs.rit.edu
Zarankiewicz number
bipartite Ramsey number
Randomized Algorithm For 3Set Splitting Problem and it's Markovian Model
2
2
In this paper we restrict every set splitting problem to the special case in which every set has just three elements. This restricted version is also NPcomplete. Then, we introduce a general conversion from any set splitting problem to 3set splitting. Then we introduce a randomize algorithm, and we use Markov chain model for run time complexity analysis of this algorithm. In the last section of this paper we introduce "Fast Split" algorithm.
1

79
92


Mahdi
Heidari
Department of Algorithms and Computation, University of Tehran
Department of Algorithms and Computation,
Iran
mahdi.heydari@intec.ugent.be


Ali
Golshani
Department of Algorithms and Computation, University of Tehran
Department of Algorithms and Computation,
Iran
ali.golshani@gmail.com


D.
Moazzami
University of Tehran, College of Engineering, Faculty of Enginering Science
University of Tehran, College of Engineering,
Iran
dmoazzami@ut.ac.ir


Ali
Moeini
University of Tehran, College of Engineering, Faculty of Enginering Science
University of Tehran, College of Engineering,
Iran
moeini@ut.ac.ir
NPcomplete problem
set splitting problem
SAT problem
Markov chain
A Cellular Automaton Based Algorithm for Mobile Sensor Gathering
2
2
In this paper we proposed a Cellular Automaton based local algorithm to solve the autonomously sensor gathering problem in Mobile Wireless Sensor Networks (MWSN). In this problem initially the connected mobile sensors deployed in the network and goal is gather all sensors into one location. The sensors decide to move only based on their local information. Cellular Automaton (CA) as dynamical systems in which space and time are discrete and rules are local, is proper candidate to simulate and analyze the problem. Using CA presents a better understanding of the problem.
1

93
99


S.
Saadatmand
University of New South Wales, College of Engineering, Department of Computer Science, Sydney, Australia.
University of New South Wales, College of
Iran
samadseadatmand@yahoo.com


D.
Moazzami
University of Tehran, College of Engineering, Faculty of Engineering Science
University of Tehran, College of Engineering,
Iran
dmoazzami@ut.ac.ir


A.
Moeini
University of Tehran, College of Engineering, Faculty of Engineering Science
University of Tehran, College of Engineering,
Iran
moeini@ut.ac.ir
Mobile Wireless Sensor Network
Mobile Sensor Gathering
Cellular Automata
Local Algorithm
A Mathematical Optimization Model for Solving Minimum Ordering Problem with Constraint Analysis and some Generalizations
2
2
In this paper, a mathematical method is proposed to formulate a generalized ordering problem. This model is formed as a linear optimization model in which some variables are binary. The constraints of the problem have been analyzed with the emphasis on the assessment of their importance in the formulation. On the one hand, these constraints enforce conditions on an arbitrary subgraph and then give sufficient conditions for feasibility, on the other hand, they provide a natural way to generalize the applied aspects of the model without increasing the number of the binary variables.
1

101
117


Samira
Rezaei
Department of Algorithms and Computation, University of Tehran
Department of Algorithms and Computation,
Iran
samirarezaei@ut.ac.ir


Amin
Ghodousian
University of Tehran, College of Engineering, Faculty of Engineering Science
University of Tehran, College of Engineering,
Iran
a.ghodousian@ut.ac.ir
linear programming
integer programming
minimum ordering
The edge tenacity of a split graph
2
2
The edge tenacity Te(G) of a graph G is dened as:Te(G) = min {[X+τ(GX)]/[ω(GX)1]X ⊆ E(G) and ω(GX) > 1} where the minimum is taken over every edgecutset X that separates G into ω(G  X) components, and by τ(G  X) we denote the order of a largest component of G. The objective of this paper is to determine this quantity for split graphs. Let G = (Z; I; E) be a noncomplete connected split graph with minimum vertex degree δ(G) we prove that if δ(G)≥E(G)/[V(G)1] then its edgetenacity is E(G)/[V(G)1] .
1

119
125


Bahareh
Bafandeh Mayvan
Department of Computer Engineering, Ferdowsi University of Mashhad
Department of Computer Engineering, Ferdowsi
Iran
bahareh.bafandeh@gmail.com
vertex degree
split graphs
edge tenacity
Minimum Tenacity of Toroidal graphs
2
2
The tenacity of a graph G, T(G), is dened by T(G) = min{[S+τ(GS)]/[ω(GS)]}, where the minimum is taken over all vertex cutsets S of G. We dene τ(G  S) to be the number of the vertices in the largest component of the graph G  S, and ω(G  S) be the number of components of G  S.In this paper a lower bound for the tenacity T(G) of a graph with genus γ(G) is obtained using the graph's connectivity κ(G). Then we show that such a bound for almost all toroidal graphs is best possible.
1

127
135


Hamid
Doost Hosseini
University of Tehran, College of Engineering, School of Civil Engineering
University of Tehran, College of Engineering,
Iran
h.doosth@gmail.com
genus
graph's connectivity
toroidal graphs