2016
48
1
0
0
Deciding Graph nonHamiltonicity via a Closure Algorithm
2
2
We present a matching and LP based heuristic algorithm that decides graph nonHamiltonicity. Each of the n! Hamilton cycles in a complete directed graph on n + 1 vertices corresponds with each of the n! npermutation matrices P, such that pu,i = 1 if and only if the ith arc in a cycle enters vertex u, starting and ending at vertex n + 1. A graph instance (G) is initially coded as exclusion set E, whose members are pairs of components of P, {pu,i, pv,i+1}, i = 1, n  1, for each arc (u, v) not in
1

1
35


E. R.
Swart
Kelowna, British Columbia, Canada
Kelowna, British Columbia, Canada
Iran
ted.swart@shaw.ca


Stephen J.
Gismondi
University of Guelph, Canada
University of Guelph, Canada
Iran
gismondi@uoguelph.ca


N. R.
Swart
University of British Columbia Okanagan, Canada
University of British Columbia Okanagan,
Iran
nicholas.swart@shaw.ca


C. E.
Bell
Guelph, Ontario, Canada
Guelph, Ontario, Canada
Iran
ca_bell@rogers.com


A.
Lee
University of Guelph, Canada
University of Guelph, Canada
Iran
alee15@mail.uoguelph.ca
Hamilton cycle
decision problem
On the tenacity of cycle permutation graph
2
2
A special class of cubic graphs are the cycle permutation graphs. A cycle permutation graph Pn(α) is defined by taking two vertexdisjoint cycles on n vertices and adding a matching between the vertices of the two cycles.In this paper we determine a good upper bound for tenacity of cycle permutation graphs.
1

37
44


D.
Jelodar
University of Tehran, Department of Algorithms and Computation
University of Tehran, Department of Algorithms
Iran
djelodar@alumni.ut.ac.ir


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


P.
Nasehpour
University of Tehran, College of Engineering, Department of Engineering Science
University of Tehran, College of Engineering,
Iran
nasehpour@gmail.com
tenacity
Tenacious
Cycle Permutation
toughness
integrity
A note on 3Prime cordial graphs
2
2
Let G be a (p, q) graph. Let f : V (G) → {1, 2, . . . , k} be a map. For each edge uv, assign the label gcd (f(u), f(v)). f is called kprime cordial labeling of G if vf (i) − vf (j) ≤ 1, i, j ∈ {1, 2, . . . , k} and ef (0) − ef (1) ≤ 1 where vf (x) denotes the number of vertices labeled with x, ef (1) and ef (0) respectively denote the number of edges labeled with 1 and not labeled with 1. A graph with a kprime cordial labeling is called a kprime cordial graph. In this paper we investigate 3 prime cordial labeling behavior of union of a 3prime cordial graph and a path Pn.
1

45
55


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


Rajpal
Singh
Research Scholar, Department of Mathematics Manonmaniam Sundaranar University, Tirunelveli627012, India
Research Scholar, Department of Mathematics
Iran
rajpalsingh@gmail.com


S.
Sathish Narayanan
Department of Mathematics, Sri Paramakalyani College,Alwarkurichi627412, India
Department of Mathematics, Sri Paramakalyani
Iran
sathishrvss@gmail.com
path
union of graphs
Edge pair sum labeling of some cycle related graphs
2
2
Let G be a (p,q) graph. An injective map f : E(G) → {±1,±2,...,±q} is said to be an edge pair sum labeling if the induced vertex function f*: V (G) → Z  {0} defined by f*(v) = ΣP∈Ev f (e) is oneone where Ev denotes the set of edges in G that are incident with a vertex v and f*(V (G)) is either of the form {±k1,±k2,...,±kp/2} or {±k1,±k2,...,±k(p1)/2} U {±k(p+1)/2} according as p is even or odd. A graph with an edge pair sum labeling is called an edge pair sum graph. In this paper we prove that the graphs GL(n), double triangular snake D(Tn), Wn, Fln, <Cm,K1,n> and <Cm * K1,n> admit edge pair sum labeling.
1

57
68


P.
Jeyanthi
Govindammal Aditanar College for Women Tiruchendur628 215, Tamil Nadu, India
Govindammal Aditanar College for Women Tiruchendur
Iran
jeyajeyanthi@rediffmail.com


T.
Saratha Devi
Department of Mathematics, G.Venkataswamy Naidu College, Kovilpatti628502,Tamilnadu,India.
Department of Mathematics, G.Venkataswamy
Iran
rajanvino03@gmail.com
Edge pair sum labeling
edge pair sum graph
double triangular snake
wheel graph
ower graph
4Prime cordiality of some classes of graphs
2
2
Let G be a (p, q) graph. Let f : V (G) → {1, 2, . . . , k} be a map. For each edge uv, assign the label gcd (f(u), f(v)). f is called kprime cordial labeling of G if vf (i) − vf (j) ≤ 1, i, j ∈ {1, 2, . . . , k} and ef (0) − ef (1) ≤ 1 where vf (x) denotes the number of vertices labeled with x, ef (1) and ef (0) respectively denote the number of edges labeled with 1 and not labeled with 1. A graph with a kprime cordial labeling is called a kprime cordial graph. In this paper we investigate 4 prime cordial labeling behavior of complete graph, book, flower, mCn and some more graphs.
1

69
79


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


Rajpal
Singh
Research Scholar, Department of Mathematics, Manonmaniam Sundaranar University, Tirunelveli627012, India
Research Scholar, Department of Mathematics,
Iran
rajpalsingh@gmail.com


S.
Sathish Narayanan
Department of Mathematics, Sri Paramakalyani College,Alwarkurichi627 412, India
Department of Mathematics, Sri Paramakalyani
Iran
sathishrvss@gmail.com


A. M. S.
Ramasamy
Department of Mathematics, Vel Tech Dr.R.R & Dr.S.R Technical University, Chennai600002, India
Department of Mathematics, Vel Tech Dr.R.R
Iran
ramasamyams@veltechuniv.edu.in
Complete graph
wheel
path
book
flower
Further results on odd mean labeling of some subdivision graphs
2
2
Let G(V,E) be a graph with p vertices and q edges. A graph G is said to have an odd mean labeling if there exists a function f : V (G) → {0, 1, 2,...,2q  1} satisfying f is 1  1 and the induced map f* : E(G) → {1, 3, 5,...,2q  1} defined by
f*(uv) = (f(u) + f(v))/2 if f(u) + f(v) is evenf*(uv) = (f(u) + f(v) + 1)/2 if f(u) + f(v) is odd
is a bijection. A graph that admits an odd mean labeling is called an odd mean graph. In this paper, we have studied an odd meanness property of the subdivision of the slanting ladder SLn for all n ≥ 2; Cn Θ K1 for n ≥ 3; the grid Pm × Pn for m, n ≥ 2; Cm@Cn for m, n ≥ 3 and P2m Θ nK1 for all m, n ≥ 1..
1

81
98


R.
Vasuki
Department of Mathematics, Dr. Sivanthi Aditanar College of Engineering, Tiruchendur628 215, Tamil Nadu, India
Department of Mathematics, Dr. Sivanthi Aditanar
Iran
vasukisehar@gmail.com


S.
Suganthi
Department of Mathematics, Dr. Sivanthi Aditanar College of Engineering, Tiruchendur628 215, Tamil Nadu, India
Department of Mathematics, Dr. Sivanthi Aditanar
Iran
vinisuga21@gmail.com


G.
Pooranam
Department of Mathematics, Dr. Sivanthi Aditanar College of Engineering, Tiruchendur628 215, Tamil Nadu, India
Department of Mathematics, Dr. Sivanthi Aditanar
Iran
dpooranamg@gmail.com
labeling
odd mean labeling
odd mean graph
An Optimization Model for Epidemic Mitigation and Some Theoretical and Applied Generalizations
2
2
In this paper, we present a binarylinear optimization model to prevent the spread of an infectious disease in a community. The model is based on the remotion of some connections in a contact network in order to separate infected nodes from the others. By using this model we nd an exact optimal solution and determine not only the minimum number of deleted links but also their exact positions. The formulation of the model is insensitive to the number of edges in a graph and can be used (with complete or local information) to measure the resistance of a network before and after an infectious spreads. Also, we propose some related models as generalizations: quarantining problem including resource constraints (time, budget, etc.), maximum rescued nodesminimum deleted links problem and minimum removed links problem nding a prespecied number of nodes with weakest connections.
1

99
116


Sima
Ranjbarfard
Department of Algorithms and Computation, University of Tehran.
Department of Algorithms and Computation,
Iran
sima.ranjbar@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


D.
Moazzami
University of Tehran, College of Engineering, Faculty of Engineering Science
University of Tehran, College of Engineering,
Iran
dmoazzami@ut.ac.ir
Epidemic control
Networks
Link removal
Quarantine
Partitioning
Optimization
Constructing Graceful Graphs with Caterpillars
2
2
A graceful labeling of a graph G of size n is an injective assignment of integers from {0, 1,..., n} to the vertices of G, such that when each edge of G has assigned a weight, given by the absolute dierence of the labels of its end vertices, the set of weights is {1, 2,..., n}. If a graceful labeling f of a bipartite graph G assigns the smaller labels to one of the two stable sets of G, then f is called an labeling and G is said to be an αgraph. A tree is a caterpillar if the deletion of all its leaves results in a path. In this work we study graceful labelings of the disjoint union of a cycle and a caterpillar. We present necessary conditions for this union to be graceful and, in the case where the cycle has even size, to be an αgraph. In addition, we present a new family of graceful trees constructed using αlabeled caterpillars.
1

117
125


Christian
Barrientos
Department of Mathematics, Clayton State University, Morrow, Georgia 30260, USA
Department of Mathematics, Clayton State
Iran
chr_barrientos@yahoo.com


Sarah
Minion
Department of Mathematics, Clayton State University, Morrow, Georgia 30260, USA
Department of Mathematics, Clayton State
Iran
sarah.m.minion@gmail.com
graceful labeling
caterpillar
graceful trees
Total vertex irregularity strength of corona product of some graphs
2
2
A vertex irregular total klabeling of a graph G with vertex set V and edge set E is an assignment of positive integer labels {1, 2, ..., k} to both vertices and edges so that the weights calculated at vertices are distinct. The total vertex irregularity strength of G, denoted by tvs(G)is the minimum value of the largest label k over all such irregular assignment. In this paper, we study the total vertex irregularity strength for n ≥ 3, m ≥ 2, Pn ⊙ K1, Pn ⊙ K2, Cn ⊙ K2, Ln ⊙ K1, CLn ⊙ K1, P2 ⊙ Cn, Pn ⊙ Km, Cn ⊙ Km
1

127
140


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


A.
Sudha
Department of Mathematics, Wavoo Wajeeha Women’s College of Arts and Science, Kayalpatnam 628 204,Tamil Nadu, India.
Department of Mathematics, Wavoo Wajeeha
Iran
sudhathanalakshmi@gmail.com
irregularity strength
total vertex irregularity strength
vertex irregular total labeling
corona product of path and cycle
path and complete graph
ladder and complete graph
graph
A Survey on Stability Measure of Networks
2
2
In this paper we discuss about tenacity and its properties in stability calculation. We indicate relationships between tenacity and connectivity, tenacity and binding number, tenacity and toughness. We also give good lower and upper bounds for tenacity.
1

141
148


Peyman
Nasehpour
Department of Algorithms and Computation, Faculty of Engineering Science, University of Tehran
Department of Algorithms and Computation,
Iran
nasehpour@gmail.com
binding number
connectivity
toughness
tenacity
Towards a measure of vulnerability, tenacity of a Graph
2
2
If we think of the graph as modeling a network, the vulnerability measure the resistance of the network to disruption of operation after the failure of certain stations or communication links. Many graph theoretical parameters have been used to describe the vulnerability of communication networks, including connectivity, integrity, toughness, binding number and tenacity.In this paper we discuss tenacity and its properties in vulnerability calculation.
1

149
154


Dara
Moazzami
University of Tehran, College of Engineering, Department of Engineering Science
University of Tehran, College of Engineering,
Iran
dmoazzami@ut.ac.ir
connectivity
integrity
toughness
binding number and tenacity
A Survey On the Vulnerability Parameters of Networks
2
2
The analysis of vulnerability in networks generally involves some questions about how the underlying graph is connected. One is naturally interested in studying the types of disruption in the network that maybe caused by failures of certain links or nodes. In terms of a graph, the concept of connectedness is used in dierent forms to study many of the measures of vulnerability. When certain vertices or edges of a connected graph are deleted, one wants to know whether the remaining graph is still connected, and if so, what its vertex  or edge  connectivity is. If on the other hand, the graph is disconnected, the determination of the number of its components or their orders is useful. Our purpose here is to describe and analyze the current status of the vulnerability measures, identify its more interesting variants, and suggesta most suitable measure of vulnerability.
1

155
162


Mahmood
Shabankhah
University of Tehran, College of Engineering, Faculty of Engineering Science
University of Tehran, College of Engineering,
Iran
shabankhah@ut.ac.ir
vulnerability measures
connectivity
binding number
toughness
integrity
tenacity