Log in

Relevant bibliographies by topics / Hamiltonian graphs / Journal articles

To see the other types of publications on this topic, follow the link: Hamiltonian graphs.

Journal articles on the topic 'Hamiltonian graphs'

Author: Grafiati

Published: 7 September 2021

Last updated: 25 April 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Hamiltonian graphs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Nikoghosyan, Zh G. "Disconnected Forbidden Subgraphs, Toughness and Hamilton Cycles." ISRN Combinatorics 2013 (March 10, 2013): 1–4. http://dx.doi.org/10.1155/2013/673971.

Full text

Abstract:

In 1974, Goodman and Hedetniemi proved that every 2-connected -free graph is hamiltonian. This result gave rise many other conditions for Hamilton cycles concerning various pairs and triples of forbidden connected subgraphs under additional connectivity conditions. In this paper we investigate analogous problems when forbidden subgraphs are disconnected which affects more global structures in graphs such as tough structures instead of traditional connectivity structures. In 1997, it was proved that a single forbidden connected subgraph in 2-connected graphs can create only a trivial class of hamiltonian graphs (complete graphs) with . In this paper we prove that a single forbidden subgraph can create a non trivial class of hamiltonian graphs if is disconnected: every -free graph either is hamiltonian or belongs to a well defined class of non hamiltonian graphs; every 1-tough -free graph is hamiltonian. We conjecture that every 1-tough -free graph is hamiltonian and every 1-tough -free graph is hamiltonian.

APA, Harvard, Vancouver, ISO, and other styles

2

Adame, Luis Enrique, Luis Manuel Rivera, and Ana Laura Trujillo-Negrete. "Hamiltonicity of Token Graphs of Some Join Graphs." Symmetry 13, no. 6 (June 16, 2021): 1076. http://dx.doi.org/10.3390/sym13061076.

Full text

Abstract:

Let G be a simple graph of order n with vertex set V(G) and edge set E(G), and let k be an integer such that 1≤k≤n−1. The k-token graph G{k} of G is the graph whose vertices are the k-subsets of V(G), where two vertices A and B are adjacent in G{k} whenever their symmetric difference A▵B, defined as (A∖B)∪(B∖A), is a pair {a,b} of adjacent vertices in G. In this paper we study the Hamiltonicity of the k-token graphs of some join graphs. We provide an infinite family of graphs, containing Hamiltonian and non-Hamiltonian graphs, for which their k-token graphs are Hamiltonian. Our result provides, to our knowledge, the first family of non-Hamiltonian graphs for which it is proven the Hamiltonicity of their k-token graphs, for any 2<k<n−2.

APA, Harvard, Vancouver, ISO, and other styles

3

Paulraja, P., and Kumar Sampath. "On hamiltonian decompositions of tensor products of graphs." Applicable Analysis and Discrete Mathematics 13, no. 1 (2019): 178–202. http://dx.doi.org/10.2298/aadm170803003p.

Full text

Abstract:

Finding a hamiltonian decomposition of G is one of the challenging problems in graph theory. We do not know for what classes of graphs G and H, their tensor product G x H is hamiltonian decomposable. In this paper, we have proved that, if G is a hamiltonian decomposable circulant graph with certain properties and H is a hamiltonian decomposable multigraph, then G x H is hamiltonian decomposable. In particular, tensor products of certain sparse hamiltonian decomposable circulant graphs are hamiltonian decomposable.

APA, Harvard, Vancouver, ISO, and other styles

4

Hopkins, Brian. "Hamiltonian paths on Platonic graphs." International Journal of Mathematics and Mathematical Sciences 2004, no. 30 (2004): 1613–16. http://dx.doi.org/10.1155/s0161171204307118.

Full text

Abstract:

We develop a combinatorial method to show that the dodecahedron graph has, up to rotation and reflection, a unique Hamiltonian cycle. Platonic graphs with this property are called topologically uniquely Hamiltonian. The same method is used to demonstrate topologically distinct Hamiltonian cycles on the icosahedron graph and to show that a regular graph embeddable on the2-holed torus is topologically uniquely Hamiltonian.

APA, Harvard, Vancouver, ISO, and other styles

5

SHERMAN, DAVID, MING TSAI, CHENG-KUAN LIN, LÁSZLÓ LIPTÁK, EDDIE CHENG, JIMMY J. M. TAN, and LIH-HSING HSU. "4-ORDERED HAMILTONICITY FOR SOME CHORDAL RING GRAPHS." Journal of Interconnection Networks 11, no. 03n04 (September 2010): 157–74. http://dx.doi.org/10.1142/s0219265910002787.

Full text

Abstract:

A graph G is k-ordered if for any sequence of k distinct vertices of G, there exists a cycle in G containing these k vertices in the specified order. It is k-ordered Hamiltonian if, in addition, the required cycle is Hamiltonian. The question of the existence of an infinite class of 3-regular 4-ordered Hamiltonian graphs was posed in 1997 by Ng and Schultz.13At the time, the only known examples were K4and K3,3. Some progress was made in 2008 by Mészáros,12when the Peterson graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered Hamiltonian; moreover, an infinite class of 3-regular 4-ordered graphs was found. In 2010 a subclass of generalized Petersen graphs was shown to be 4-ordered by Hsu et al.,10with an infinite subset of this subclass being 4-ordered Hamiltonian, thus answering the open question. In this paper we find another infinite class of 3-regular 4-ordered Hamiltonian graphs, part of a subclass of the chordal ring graphs. In addition, we classify precisely which of these graphs are 4-ordered Hamiltonian.

APA, Harvard, Vancouver, ISO, and other styles

6

Takaoka, Asahi. "Complexity of Hamiltonian Cycle Reconfiguration." Algorithms 11, no. 9 (September 17, 2018): 140. http://dx.doi.org/10.3390/a11090140.

Full text

Abstract:

The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles C 0 and C t of a graph G, whether there is a sequence of Hamiltonian cycles C 0 , C 1 , … , C t such that C i can be obtained from C i − 1 by a switch for each i with 1 ≤ i ≤ t , where a switch is the replacement of a pair of edges u v and w z on a Hamiltonian cycle with the edges u w and v z of G, given that u w and v z did not appear on the cycle. We show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete, settling an open question posed by Ito et al. (2011) and van den Heuvel (2013). More precisely, we show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete for chordal bipartite graphs, strongly chordal split graphs, and bipartite graphs with maximum degree 6. Bipartite permutation graphs form a proper subclass of chordal bipartite graphs, and unit interval graphs form a proper subclass of strongly chordal graphs. On the positive side, we show that, for any two Hamiltonian cycles of a bipartite permutation graph and a unit interval graph, there is a sequence of switches transforming one cycle to the other, and such a sequence can be obtained in linear time.

APA, Harvard, Vancouver, ISO, and other styles

7

Bueno, Letícia, Luerbio Faria, Figueiredo De, and Fonseca Da. "Hamiltonian paths in odd graphs." Applicable Analysis and Discrete Mathematics 3, no. 2 (2009): 386–94. http://dx.doi.org/10.2298/aadm0902386b.

Full text

Abstract:

Lov?sz conjectured that every connected vertex-transitive graph has a Hamiltonian path. The odd graphs Ok form a well-studied family of connected, k-regular, vertex-transitive graphs. It was previously known that Ok has Hamiltonian paths for k ? 14. A direct computation of Hamiltonian paths in Ok is not feasible for large values of k, because Ok has (2k - 1, k - 1) vertices and k/2 (2k - 1, k - 1) edges. We show that Ok has Hamiltonian paths for 15 ? k ? 18. Instead of directly running any heuristics, we use existing results on the middle levels problem, therefore further relating these two fundamental problems, namely finding a Hamiltonian path in the odd graph and finding a Hamiltonian cycle in the corresponding middle levels graph. We show that further improved results for the middle levels problem can be used to find Hamiltonian paths in Ok for larger values of k.

APA, Harvard, Vancouver, ISO, and other styles

8

Keshavarz-Kohjerdi, Fatemeh, and Ruo-Wei Hung. "Finding Hamiltonian and Longest (s,t)-Paths of C-Shaped Supergrid Graphs in Linear Time." Algorithms 15, no. 2 (February 13, 2022): 61. http://dx.doi.org/10.3390/a15020061.

Full text

Abstract:

A graph is called Hamiltonian connected if it contains a Hamiltonian path between any two distinct vertices. In the past, we proved the Hamiltonian path and cycle problems for general supergrid graphs to be NP-complete. However, they are still open for solid supergrid graphs. In this paper, first we will verify the Hamiltonian cycle property of C-shaped supergrid graphs, which are a special case of solid supergrid graphs. Next, we show that C-shaped supergrid graphs are Hamiltonian connected except in a few conditions. For these excluding conditions of Hamiltonian connectivity, we compute their longest paths. Then, we design a linear-time algorithm to solve the longest path problem in these graphs. The Hamiltonian connectivity of C-shaped supergrid graphs can be applied to compute the optimal stitching trace of computer embroidery machines, and construct the minimum printing trace of 3D printers with a C-like component being printed.

APA, Harvard, Vancouver, ISO, and other styles

9

Shabbir, Ayesha, Muhammad Faisal Nadeem, and Tudor Zamfirescu. "The Property of Hamiltonian Connectedness in Toeplitz Graphs." Complexity 2020 (March 12, 2020): 1–6. http://dx.doi.org/10.1155/2020/5608720.

Full text

Abstract:

A spanning path in a graph G is called a Hamiltonian path. To determine which graphs possess such paths is an NP-complete problem. A graph G is called Hamiltonian-connected if any two vertices of G are connected by a Hamiltonian path. We consider here the family of Toeplitz graphs. About them, it is known only for n=3 that Tnp,q is Hamiltonian-connected, while some particular cases of Tnp,q,r for p=1 and q=2,3,4 have also been investigated regarding Hamiltonian connectedness. Here, we prove that the nonbipartite Toeplitz graph Tn1,q,r is Hamiltonian-connected for all 1<q<r<n and n≥5r−2.

APA, Harvard, Vancouver, ISO, and other styles

10

Lynch, Mark A. M. "Creating recreational Hamiltonian cycle problems." Mathematical Gazette 88, no. 512 (July 2004): 215–18. http://dx.doi.org/10.1017/s0025557200174935.

Full text

Abstract:

In this paper graphs that contain unique Hamiltonian cycles are introduced. The graphs are of arbitrary size and dense in the sense that their average vertex degree is greater than half the number of vertices that make up the graph. The graphs can be used to generate challenging puzzles. The problem is particularly challenging when the graph is large and the ‘method’ of solution is unknown to the solver.

APA, Harvard, Vancouver, ISO, and other styles

11

Thomassen, Carsten. "On the Number of Hamiltonian Cycles in Bipartite Graphs." Combinatorics, Probability and Computing 5, no. 4 (December 1996): 437–42. http://dx.doi.org/10.1017/s0963548300002182.

Full text

Abstract:

We prove that a bipartite uniquely Hamiltonian graph has a vertex of degree 2 in each color class. As consequences, every bipartite Hamiltonian graph of minimum degree d has at least 21−dd! Hamiltonian cycles, and every bipartite Hamiltonian graph of minimum degree at least 4 and girth g has at least (3/2)g/8 Hamiltonian cycles. We indicate how the existence of more than one Hamiltonian cycle may lead to a general reduction method for Hamiltonian graphs.

APA, Harvard, Vancouver, ISO, and other styles

12

Malik, Shabnam, Ahmad Mahmood Qureshi, and Tudor Zamfirescu. "Hamiltonian Properties of Generalized Halin Graphs." Canadian Mathematical Bulletin 52, no. 3 (September 1, 2009): 416–23. http://dx.doi.org/10.4153/cmb-2009-045-6.

Full text

Abstract:

AbstractA Halin graph is a graph H = T ∪ C, where T is a tree with no vertex of degree two, and C is a cycle connecting the end-vertices of T in the cyclic order determined by a plane embedding of T. In this paper, we define classes of generalized Halin graphs, called k-Halin graphs, and investigate their Hamiltonian properties.

APA, Harvard, Vancouver, ISO, and other styles

13

Thirusangu, K., and K. Rangarajan. "Marked graphs and hamiltonian graphs." Microelectronics Reliability 37, no. 8 (August 1997): 1243–50. http://dx.doi.org/10.1016/s0026-2714(97)00001-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Basic, Milan. "Hamiltonian properties on a class of circulant interconnection networks." Filomat 32, no. 1 (2018): 71–85. http://dx.doi.org/10.2298/fil1801071b.

Full text

Abstract:

Classes of circulant graphs play an important role in modeling interconnection networks in parallel and distributed computing. They also find applications in modeling quantum spin networks supporting the perfect state transfer. It has been noticed that unitary Cayley graphs as a class of circulant graphs possess many good properties such as small diameter, mirror symmetry, recursive structure, regularity, etc. and therefore can serve as a model for efficient interconnection networks. In this paper we go a step further and analyze some other characteristics of unitary Cayley graphs important for the modeling of a good interconnection network. We show that all unitary Cayley graphs are hamiltonian. More precisely, every unitary Cayley graph is hamiltonian-laceable (up to one exception for X6) if it is bipartite, and hamiltonianconnected if it is not. We prove this by presenting an explicit construction of hamiltonian paths on Xnm using the hamiltonian paths on Xn and Xm for gcd(n,m) = 1. Moreover, we also prove that every unitary Cayley graph is bipancyclic and every nonbipartite unitary Cayley graph is pancyclic.

APA, Harvard, Vancouver, ISO, and other styles

15

Manoussakis, Yannis. "Directed hamiltonian graphs." Journal of Graph Theory 16, no. 1 (March 1992): 51–59. http://dx.doi.org/10.1002/jgt.3190160106.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Katona, D., A. Kostochka, Ya Pykh, and B. Stechkin. "Locally Hamiltonian graphs." Mathematical Notes of the Academy of Sciences of the USSR 45, no. 1 (January 1989): 25–29. http://dx.doi.org/10.1007/bf01158712.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Chen, Ya-Chen, and Z. Füredi. "Hamiltonian Kneser Graphs." Combinatorica 22, no. 1 (January 1, 2002): 147–49. http://dx.doi.org/10.1007/s004930200007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Kewen, Zhao, Hong-Jian Lai, and Ju Zhou. "Hamiltonian-connected graphs." Computers & Mathematics with Applications 55, no. 12 (June 2008): 2707–14. http://dx.doi.org/10.1016/j.camwa.2007.10.018.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Wu, Baoyindureng, and Jixiang Meng. "Hamiltonian jump graphs." Discrete Mathematics 289, no. 1-3 (December 2004): 95–106. http://dx.doi.org/10.1016/j.disc.2004.09.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Ebrahimi, Mahdi, Ali Iranmanesh, and Mohammad Ali Hosseinzadeh. "Hamiltonian character graphs." Journal of Algebra 428 (April 2015): 54–66. http://dx.doi.org/10.1016/j.jalgebra.2014.12.038.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Harary, Frank, and Uri Peled. "Hamiltonian threshold graphs." Discrete Applied Mathematics 16, no. 1 (January 1987): 11–15. http://dx.doi.org/10.1016/0166-218x(87)90050-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

LIU, RUIFANG, XUE DU, and HUICAI JIA. "WIENER INDEX ON TRACEABLE AND HAMILTONIAN GRAPHS." Bulletin of the Australian Mathematical Society 94, no. 3 (August 30, 2016): 362–72. http://dx.doi.org/10.1017/s0004972716000447.

Full text

Abstract:

We give sufficient conditions for a graph to be traceable and Hamiltonian in terms of the Wiener index and the complement of the graph, which correct and extend the result of Yang [‘Wiener index and traceable graphs’, Bull. Aust. Math. Soc.88 (2013), 380–383]. We also present sufficient conditions for a bipartite graph to be traceable and Hamiltonian in terms of its Wiener index and quasicomplement. Finally, we give sufficient conditions for a graph or a bipartite graph to be traceable and Hamiltonian in terms of its distance spectral radius.

APA, Harvard, Vancouver, ISO, and other styles

23

Nebeský, Ladislav. "Hamiltonian colorings of graphs with long cycles." Mathematica Bohemica 128, no. 3 (2003): 263–75. http://dx.doi.org/10.21136/mb.2003.134180.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Zheng, Wei, Hajo Broersma, and Ligong Wang. "Toughness, Forbidden Subgraphs and Pancyclicity." Graphs and Combinatorics 37, no. 3 (February 19, 2021): 839–66. http://dx.doi.org/10.1007/s00373-021-02284-y.

Full text

Abstract:

AbstractMotivated by several conjectures due to Nikoghosyan, in a recent article due to Li et al., the aim was to characterize all possible graphs H such that every 1-tough H-free graph is hamiltonian. The almost complete answer was given there by the conclusion that every proper induced subgraph H of $$K_1\cup P_4$$ K 1 ∪ P 4 can act as a forbidden subgraph to ensure that every 1-tough H-free graph is hamiltonian, and that there is no other forbidden subgraph with this property, except possibly for the graph $$K_1\cup P_4$$ K 1 ∪ P 4 itself. The hamiltonicity of 1-tough $$K_1\cup P_4$$ K 1 ∪ P 4 -free graphs, as conjectured by Nikoghosyan, was left there as an open case. In this paper, we consider the stronger property of pancyclicity under the same condition. We find that the results are completely analogous to the hamiltonian case: every graph H such that any 1-tough H-free graph is hamiltonian also ensures that every 1-tough H-free graph is pancyclic, except for a few specific classes of graphs. Moreover, there is no other forbidden subgraph having this property. With respect to the open case for hamiltonicity of 1-tough $$K_1\cup P_4$$ K 1 ∪ P 4 -free graphs we give infinite families of graphs that are not pancyclic.

APA, Harvard, Vancouver, ISO, and other styles

25

Pirzada, S., and Mushtaq A. Shah. "Construction of Barnette graphs whose large subgraphs are non-Hamiltonian." Acta Universitatis Sapientiae, Mathematica 11, no. 2 (December 1, 2019): 363–70. http://dx.doi.org/10.2478/ausm-2019-0026.

Full text

Abstract:

Abstract Barnette’s conjecture states that every three connected cubic bipartite planar graph (CPB3C) is Hamiltonian. In this paper we show the existence of a family of CPB3C Hamiltonian graphs in which large and large subgraphs are non-Hamiltonian.

APA, Harvard, Vancouver, ISO, and other styles

26

ZHONG, LIANG. "THE COMPLEXITY OF THOMASON’S ALGORITHM FOR FINDING A SECOND HAMILTONIAN CYCLE." Bulletin of the Australian Mathematical Society 98, no. 1 (May 3, 2018): 18–26. http://dx.doi.org/10.1017/s0004972718000242.

Full text

Abstract:

By Smith’s theorem, if a cubic graph has a Hamiltonian cycle, then it has a second Hamiltonian cycle. Thomason [‘Hamilton cycles and uniquely edge-colourable graphs’, Ann. Discrete Math.3 (1978), 259–268] gave a simple algorithm to find the second cycle. Thomassen [private communication] observed that if there exists a polynomially bounded algorithm for finding a second Hamiltonian cycle in a cubic cyclically 4-edge connected graph $G$, then there exists a polynomially bounded algorithm for finding a second Hamiltonian cycle in any cubic graph $G$. In this paper we present a class of cyclically 4-edge connected cubic bipartite graphs $G_{i}$ with $16(i+1)$ vertices such that Thomason’s algorithm takes $12(2^{i}-1)+3$ steps to find a second Hamiltonian cycle in $G_{i}$.

APA, Harvard, Vancouver, ISO, and other styles

27

Shukor, Noorsufia Abd, Tahir Ahmad, Amidora Idris, Siti Rahmah Awang, and Amirul Aizad Ahmad Fuad. "Graph of Fuzzy Topographic Topological Mapping in relation to k-Fibonacci Sequence." Journal of Mathematics 2021 (August 24, 2021): 1–10. http://dx.doi.org/10.1155/2021/7519643.

Full text

Abstract:

A generated n-sequence of fuzzy topographic topological mapping, FTTM n , is a combination of n number of FTTM’s graphs. An assembly graph is a graph whereby its vertices have valency of one or four. A Hamiltonian path is a path that visits every vertex of the graph exactly once. In this paper, we prove that assembly graphs exist in FTTM n and establish their relations to the Hamiltonian polygonal paths. Finally, the relation between the Hamiltonian polygonal paths induced from FTTM n to the k-Fibonacci sequence is established and their upper and lower bounds’ number of paths is determined.

APA, Harvard, Vancouver, ISO, and other styles

28

Sumitra Devi, M. R., and A. Girisha. "Hamiltonian Laceability in Book Graphs." Journal of Physics: Conference Series 2161, no. 1 (January 1, 2022): 012032. http://dx.doi.org/10.1088/1742-6596/2161/1/012032.

Full text

Abstract:

Abstract A connected graph network G is a Hamilton-t-laceable (Hamilton- t*-laceable) if Ǝ in G a Hamilton path connecting each pair (at least one pair) of vertices at distance ‘t’ in G such that 1 ≤ t ≤ diameter (G). In this paper, we discuss the f-edge-Hamilton-t-laceability of Book and stacked Book graphs, where 1 ≤ t ≤ diameter (G).

APA, Harvard, Vancouver, ISO, and other styles

29

Zhang, Xinhong, and Ruijuan Li. "The H-force sets of the graphs satisfying the condition of Ore’s theorem." Open Mathematics 18, no. 1 (July 21, 2020): 771–80. http://dx.doi.org/10.1515/math-2020-0039.

Full text

Abstract:

Abstract Let G be a Hamiltonian graph. A nonempty vertex set X\subseteq V(G) is called a Hamiltonian cycle enforcing set (in short, an H-force set) of G if every X-cycle of G (i.e., a cycle of G containing all vertices of X) is a Hamiltonian cycle. For the graph G, h(G) (called the H-force number of G) is the smallest cardinality of an H-force set of G. Ore’s theorem states that an n-vertex graph G is Hamiltonian if d(u)+d(v)\ge n for every pair of nonadjacent vertices u,v of G. In this article, we study the H-force sets of the graphs satisfying the condition of Ore’s theorem, show that the H-force number of these graphs is possibly n, or n-2 , or \frac{n}{2} and give a classification of these graphs due to the H-force number.

APA, Harvard, Vancouver, ISO, and other styles

30

LIN, CHENG-KUAN, TUNG-YANG HO, JIMMY J. M. TAN, and LIH-HSING HSU. "FAULT-TOLERANT HAMILTONIAN LACEABILITY AND FAULT-TOLERANT CONDITIONAL HAMILTONIAN FOR BIPARTITE HYPERCUBE-LIKE NETWORKS." Journal of Interconnection Networks 10, no. 03 (September 2009): 243–51. http://dx.doi.org/10.1142/s0219265909002558.

Full text

Abstract:

A bipartite graph G is hamiltonian laceable if there is a hamiltonian path between any two vertices of G from distinct vertex bipartite sets. A bipartite graph G is k-edge fault-tolerant hamiltonian laceable if G - F is hamiltonian laceable for every F ⊆ E(G) with |F| ≤ k. A graph G is k-edge fault-tolerant conditional hamiltonian if G - F is hamiltonian for every F ⊆ E(G) with |F| ≤ k and δ(G - F) ≥ 2. Let G0 = (V0, E0) and G1 = (V1, E1) be two disjoint graphs with |V0| = |V1|. Let Er = {(v,ɸ(v)) | v ϵ V0,ɸ(v) ϵ V1, and ɸ: V0 → V1 is a bijection}. Let G = G0 ⊕ G1 = (V0 ⋃ V1, E0 ⋃ E1 ⋃ Er). The set of n-dimensional hypercube-like graphHn is defined recursively as (a) H1 = K2, K2 is the complete graph with two vertices, and (b) if G0 and G1 are in Hn, then G = G0 ⊕ G1 is in Hn+1. Let Bn be the set of graphs G where G is bipartite and G ϵ Hn. In this paper, we show that every graph in Bn is (n - 2)-edge fault-tolerant hamiltonian laceable if n ≥ 2 and every graph in Bn is (2n - 5)-edge fault-tolerant conditional hamiltonian if n ≥ 3.

APA, Harvard, Vancouver, ISO, and other styles

31

Lanel, G. H. J., H. K. Pallage, J. K. Ratnayake, S. Thevasha, and B. A. K. Welihinda. "A survey on Hamiltonicity in Cayley graphs and digraphs on different groups." Discrete Mathematics, Algorithms and Applications 11, no. 05 (October 2019): 1930002. http://dx.doi.org/10.1142/s1793830919300029.

Full text

Abstract:

Lovász had posed a question stating whether every connected, vertex-transitive graph has a Hamilton path in 1969. There is a growing interest in solving this longstanding problem and still it remains widely open. In fact, it was known that only five vertex-transitive graphs exist without a Hamiltonian cycle which do not belong to Cayley graphs. A Cayley graph is the subclass of vertex-transitive graph, and in view of the Lovász conjecture, the attention has focused more toward the Hamiltonicity of Cayley graphs. This survey will describe the current status of the search for Hamiltonian cycles and paths in Cayley graphs and digraphs on different groups, and discuss the future direction regarding famous conjecture.

APA, Harvard, Vancouver, ISO, and other styles

32

Andeelić, Milica, Domingos M. Cardoso, and António Pereira. "A sharp lower bound on the signless Laplacian index of graphs with (κ,τ)-regular sets." Special Matrices 6, no. 1 (February 1, 2018): 68–76. http://dx.doi.org/10.1515/spma-2018-0007.

Full text

Abstract:

Abstract A new lower bound on the largest eigenvalue of the signless Laplacian spectra for graphs with at least one (κ,τ)regular set is introduced and applied to the recognition of non-Hamiltonian graphs or graphs without a perfect matching. Furthermore, computational experiments revealed that the introduced lower bound is better than the known ones. The paper also gives sufficient condition for a graph to be non Hamiltonian (or without a perfect matching).

APA, Harvard, Vancouver, ISO, and other styles

33

Wei, Bing. "Hamiltonian paths and hamiltonian connectivity in graphs." Discrete Mathematics 121, no. 1-3 (October 1993): 223–28. http://dx.doi.org/10.1016/0012-365x(93)90555-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Bell, F. K., and P. Rowlinson. "On the index of tricyclic Hamiltonian graphs." Proceedings of the Edinburgh Mathematical Society 33, no. 2 (June 1990): 233–40. http://dx.doi.org/10.1017/s0013091500018150.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

PANDA, B. S., VIJAY NATARAJAN, and SAJAL K. DAS. "PARALLEL ALGORITHMS FOR HAMILTONIAN 2-SEPARATOR CHORDAL GRAPHS." Parallel Processing Letters 12, no. 01 (March 2002): 51–64. http://dx.doi.org/10.1142/s0129626402000823.

Full text

Abstract:

In this paper we propose a parallel algorithm to construct a one-sided monotone polygon from a Hamiltonian 2-separator chordal graph. The algorithm requires O( log n) time and O(n) processors on the CREW PRAM model, where n is the number of vertices and m is the number of edges in the graph. We also propose parallel algorithms to recognize Hamiltonian 2-separator chordal graphs and to construct a Hamiltonian cycle in such a graph. They run in O( log 2 n) time using O(mn) processors on the CRCW PRAM model and O( log 2 n) time using O(m) processors on the CREW PRAM model, respectively.

APA, Harvard, Vancouver, ISO, and other styles

36

Arguello, Anahy Santiago, and Juan José Montellano-Ballesteros. "Hamiltonian normal Cayley graphs." Discussiones Mathematicae Graph Theory 39, no. 3 (2019): 731. http://dx.doi.org/10.7151/dmgt.2214.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Manesh, Silviya. "K-ordered Hamiltonian Graphs." Indian Journal of Science and Technology 7, is3 (March 22, 2014): 28–29. http://dx.doi.org/10.17485/ijst/2014/v7sp3.8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Chang, Gerard J., and Xuding Zhu. "Pseudo-Hamiltonian-connected graphs." Discrete Applied Mathematics 100, no. 3 (March 2000): 145–53. http://dx.doi.org/10.1016/s0166-218x(99)00181-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Funk, M., Bill Jackson, D. Labbate, and J. Sheehan. "2-Factor hamiltonian graphs." Journal of Combinatorial Theory, Series B 87, no. 1 (January 2003): 138–44. http://dx.doi.org/10.1016/s0095-8956(02)00031-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Heuberger, Clemens. "On hamiltonian Toeplitz graphs." Discrete Mathematics 245, no. 1-3 (February 2002): 107–25. http://dx.doi.org/10.1016/s0012-365x(01)00136-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Xiong, Liming, and Zhanhong Liu. "Hamiltonian iterated line graphs." Discrete Mathematics 256, no. 1-2 (September 2002): 407–22. http://dx.doi.org/10.1016/s0012-365x(01)00442-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

LIU, ZHENHONG, YONGJIN ZHU, and FENG TIAN. "Hamiltonian Cycles in Graphs." Annals of the New York Academy of Sciences 576, no. 1 Graph Theory (December 1989): 367–76. http://dx.doi.org/10.1111/j.1749-6632.1989.tb16419.x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Jeng-Jung, Wang, Hung Chun-Nan, and Hsu Lih-Hsing. "Optimal 1-hamiltonian graphs." Information Processing Letters 65, no. 3 (February 1998): 157–61. http://dx.doi.org/10.1016/s0020-0190(98)00004-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Yang, Zhenqi. "On F-Hamiltonian graphs." Discrete Mathematics 196, no. 1-3 (February 1999): 281–86. http://dx.doi.org/10.1016/s0012-365x(98)00216-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Renzema, Willem, and Ping Zhang. "Hamiltonian labelings of graphs." Involve, a Journal of Mathematics 2, no. 1 (March 18, 2009): 95–114. http://dx.doi.org/10.2140/involve.2009.2.95.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Ng, Lenhard, and Michelle Schultz. "k-ordered Hamiltonian graphs." Journal of Graph Theory 24, no. 1 (January 1997): 45–57. http://dx.doi.org/10.1002/(sici)1097-0118(199701)24:1<45::aid-jgt6>3.0.co;2-j.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Wei, Bing, and Yongjin Zhu. "Hamiltonian ?-factors in graphs." Journal of Graph Theory 25, no. 3 (July 1997): 217–27. http://dx.doi.org/10.1002/(sici)1097-0118(199707)25:3<217::aid-jgt5>3.0.co;2-o.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Kierstead, H. A., G. N. S�rk�zy, and S. M. Selkow. "Onk-ordered Hamiltonian graphs." Journal of Graph Theory 32, no. 1 (September 1999): 17–25. http://dx.doi.org/10.1002/(sici)1097-0118(199909)32:1<17::aid-jgt2>3.0.co;2-g.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Lai, Hong-Jian, and Yehong Shao. "Ons-Hamiltonian Line Graphs." Journal of Graph Theory 74, no. 3 (January 2, 2013): 344–58. http://dx.doi.org/10.1002/jgt.21713.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Paoli, M., W. W. Wong, and C. K. Wong. "Minimumk-hamiltonian graphs, II." Journal of Graph Theory 10, no. 1 (1986): 79–95. http://dx.doi.org/10.1002/jgt.3190100111.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!