University of TehranJournal of Algorithms and Computation2476-277648120161128Deciding Graph non-Hamiltonicity via a Closure Algorithm135793710.22059/jac.2016.7937ENE. R.SwartKelowna, British Columbia, CanadaStephen J.GismondiUniversity of Guelph, CanadaN. R.SwartUniversity of British Columbia Okanagan, CanadaC. E.BellGuelph, Ontario, CanadaA.LeeUniversity of Guelph, CanadaJournal Article20160126We present a matching and LP based heuristic algorithm that decides graph non-Hamiltonicity. Each of the <em>n</em>! Hamilton cycles in a complete directed graph on <em>n</em> + 1 vertices corresponds with each of the <em>n</em>! <em>n</em>-permutation matrices <em>P</em>, such that <em>p<sub>u</sub></em><sub>,<em>i</em></sub> = 1 if and only if the <em>i<sup>th</sup></em> arc in a cycle enters vertex <em>u</em>, starting and ending at vertex <em>n</em> + 1. A graph instance (<em>G</em>) is initially coded as exclusion set <em>E</em>, whose members are pairs of components of <em>P</em>, {<em>p</em><sub><em>u</em>,<em>i</em></sub>, <em>p<sub>v</sub></em><sub>,<em>i</em>+1</sub>}, <em>i</em> = 1, <em>n</em> - 1, for each arc (<em>u</em>, <em>v</em>) not inhttps://jac.ut.ac.ir/article_7937_15545482e67a30452c97e86eb5b51fa9.pdfUniversity of TehranJournal of Algorithms and Computation2476-277648120161208On the tenacity of cycle permutation graph3744793810.22059/jac.2016.7938END.JelodarUniversity of Tehran, Department of Algorithms and ComputationD.MoazzamiUniversity of Tehran, College of Engineering, Department of Engineering ScienceP.NasehpourUniversity of Tehran, College of Engineering, Department of Engineering Science0000-0001-6625-364XJournal Article20160220A special class of cubic graphs are the cycle permutation graphs. A cycle permutation graph <em>P<sub>n</sub></em>(<em>α</em>) is defined by taking two vertex-disjoint cycles on <em>n</em> vertices and adding a matching between the vertices of the two cycles.<br />In this paper we determine a good upper bound for tenacity of cycle permutation graphs.https://jac.ut.ac.ir/article_7938_a7b34f56efc535ed46a94f44aa7e3d23.pdfUniversity of TehranJournal of Algorithms and Computation2476-277648120161110A note on 3-Prime cordial graphs4555793910.22059/jac.2016.7939ENR.PonrajDepartment of Mathematics, Sri Paramakalyani College,Alwarkurichi-627412, IndiaRajpalSinghResearch Scholar, Department of Mathematics Manonmaniam Sundaranar University, Tirunelveli-627012, IndiaS.Sathish NarayananDepartment of Mathematics, Sri Paramakalyani College,Alwarkurichi-627412, IndiaJournal Article20160616Let <em>G</em> be a (<em>p</em>, <em>q</em>) graph. Let <em>f</em> : <em>V</em> (<em>G</em>) → {1, 2, . . . , <em>k</em>} be a map. For each edge <em>uv</em>, assign the label gcd (<em>f</em>(<em>u</em>), <em>f</em>(<em>v</em>)). <em>f</em> is called <em>k</em>-prime cordial labeling of <em>G</em> if |<em>v<sub>f</sub></em> (<em>i</em>) − <em>v<sub>f</sub></em> (<em>j</em>)| ≤ 1, <em>i</em>, <em>j</em> ∈ {1, 2, . . . , <em>k</em>} and |<em>e<sub>f</sub></em> (0) − <em>e<sub>f</sub></em> (1)| ≤ 1 where <em>v<sub>f</sub></em> (<em>x</em>) denotes the number of vertices labeled with <em>x</em>, <em>e<sub>f</sub></em> (1) and <em>e<sub>f</sub></em> (0) respectively denote the number of edges labeled with 1 and not labeled with 1. A graph with a <em>k</em>-prime cordial labeling is called a <em>k</em>-prime cordial graph. In this paper we investigate 3- prime cordial labeling behavior of union of a 3-prime cordial graph and a path <em>P<sub>n</sub></em>.https://jac.ut.ac.ir/article_7939_495c61efe2289c038edc6c7099386507.pdfUniversity of TehranJournal of Algorithms and Computation2476-277648120161101Edge pair sum labeling of some cycle related graphs5768794010.22059/jac.2016.7940ENP.JeyanthiGovindammal Aditanar College for Women Tiruchendur-628 215, Tamil Nadu, IndiaT.Saratha DeviDepartment of Mathematics, G.Venkataswamy Naidu College, Kovilpatti-628502,Tamilnadu,India.Journal Article20160128Let <em>G</em> be a (<em>p</em>,<em>q</em>) graph. An injective map <em>f</em> : <em>E</em>(<em>G</em>) → {±1,±2,...,±q} is said to be an edge pair sum labeling if the induced vertex function <em>f</em><sup>*</sup>: <em>V</em> (<em>G</em>) → <em>Z</em> - {0} defined by <em>f</em><sup>*</sup>(<em>v</em>) = Σ<sub><em>P</em><span>∈</span><em>Ev</em></sub> <em>f</em> (<em>e</em>) is one-one where <em>E<sub>v</sub></em> denotes the set of edges in<em> G</em> that are incident with a vertex <em>v</em> and <em>f</em><sup>*</sup>(<em>V</em> (<em>G</em>)) is either of the form {±<em>k</em><sub>1</sub>,±<em>k</em><sub>2</sub>,...,±<em>k<sub>p</sub></em><sub>/2</sub>} or {±<em>k</em><sub>1</sub>,±<em>k</em><sub>2</sub>,...,±<em>k</em><sub>(<em>p</em>-1)</sub><sub>/2</sub>} U {±<em>k</em><sub>(<em>p+</em>1)</sub><sub>/2</sub>} according as <em>p</em> 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 <em>GL</em>(<em>n</em>), double triangular snake <em>D</em>(<em>T<sub>n</sub></em>), <em>W<sub>n</sub></em>, <em>Fl<sub>n</sub></em>, <<em>C<sub>m</sub></em>,<em>K</em><sub>1,<em>n</em></sub>> and <<em>C<sub>m</sub></em> * <em>K</em><sub>1,<em>n</em></sub>> admit edge pair sum labeling.https://jac.ut.ac.ir/article_7940_56568b68b988fc59429af15e748b7a64.pdfUniversity of TehranJournal of Algorithms and Computation2476-2776481201612154-Prime cordiality of some classes of graphs6979794110.22059/jac.2016.7941ENR.PonrajDepartment of Mathematics, Sri Paramakalyani College,Alwarkurichi-627 412, IndiaRajpalSinghResearch Scholar, Department of Mathematics, Manonmaniam Sundaranar University, Tirunelveli-627012, IndiaS.Sathish NarayananDepartment of Mathematics, Sri Paramakalyani College,Alwarkurichi-627 412, IndiaA. M. S.RamasamyDepartment of Mathematics, Vel Tech Dr.R.R & Dr.S.R Technical University, Chennai-600002, IndiaJournal Article20160701Let <em>G</em> be a (<em>p</em>, <em>q</em>) graph. Let <em>f</em> : <em>V</em> (<em>G</em>) → {1, 2, . . . , <em>k</em>} be a map. For each edge <em>uv</em>, assign the label gcd (<em>f</em>(<em>u</em>), <em>f</em>(<em>v</em>)). <em>f</em> is called <em>k</em>-prime cordial labeling of <em>G</em> if |<em>v<sub>f</sub></em> (<em>i</em>) − <em>v<sub>f</sub></em> (<em>j</em>)| ≤ 1, <em>i</em>, <em>j</em> ∈ {1, 2, . . . , <em>k</em>} and |<em>e<sub>f</sub></em> (0) − <em>e<sub>f</sub></em> (1)| ≤ 1 where <em>v<sub>f</sub></em> (x) denotes the number of vertices labeled with <em>x</em>, <em>e<sub>f</sub></em> (1) and <em>e<sub>f</sub></em> (0) respectively denote the number of edges labeled with 1 and not labeled with 1. A graph with a<em> k</em>-prime cordial labeling is called a <em>k</em>-prime cordial graph. In this paper we investigate 4- prime cordial labeling behavior of complete graph, book, flower, <em>mC<sub>n</sub></em> and some more graphs.https://jac.ut.ac.ir/article_7941_01050790c89557f0425ee26385c3b6b9.pdfUniversity of TehranJournal of Algorithms and Computation2476-277648120161216Further results on odd mean labeling of some subdivision graphs8198794210.22059/jac.2016.7942ENR.VasukiDepartment of Mathematics, Dr. Sivanthi Aditanar College of Engineering, Tiruchendur-628 215, Tamil Nadu, IndiaS.SuganthiDepartment of Mathematics, Dr. Sivanthi Aditanar College of Engineering, Tiruchendur-628 215, Tamil Nadu, IndiaG.PooranamDepartment of Mathematics, Dr. Sivanthi Aditanar College of Engineering, Tiruchendur-628 215, Tamil Nadu, IndiaJournal Article20160418Let <em>G</em>(<em>V</em>,<em>E</em>) be a graph with <em>p</em> vertices and <em>q</em> edges. A graph <em>G</em> is said to have an odd mean labeling if there exists a function <em>f</em> : <em>V</em> (<em>G</em>) → {0, 1, 2,...,2<em>q</em> - 1} satisfying <em>f</em> is 1 - 1 and the induced map <em>f</em><sup>*</sup> : <em>E</em>(<em>G</em>) → {1, 3, 5,...,2<em>q</em> - 1} defined by
<br /><em>f</em><sup>*</sup>(<em>uv</em>) = (<em>f</em>(<em>u</em>) + <em>f</em>(<em>v</em>))/2 if <em>f</em>(<em>u</em>) + <em>f</em>(<em>v</em>) is even<br /><em>f</em><sup>*</sup>(<em>uv</em>) = (<em>f</em>(<em>u</em>) + <em>f</em>(<em>v</em>) + 1)/2 if <em>f</em>(<em>u</em>) + <em>f</em>(<em>v</em>) is odd
<br />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 <em>SL<sub>n</sub></em> for all <em>n</em> ≥ 2; <em>C<sub>n</sub> </em>Θ <em>K<sub>1</sub></em> for n ≥ 3; the grid <em>P<sub>m </sub></em>× <em>P<sub>n</sub></em> for m, n ≥ 2; <em>C<sub>m</sub></em>@<em>C<sub>n</sub></em> for m, n ≥ 3 and <em>P</em><sub>2<em>m </em></sub>Θ <em>nK</em><sub>1</sub> for all m, n ≥ 1..https://jac.ut.ac.ir/article_7942_b5919c4f284019e6cc358136ade4b8ed.pdfUniversity of TehranJournal of Algorithms and Computation2476-277648120161101An Optimization Model for Epidemic Mitigation and Some Theoretical and Applied Generalizations99116794510.22059/jac.2016.7945ENSimaRanjbarfardDepartment of Algorithms and Computation, University of Tehran.AminGhodousianUniversity of Tehran, College of Engineering, Faculty of Engineering ScienceD.MoazzamiUniversity of Tehran, College of Engineering, Faculty of Engineering ScienceJournal Article20150630In this paper, we present a binary-linear 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 nodes-minimum deleted links problem and minimum removed links problem nding a prespecied number of nodes with weakest connections.https://jac.ut.ac.ir/article_7945_d579d657e55fe3023b8855e49200e683.pdfUniversity of TehranJournal of Algorithms and Computation2476-277648120161225Constructing Graceful Graphs with Caterpillars117125794610.22059/jac.2016.7946ENChristianBarrientosDepartment of Mathematics, Clayton State University, Morrow, Georgia 30260, USASarahMinionDepartment of Mathematics, Clayton State University, Morrow, Georgia 30260, USAJournal Article20160605A graceful labeling of a graph <em>G</em> of size <em>n</em> is an injective assignment of integers from {0, 1,...,<em> n</em>} to the vertices of <em>G</em>, such that when each edge of <em>G</em> has assigned a weight, given by the absolute dierence of the labels of its end vertices, the set of weights is {1, 2,..., <em>n</em>}. If a graceful labeling <em>f</em> of a bipartite graph <em>G</em> assigns the smaller labels to one of the two stable sets of <em>G</em>, then <em>f</em> is called an -labeling and <em>G</em> is said to be an <em>α</em>-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 <em>α</em>-graph. In addition, we present a new family of graceful trees constructed using <em>α</em>-labeled caterpillars.https://jac.ut.ac.ir/article_7946_ab86e4c77cafca0ee7fc0724a85925bb.pdfUniversity of TehranJournal of Algorithms and Computation2476-277648120161225Total vertex irregularity strength of corona product of some graphs127140794810.22059/jac.2016.7948ENP.JeyanthiResearch Centre, Department of Mathematics, Govindammal Aditanar College for Women, Tiruchendur-628 215, Tamil Nadu, India.A.SudhaDepartment of Mathematics, Wavoo Wajeeha Women’s College of Arts and Science, Kayalpatnam -628 204,Tamil Nadu, India.Journal Article20160822A vertex irregular total k-labeling of a graph <em>G</em> with vertex set <em>V</em> and edge set <em>E</em> is an assignment of positive integer labels {1, 2, ..., <em>k</em>} to both vertices and edges so that the weights calculated at vertices are distinct. The total vertex irregularity strength of <em>G</em>, denoted by <em>tvs</em>(<em>G</em>)is the minimum value of the largest label <em>k</em> over all such irregular assignment. In this paper, we study the total vertex irregularity strength for <em>n</em> ≥ 3, <em>m</em> ≥ 2, <em>P<sub>n</sub></em> ⊙ <em>K<sub>1</sub></em>, <em>P<sub>n</sub></em> ⊙ <em>K<sub>2</sub></em>, <em>C<sub>n</sub></em> ⊙ <em>K<sub>2</sub></em>, <em>L<sub>n</sub></em> ⊙ <em>K<sub>1</sub></em>, <em>CL<sub>n</sub></em> ⊙ <em>K<sub>1</sub></em>, <em>P<sub>2</sub></em> ⊙ <em>C<sub>n</sub></em>, <em>P<sub>n</sub></em> ⊙ <em>K<sub>m</sub></em>, <em>C<sub>n</sub></em> ⊙ <em>K<sub>m</sub></em>https://jac.ut.ac.ir/article_7948_75d3525b3126762d9d4dfccb440cd4e7.pdfUniversity of TehranJournal of Algorithms and Computation2476-277648120161225A Survey on Stability Measure of Networks141148795210.22059/jac.2016.7952ENPeymanNasehpourDepartment of Algorithms and Computation, Faculty of Engineering Science, University of Tehran0000-0001-6625-364XJournal Article20160215In 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.https://jac.ut.ac.ir/article_7952_6f002c9f5ab6a9706c13862fae8bd92a.pdfUniversity of TehranJournal of Algorithms and Computation2476-277648120161211Towards a measure of vulnerability, tenacity of a Graph149153795310.22059/jac.2016.7953ENDaraMoazzamiUniversity of Tehran, College of Engineering, Department of Engineering ScienceJournal Article20160110If 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.<br />In this paper we discuss tenacity and its properties in vulnerability calculation.https://jac.ut.ac.ir/article_7953_f2b13c1826d752109b66c0748d01a288.pdfUniversity of TehranJournal of Algorithms and Computation2476-277648120161225A Survey On the Vulnerability Parameters of Networks155162795510.22059/jac.2016.7955ENMahmoodShabankhahUniversity of Tehran, College of Engineering, Faculty of Engineering ScienceJournal Article20160306The 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 suggest<br />a most suitable measure of vulnerability.https://jac.ut.ac.ir/article_7955_90bffa8a1a1619f646beb2bd9af65d54.pdf