Equivalent condition and two algorithms for hamiltonian graphs

Equivalent condition and two algorithms for hamiltonian graphs

• 1.
  International Journal onApplications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC) Vol.6, No.3, September 2014 EQUIVALENT CONDITION AND TWO ALGORITHMS FOR HAMILTONIAN GRAPHS A.Z.Abdian, , Hosseinhatami, F.Shahamiri Department of mathematics, college of science Lorestanuniversity, Lorestan, Iran ABSTRACT: In this paper we present a necessary and sufficient condition for Hamiltonian graphs and also twoalgorithms and two examples in another part. KEYWORDS: Hamiltonian Graph; Finite Sequence; Algorithm, Spanning graph, Edge Induced, Chord. 1. INTRODUCTION We consider finite and simple graphs in this paper; undefined notations and terminology can be found in[1]. A Hamiltonian graph is a graph with a spanning cycle, also called a Hamiltonian cycle [2]. We note thatthe spanning cycle is not unique. Now suppose that E' is a nonempty subset of E. The sub graph of G where vertex set is the set of ends of edges in E' and whose edge set is E' is called the sub graph of G induced by E'and is denoted by G[E']; G[E'] is an edge-induced sub graph of G[1] . A chord of a cycle C is an edgenot in Cwhere endpoints put in G[2]. = { : is a cycle, such that it has an edge it ofE(G)}. We note that including the edge i th is not unique. In this paper we suppose that , then G has a cycle at least.Let be cycles, if and
• 2.
  , with i 1areintersected, we call
• 3.
  a sequence ofcycles.Also spanning sequence S is a sequence of cycles, which V[G]=V[S]. If and are cycles of graph G such that V( ) V() then we say that Extends . So C is a minimal cycle, if there is not a cycle , where C extends . 2. MAIN RESULTS Theorem 2.1. If G is a graph of order n, then G is Hamiltonian if and only if G satisfies in the following condition (* ); (* ) There is a finite sequence of members, where this sequence is an edge-induced and spanning Sub graph (with initial cycle ), and only for every i that i 1,
• 4.
  and intersectin i, which i is an edge ofE(G). DOI:10.5121/jgraphoc.2014.6301 1
• 5.
  International Journal onApplications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC) Vol.6, No.3, September 2014 Proof (Necessity). We suppose that G is Hamiltonian, then G has at least one spanning cycle C, with sequence of distinct vertices
• 6.
  . If G= C, then we must consider C as a single sequence.But if G C, so complement of C in G has a finite number of edge (chord), which it is introduced by .We prove by induction on number of the chord i.e. = , the existence of sequence. But for k=2 , i.e. if there are two chords and , we will have two case. The first, for i j s t, there exists by Figure (2) 2 Remark 2.2. Indeed we give to make this sequence a finite number ofmembers. Basis step: if k=1 , this is obvious (look at the graph in Figure 1). . In the second, if i j t s, according to the graph in Figure 3, we deleteone of the chords, and so by k=1 , there are two cycles. This is straightforward to understand that there isnot any case. ''Figure(1), graph of k=1'' ''Figure(2), graph of the first mode in k=2'' '' Figure(3), graph second mode in of the second mode in k=2' Induction step: We suppose that claim holds for all values less than m,also length of sequence is t .Now by adding chord m th, we establish the existence a spanning sequence of members, where only for every i with i 1, and are common in one edge i. If the chord m is in two distinct cycles and , such that g-h=r with r 1, i.e. endpoints are not just lied in one cycle. We give these cycles ( r +1cycles) as two new cycle. Therefore a spanning sequence is found and the statement is
• 7.
  International Journal onApplications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC) Vol.6, No.3, September 2014 established by induction hypothesis. But if this chord is only in one cycle as . The cycle decomposes into two smaller cycles. Hence there is a spanning sequence of members in , that its length is t or t + 1, as claimed. Proof (sufficiency). Let G be a graph that satisfies the (* ). Since this sequence contains all the vertices of G, we must achieve by removing the edges shared between any two consecutive cycles a spanning cycle. Therefore G is Hamiltonian. Algorithm2.5. According to the Theorem 2.1, we consider an initial cycle that is denoted by firstly. Afterwards we give as a new cycle of G, which and are common in only one edge, and is too. With doing the same process (this process) we achieve a basic algorithm. 3 Remark2.3. In the necessity proof of Theorem 2.1, we show a sequence with respect to (* ). and the Growing process of sequence is not denoted.We use Theorem 2.1. Example2.6. Note to Figure (5-a). We know already this graph is Hamiltonian. ''Figure(5-a), dodecahedron'' ''Figure(5-b) sequence with the equivalent condition of theorem 2.1'
• 8.
  International Journal onApplications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC) Vol.6, No.3, September 2014 4 In Figure (5-b), sequence is taken, such that: : ! #$%%'%(%)% *: + + , -:+ , ++ .$'()%%%' /: ! Which it has the initial cycle . At each step, we mark by a little straight line the edge shared of two consecutive cycle. As you have understand so far, providing the conditions of Theorem 2.1, is required to test cycles Dependent to single-edges(the same members). Thus for the design of more advanced algorithm Respect to the Algorithm 2.5, you must select the with restrictions. One of these ways we denote the following. Algorithm2.7. Firstly we define a set A; A = { : is a minimal cycle, that it has an edge ith of E(G)} Remark2.8. We note that A , and every element of A is not unique . Also every element of can be Considered as a Hamiltonian graph on its vertices set, which if this cycle has chords, we must consider it as a sequence of smaller cycles with Algorithm 2.5. By doing the same process, a sequence of A members must be achieved for the smaller cycles. Continue of the Algorithm2.7. Now, we study the equivalent condition of Theorem 2.1 over members of A. If a spanning sequence of A is found, then G is Hamiltonian. If not, let S be a maximum sequence and C is a generated cycle by method of Algorithm 2.5 in S. Afterwards C is a member of A too, by deleting chords of C. At present, we study again the condition (* ) over members of the redefined collection A and we use the above method. Finally either a spanning cycle is found by doing this process, and so G is a Hamiltonian graph, or a longest cycle where it is not spanning. This is obvious, if G is a Hamiltonian graph, we can find a spanning cycle by method of Algorithm 2.7, but we must verify the following theorem. Theorem2.9. If C is the longest and not spanning cycle of G, which it is built by the method of Algorithm 2.7, then G is not Hamiltonian. Proof. By contradiction, let G be a Hamiltonian graph. Thus it has a spanning cycle as , and this cycle is not built by the method of Algorithm 2.7. Therefore has at least one chord (because C is notspanning). Now we give a sequence of the A members, as in the method of Algorithm 2.5.
• 9.
  International Journal onApplications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC) Vol.6, No.3, September 2014 Afterwards with the second part of Remark 2.8, G has a cycle, which it is built as in the method of Algorithm 2.7. This is contrary to the primary assumption. Result2.10. If we may not prove that G is Hamiltonian as in the method of Algorithm 2.7, then G is not Hamiltonian. 5 Proof. This clear. ''Figure(6), Hershel graph and two of the most longest sequence with length 4''
• 10.
  International Journal onApplications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC) Vol.6, No.3, September 2014 Example2.11. Note to the Figure (6), that it has a Herschel graph G (already we know that it is not Hamiltonian) and three of the longest sequences, but these sequences are not spanning, then G is not Hamiltonian by the Algorithm 2.7. And so G is not Hamiltonian with Result 2.10. Explanation2.12. Clearly finding the longest sequence is the most important section of the method of Remark 2.7. [1] A.J. Bondy, U.S.R. Murty, Graph Theory with Applications, American Elsevier, New York, 1976. [2] Douglas B.West, Introduction to Graph Theory, University of Illinois Urbana, First Indian Reprint, 6 REFERENCES 2002. [3] Kewen Zhao, Hong-Jian Lai, Yehong Shao, New sufficient condition for Hamiltonian graphs, Applied Mathematics Letters 20 (2007) 116 122.