Log in

Relevant bibliographies by topics / Graph theory. Hamiltonian graph theory / Journal articles

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

Journal articles on the topic 'Graph theory. Hamiltonian graph theory'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 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 'Graph theory. Hamiltonian graph theory.'

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

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

2

Ceulemans, A., E. Lijnen, P. W. Fowler, R. B. Mallion, and T. Pisanski. "Graph theory and the Jahn–Teller theorem." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 468, no. 2140 (2011): 971–89. http://dx.doi.org/10.1098/rspa.2011.0508.

Full text

Abstract:

The Jahn–Teller (JT) theorem predicts spontaneous symmetry breaking and lifting of degeneracy in degenerate electronic states of (nonlinear) molecular and solid-state systems. In these cases, degeneracy is lifted by geometric distortion. Molecular problems are often modelled using spectral theory for weighted graphs, and the present paper turns this process around and reformulates the JT theorem for general vertex- and edge-weighted graphs themselves. If the eigenvectors and eigenvalues of a general graph are considered as orbitals and energy levels (respectively) to be occupied by electrons, then degeneracy of states can be resolved by a non-totally symmetric re-weighting of edges and, where necessary, vertices. This leads to the conjecture that whenever the spectrum of a graph contains a set of bonding or anti-bonding degenerate eigenvalues, the roots of the Hamiltonian matrix over this set will show a linear dependence on edge distortions, which has the effect of lifting the degeneracy. When the degenerate level is non-bonding, distortions of vertex weights have to be included to obtain a full resolution of the eigenspace of the degeneracy. Explicit treatments are given for examples of the octahedral graph, where the degeneracy to be lifted is forced by symmetry, and the phenalenyl graph, where the degeneracy is accidental in terms of the automorphism group.

APA, Harvard, Vancouver, ISO, and other styles

3

Thomassen, Carsten. "On the Number of Hamiltonian Cycles in Bipartite Graphs." Combinatorics, Probability and Computing 5, no. 4 (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

4

Takaoka, Asahi. "Complexity of Hamiltonian Cycle Reconfiguration." Algorithms 11, no. 9 (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

5

Mickewich, Tom. "HAMILTONIAN GRAPHS – COMPARING FOUR SUFFICIENT CONDITIONS IN AN UNDERGRADUATE GRAPH THEORY COURSE." PRIMUS 4, no. 2 (1994): 173–81. http://dx.doi.org/10.1080/10511979408965747.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Montgomery, Richard. "Hamiltonicity in random directed graphs is born resilient." Combinatorics, Probability and Computing 29, no. 6 (2020): 900–942. http://dx.doi.org/10.1017/s0963548320000140.

Full text

Abstract:

AbstractLet $\{D_M\}_{M\geq 0}$ be the n-vertex random directed graph process, where $D_0$ is the empty directed graph on n vertices, and subsequent directed graphs in the sequence are obtained by the addition of a new directed edge uniformly at random. For each $$\varepsilon > 0$$ , we show that, almost surely, any directed graph $D_M$ with minimum in- and out-degree at least 1 is not only Hamiltonian (as shown by Frieze), but remains Hamiltonian when edges are removed, as long as at most $1/2-\varepsilon$ of both the in- and out-edges incident to each vertex are removed. We say such a directed graph is $(1/2-\varepsilon)$ -resiliently Hamiltonian. Furthermore, for each $\varepsilon > 0$ , we show that, almost surely, each directed graph $D_M$ in the sequence is not $(1/2+\varepsilon)$ -resiliently Hamiltonian.This improves a result of Ferber, Nenadov, Noever, Peter and Škorić who showed, for each $\varepsilon > 0$ , that the binomial random directed graph $D(n,p)$ is almost surely $(1/2-\varepsilon)$ -resiliently Hamiltonian if $p=\omega(\log^8n/n)$ .

APA, Harvard, Vancouver, ISO, and other styles

7

AMORIM, LINO, YONG–GEUN OH, and JOANA OLIVEIRA DOS SANTOS. "Exact Lagrangian submanifolds, Lagrangian spectral invariants and Aubry–Mather theory." Mathematical Proceedings of the Cambridge Philosophical Society 165, no. 3 (2017): 411–34. http://dx.doi.org/10.1017/s0305004117000561.

Full text

Abstract:

AbstractWe construct graph selectors for compact exact Lagrangians in the cotangent bundle of an orientable, closed manifold. The construction combines Lagrangian spectral invariants, developed by Oh, and results, by Abouzaid, about the Fukaya category of a cotangent bundle. We also introduce the notion of Lipschitz-exact Lagrangians and prove that these admit an appropriate generalisation of graph selector. We then, following Bernard–Oliveira dos Santos, use these results to give a new characterisation of the Aubry and Mañé sets of a Tonelli Hamiltonian and to generalise a result of Arnaud on Lagrangians invariant under the flow of such Hamiltonians.

APA, Harvard, Vancouver, ISO, and other styles

8

Broersma, H. J. "A note on K4-closures in hamiltonian graph theory." Discrete Mathematics 121, no. 1-3 (1993): 19–23. http://dx.doi.org/10.1016/0012-365x(93)90533-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Liu, Donglin, Chunxiang Wang, and Shaohui Wang. "Hamilton-connectivity of Interconnection Networks Modeled by a Product of Graphs." Applied Mathematics and Nonlinear Sciences 3, no. 2 (2018): 419–26. http://dx.doi.org/10.21042/amns.2018.2.00032.

Full text

Abstract:

AbstractThe product graph Gm *Gp of two given graphs Gm and Gp, defined by J.C. Bermond et al.[J Combin Theory, Series B 36(1984) 32-48] in the context of the so-called (Δ,D)-problem, is one interesting model in the design of large reliable networks. This work deals with sufficient conditions that guarantee these product graphs to be hamiltonian-connected. Moreover, we state product graphs for which provide panconnectivity of interconnection networks modeled by a product of graphs with faulty elements.

APA, Harvard, Vancouver, ISO, and other styles

10

BEN-SHIMON, SONNY, MICHAEL KRIVELEVICH, and BENNY SUDAKOV. "Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs." Combinatorics, Probability and Computing 20, no. 2 (2010): 173–211. http://dx.doi.org/10.1017/s0963548310000453.

Full text

Abstract:

For an increasing monotone graph propertythelocal resilienceof a graphGwith respect tois the minimalrfor which there exists a subgraphH⊆Gwith all degrees at mostr, such that the removal of the edges ofHfromGcreates a graph that does not possess. This notion, which was implicitly studied for somead hocproperties, was recently treated in a more systematic way in a paper by Sudakov and Vu. Most research conducted with respect to this distance notion focused on the binomial random graph model(n, p) and some families of pseudo-random graphs with respect to several graph properties, such as containing a perfect matching and being Hamiltonian, to name a few. In this paper we continue to explore the local resilience notion, but turn our attention to random and pseudo-randomregulargraphs of constant degree. We investigate the local resilience of the typical randomd-regular graph with respect to edge and vertex connectivity, containing a perfect matching, and being Hamiltonian. In particular, we prove that for every positive ϵ and large enough values ofd, with high probability, the local resilience of the randomd-regular graph,n, d, with respect to being Hamiltonian, is at least (1−ϵ)d/6. We also prove that for the binomial random graph model(n, p), for every positive ϵ > 0 and large enough values ofK, ifp>$\frac{K\ln n}{n}$then, with high probability, the local resilience of(n, p) with respect to being Hamiltonian is at least (1−ϵ)np/6. Finally, we apply similar techniques to positional games, and prove that ifdis large enough then, with high probability, a typical randomd-regular graphGis such that, in the unbiased Maker–Breaker game played on the edges ofG, Maker has a winning strategy to create a Hamilton cycle.

APA, Harvard, Vancouver, ISO, and other styles

11

Broersma, H. J. "On some intriguing problems in hamiltonian graph theory—a survey." Discrete Mathematics 251, no. 1-3 (2002): 47–69. http://dx.doi.org/10.1016/s0012-365x(01)00325-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Li, Hao. "Generalizations of Dirac’s theorem in Hamiltonian graph theory—A survey." Discrete Mathematics 313, no. 19 (2013): 2034–53. http://dx.doi.org/10.1016/j.disc.2012.11.025.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

LEE, CHOONGBUM, BENNY SUDAKOV, and DAN VILENCHIK. "Getting a Directed Hamilton Cycle Two Times Faster." Combinatorics, Probability and Computing 21, no. 5 (2012): 773–801. http://dx.doi.org/10.1017/s096354831200020x.

Full text

Abstract:

Consider the random graph process where we start with an empty graph on n vertices and, at time t, are given an edge et chosen uniformly at random among the edges which have not appeared so far. A classical result in random graph theory asserts that w.h.p. the graph becomes Hamiltonian at time (1/2+o(1))n log n. On the contrary, if all the edges were directed randomly, then the graph would have a directed Hamilton cycle w.h.p. only at time (1+o(1))n log n. In this paper we further study the directed case, and ask whether it is essential to have twice as many edges compared to the undirected case. More precisely, we ask if, at time t, instead of a random direction one is allowed to choose the orientation of et, then whether or not it is possible to make the resulting directed graph Hamiltonian at time earlier than n log n. The main result of our paper answers this question in the strongest possible way, by asserting that one can orient the edges on-line so that w.h.p. the resulting graph has a directed Hamilton cycle exactly at the time at which the underlying graph is Hamiltonian.

APA, Harvard, Vancouver, ISO, and other styles

14

Kirkland, Steve, Sarah Plosker, and Xiaohong Zhang. "Switching and partially switching the hypercube while maintaining perfect state transfer." Quantum Information and Computation 19, no. 7&8 (2019): 541–54. http://dx.doi.org/10.26421/qic19.7-8-1.

Full text

Abstract:

A graph is said to exhibit perfect state transfer (PST) if one of its corresponding Hamiltonian matrices, which are based on the vertex-edge structure of the graph, gives rise to PST in a quantum information-theoretic context, namely with respect to inter-qubit interactions of a quantum system. We perform various perturbations to the hypercube graph---a graph that is known to exhibit PST---to create graphs that maintain many of the same properties of the hypercube, including PST as well as the distance for which PST occurs. We show that the sensitivity with respect to readout time errors remains unaffected for the vertices involved in PST. We give motivation for when these perturbations may be physically desirable or even necessary.

APA, Harvard, Vancouver, ISO, and other styles

15

HIRANO, YOSHIYASU. "IMPROVED LOWER BOUND FOR THE NUMBER OF KNOTTED HAMILTONIAN CYCLES IN SPATIAL EMBEDDINGS OF COMPLETE GRAPHS." Journal of Knot Theory and Its Ramifications 19, no. 05 (2010): 705–8. http://dx.doi.org/10.1142/s0218216510007991.

Full text

Abstract:

We prove that every spatial embedding of the complete graph K8 contains at least 3 knotted Hamiltonian cycles, and that every spatial embedding of Kn contains at least 3(n - 1)(n - 2) ⋯ 8 knotted Hamiltonian cycles, for n > 8.

APA, Harvard, Vancouver, ISO, and other styles

16

Ma, Jingjing. "Application of DNA Nanoparticle Conjugation on the Hamiltonian Path Problem." Journal of Nanoelectronics and Optoelectronics 16, no. 3 (2021): 501–5. http://dx.doi.org/10.1166/jno.2021.2930.

Full text

Abstract:

A DNA computing algorithm is proposed in this paper. The algorithm uses the assembly of DNA/Au nanoparticle conjugation to solve an NP-complete problem in the Graph theory, the Hamiltonian Path problem. According to the algorithm, I designed the special DNA/Au nanoparticle conjugations which assembled based on a specific graph, then, a series of experimental techniques are utilized to get the final result. This biochemical algorithm can reduce the complexity of the Hamiltonian Path problem greatly, which will provide a practical way to the best use of DNA self-assembly model.

APA, Harvard, Vancouver, ISO, and other styles

17

Horák, Peter, Tomáš Kaiser, Moshe Rosenfeld, and Zdeněk Ryjáček. "The Prism Over the Middle-levels Graph is Hamiltonian." Order 22, no. 1 (2005): 73–81. http://dx.doi.org/10.1007/s11083-005-9008-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

BOSE, PROSENJIT, HAZEL EVERETT, and STEPHEN WISMATH. "PROPERTIES OF ARRANGEMENT GRAPHS." International Journal of Computational Geometry & Applications 13, no. 06 (2003): 447–62. http://dx.doi.org/10.1142/s0218195903001281.

Full text

Abstract:

An arrangement graph G is the abstract graph obtained from an arrangement of lines L, in general position by associating vertices of G with the intersection points of L, and the edges of G with the line segments joining the intersection points of L. A simple polygon (respectively path) of n sides in general position, induces a set of n lines by extension of the line segments into lines. The main results of this paper are: • Given a graph G, it is NP-Hard to determine if G is the arrangement graph of some set of lines. • There are non-Hamiltonian arrangement graphs for arrangements of six lines and for odd values of n>6 lines. • All arrangements of n lines contain a subarrangement of size [Formula: see text] with an inducing polygon. • All arrangements on n lines contain an inducing path consisting of n line segments. A Java applet implementing the algorithm for determining such a path is also provided. • All arrangements on n hyperplanes in Rd contain a simple inducing polygonal cycle of size n.

APA, Harvard, Vancouver, ISO, and other styles

19

LOERA, J. A., J. LEE, S. MARGULIES, and S. ONN. "Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz." Combinatorics, Probability and Computing 18, no. 4 (2009): 551–82. http://dx.doi.org/10.1017/s0963548309009894.

Full text

Abstract:

Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colourable, Hamiltonian, etc.) if and only if a related system of polynomial equations has a solution.For an infeasible polynomial system, the (complex) Hilbert Nullstellensatz gives a certificate that the associated combinatorial problem is infeasible. Thus, unless P = NP, there must exist an infinite sequence of infeasible instances of each hard combinatorial problem for which the minimum degree of a Hilbert Nullstellensatz certificate of the associated polynomial system grows.In the first part of the paper, we show that the minimum degree of a Nullstellensatz certificate for the non-existence of a stable set of size greater than the stability number of the graph is the stability number of the graph. Moreover, such a certificate contains at least one term per stable set of G. In contrast, for non-3-colourability, we proved that the minimum degree of a Nullstellensatz certificate is at least four. Our efforts so far have only yielded graphs with Nullstellensatz certificates of precisely that degree.In the second part of this paper, for the purpose of computation, we construct new polynomial encodings for the problems of finding in a graph its longest cycle, the largest planar subgraph, the edge-chromatic number, or the largest k-colourable subgraph. We include some applications to graph theory.

APA, Harvard, Vancouver, ISO, and other styles

20

Zarei, Mohammad Hossein, та Yahya Khalili. "Systematic study of the completeness of two-dimensional classical ϕ4 theory". International Journal of Quantum Information 15, № 07 (2017): 1750051. http://dx.doi.org/10.1142/s0219749917500514.

Full text

Abstract:

The completeness of some classical statistical mechanical (SM) models is a recent result that has been developed by quantum formalism for the partition functions. In this paper, we consider a 2D classical [Formula: see text] filed theory whose completeness has been proved in [V. Karimipour and M. H. Zarei, Phys. Rev. A 85 (2012) 032316]. We give a new and general systematic proof for the completeness of such a model where, by a few simple steps, we show how the partition function of an arbitrary classical field theory can be derived from a 2D classical [Formula: see text] model. To this end, we start from various classical field theories containing models on arbitrary lattices and also [Formula: see text] lattice gauge theories. Then we convert them to a new classical field model on a nonplanar bipartite graph with imaginary kinetic terms. After that, we show that any polynomial function of the field in the corresponding Hamiltonian can approximately be converted to a [Formula: see text] term by adding enough numbers of vertices to the bipartite graph. In the next step, we give a few graphical transformations to convert the final nonplanar graph to a 2D rectangular lattice. We also show that the number of vertices which should be added grows polynomially with the number of vertices in the original model.

APA, Harvard, Vancouver, ISO, and other styles

21

Kirilchuk, I. O., A. V. Iordanova, V. V. Yushin, and V. M. Popov. "Development of the Authors' Method for Arranging Routes for Elimination of Unauthorized Dumps." Proceedings of the Southwest State University 24, no. 2 (2020): 153–69. http://dx.doi.org/10.21869/2223-1560-2020-24-2-153-169.

Full text

Abstract:

Purpose of research is to develop a method for arraging routes for elimination of spontaneously formed unauthorized dumps on the territory of a municipal formation of a constituent entity of the Russian Federation.Methods. The development of a method for arraging routes for elimination of unauthorized dumps is based on the theory of graphs, which includes algorithms for finding the shortest path: Dijkstra's algorithm, Floyd-Warshall algorithm, Ford-Bellman algorithm, Hamiltonian cycle, etc. Having analyzed the peculiarities of using the listed algorithms, the authors have developed a method for arranging a route for the elimination of unauthorized dumps based on the Hamiltonian cycle.Results. The task of arranging a route is reduced to choosing those unauthorized dumps from the detected ones, which will be accepted as the vertices of the graph, between which it is necessary to find the shortest path. The authors' approach to the formation of a set of vertices of the graph is as follows. At the first stage, the initial and boundary conditions are set. The parking of special equipment (garbage trucks) is selected as the zero vertex of the graph, and the SMW polygon is selected as the last (nth) vertex. In this case, it should be taken in the account that after transporting waste from dumps to the place of their burial (landfill), the garbage truck must return back to the parking place. The limits taken into consideration are the maximum distance that the garbage truck can travel without refueling and the volume of the garbage truck body. Then, the closest to the starting point unauthorized dump which represents the greatest danger to the environment is chosen as the first vertex of the graph. An unauthorized dump closest to the first peak is chosen as the second, etc.. The search for vertices continues until the inequalities that take into account the given constraints are satisfied. Next, a graph, an adjacency matrix, and a route are formed. With this approach, for arranging a route, it is optimal to use the Hamiltonian cycle, which ensures finding the minimum path between all the vertices of the graph and returns to the starting point.Conclusion. Application of the authors' method for arranging routes for elimination of unauthorized dumps will make it possible to promptly clean up unauthorized dumps found in the city, which will significantly reduce the environmental load.

APA, Harvard, Vancouver, ISO, and other styles

22

Rappaport, David. "The visibility graph of congruent discs is Hamiltonian." Computational Geometry 25, no. 3 (2003): 257–65. http://dx.doi.org/10.1016/s0925-7721(02)00113-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Dumitru, Violeta. "Economical Model Based on Graph Theory for Optimization Execution Order of Automotive Products on the Manufacturing Lines Served by Robots." Applied Mechanics and Materials 822 (January 2016): 443–51. http://dx.doi.org/10.4028/www.scientific.net/amm.822.443.

Full text

Abstract:

This paper presents an economic model based on graph theory to optimize the execution order for automotive products on the manufacturing lines served by robots, so that the total manufacturing cost is minimized. The starting point is a representation of the range of automotive products with similar design attributes but with different construction requirements (material, tolerances, production volume). This representation is distinguished by a directed graph G = (X, Γ) consisting of the set X of nodes (products) and the set Γ of arcs (paths with minimal cost). In terms of mathematical optimization problem is solved by determining the minimum length Hamiltonian path in the graph, using the algorithm of Foulkes. The length of a path is obtained by adding the numbers associated with that path arcs. The model can be applied to other extreme transportation issues CIM type, such as: transportation network modeling; determining minimum distances; median problem (placing checkpoints); multi-product maximum flow problem.

APA, Harvard, Vancouver, ISO, and other styles

24

Gokan, Yusuke, Hayato Katsumata, Katsuya Nakajima, Ayaka Shimizu, and Yoshiro Yaguchi. "A note on the cross-index of a complete graph based on a linear tree." Journal of Knot Theory and Its Ramifications 27, no. 11 (2018): 1843010. http://dx.doi.org/10.1142/s0218216518430101.

Full text

Abstract:

In this paper, it is shown that a complete graph with [Formula: see text] vertices has an optimal diagram, i.e. a diagram whose crossing number equals the value of Guy’s formula, with a free maximal linear tree and without free Hamiltonian cycles for any odd integer [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

25

Bauer, Douglas, and Edward Schmeichel. "Hamiltonian degree conditions which imply a graph is pancyclic." Journal of Combinatorial Theory, Series B 48, no. 1 (1990): 111–16. http://dx.doi.org/10.1016/0095-8956(90)90133-k.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Maruyama, Koji, Daniel Burgarth, Akihito Ishizaki, Takeji Takui, and K. Birgitta Whaley. "Application of indirect Hamiltonian tomography to complex systems with short coherence times." Quantum Information and Computation 12, no. 9&10 (2012): 763–74. http://dx.doi.org/10.26421/qic12.9-10-3.

Full text

Abstract:

The identification of parameters in the Hamiltonian that describes complex many-body quantum systems is generally a very hard task. Recent attention has focused on such problems of Hamiltonian tomography for networks constructed with two-level systems. For open quantum systems, the fact that injected signals are likely to decay before they accumulate sufficient information for parameter estimation poses additional challenges. In this paper, we consider use of the gateway approach to Hamiltonian tomography \cite{Burgarth2009,Burgarth2009a} to complex quantum systems with a limited set of state preparation and measurement probes. We classify graph properties of networks for which the Hamiltonian may be estimated under equivalent conditions on state preparation and measurement. We then examine the extent to which the gateway approach may be applied to estimation of Hamiltonian parameters for network graphs with non-trivial topologies mimicking biomolecular systems.

APA, Harvard, Vancouver, ISO, and other styles

27

Sattath, Or, Siddhardh C. Morampudi, Chris R. Laumann, and Roderich Moessner. "When a local Hamiltonian must be frustration-free." Proceedings of the National Academy of Sciences 113, no. 23 (2016): 6433–37. http://dx.doi.org/10.1073/pnas.1519833113.

Full text

Abstract:

A broad range of quantum optimization problems can be phrased as the question of whether a specific system has a ground state at zero energy, i.e., whether its Hamiltonian is frustration-free. Frustration-free Hamiltonians, in turn, play a central role for constructing and understanding new phases of matter in quantum many-body physics. Unfortunately, determining whether this is the case is known to be a complexity-theoretically intractable problem. This makes it highly desirable to search for efficient heuristics and algorithms to, at least, partially answer this question. Here we prove a general criterion—a sufficient condition—under which a local Hamiltonian is guaranteed to be frustration-free by lifting Shearer’s theorem from classical probability theory to the quantum world. Remarkably, evaluating this condition proceeds via a fully classical analysis of a hardcore lattice gas at negative fugacity on the Hamiltonian’s interaction graph, which, as a statistical mechanics problem, is of interest in its own right. We concretely apply this criterion to local Hamiltonians on various regular lattices, while bringing to bear the tools of spin glass physics that permit us to obtain new bounds on the satisfiable to unsatisfiable transition in random quantum satisfiability. We are then led to natural conjectures for when such bounds will be tight, as well as to a novel notion of universality for these computer science problems. Besides providing concrete algorithms leading to detailed and quantitative insights, this work underscores the power of marrying classical statistical mechanics with quantum computation and complexity theory.

APA, Harvard, Vancouver, ISO, and other styles

28

Bansal, N., S. Bravyi, and B. M. Terhal. "Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs." Quantum Information and Computation 9, no. 7&8 (2009): 701–20. http://dx.doi.org/10.26421/qic9.7-8-12.

Full text

Abstract:

We describe a classical approximation algorithm for evaluating the ground state energy of the classical Ising Hamiltonian with linear terms on an arbitrary planar graph. The running time of the algorithm grows linearly with the number of spins and exponentially with $1/\epsilon$, where $\epsilon$ is the worst-case relative error. This result contrasts the well known fact that exact computation of the ground state energy for the two-dimensional Ising spin glass model is NP-hard. We also present a classical approximation algorithm for the quantum Local Hamiltonian Problem or Quantum Ising Spin Glass problem on a planar graph {\em with bounded degree} which is known to be a QMA-complete problem. Using a different technique we find a classical approximation algorithm for the quantum Ising spin glass problem on the simplest planar graph with unbounded degree, the star graph.

APA, Harvard, Vancouver, ISO, and other styles

29

Baril, Jean-Lue. "Hamiltonian paths for involutions in the square of a Cayley graph." Journal of Discrete Mathematical Sciences and Cryptography 10, no. 4 (2007): 473–84. http://dx.doi.org/10.1080/09720529.2007.10698133.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Abrosimov, M. B. "COMPARISON OF SUFFICIENT DEGREE BASED CONDITIONS FOR HAMILTONIAN GRAPH." Prikladnaya Diskretnaya Matematika, no. 45 (September 1, 2019): 55–63. http://dx.doi.org/10.17223/20710410/45/6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Lai, Hong-Jian, Yehong Shao, Hehui Wu, and Ju Zhou. "Every 3-connected, essentially 11-connected line graph is Hamiltonian." Journal of Combinatorial Theory, Series B 96, no. 4 (2006): 571–76. http://dx.doi.org/10.1016/j.jctb.2005.11.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Andrianova, E. G., V. K. Raev, and D. I. Filgus. "Determination of the Shortest Hamiltonian Paths in an Arbitrary Graph of Distributed Databases." Russian Technological Journal 7, no. 4 (2019): 7–20. http://dx.doi.org/10.32362/2500-316x-2019-7-4-7-20.

Full text

Abstract:

A method has been developed for finding the shortest Hamiltonian path in an arbitrary graph based on the rank approach, which provides high efficiency and a significant reduction in the error in solving the problem of organizing the process of managing multiple transactions and queries when they are implemented in network databases. In many cases, existing solutions do not provide the necessary results in terms of access time and accuracy of the found solution. Using the developed method allows minimizing the idle time of computing devices, reducing the volume and time of data transfer from one device to another, increases overall scalability, minimizes data access time, etc. An important advantage of the proposed method is to reduce the number of elementary operations and the number of vectors being processed the queue of the operations of the request, which leads to a significant reduction in time to implement the procedures for the formation of echer di operations in the requests. Methods of graph theory were used in this paper. The effectiveness of the task solution was evaluated using a systems approach, system analysis and the theory of operations research. Processing of experimental data obtained during the work was carried out in accordance with the provisions of mathematical statistics.

APA, Harvard, Vancouver, ISO, and other styles

33

Wocjan, P., D. Janzing, and T. Beth. "Simulating arbitrary pair-interactions by a given Hamiltonian: graph-theoretical bounds on the time-complexity." Quantum Information and Computation 2, no. 2 (2002): 117–32. http://dx.doi.org/10.26421/qic2.2-2.

Full text

Abstract:

We consider a quantum computer consisting of n spins with an arbitrary but fixed pair-interaction Hamiltonian and describe how to simulate other pair-interactions by interspersing the natural time evolution with fast local transformations. Calculating the minimal time overhead of such a simulation leads to a convex optimization problem. Lower and upper bounds on the minimal time overhead are derived in terms of chromatic indices of interaction graphs and spectral majorization criteria. These results classify Hamiltonians with respect to their computational power. For a specific Hamiltonian, namely \sigma_z\otimes\sigma_z-interactions between all spins, the optimization is mathematically equivalent to a separability problem of n-qubit density matrices. We compare the complexity defined by such a quantum computer with the usual gate complexity.

APA, Harvard, Vancouver, ISO, and other styles

34

Häggkvist, Roland. "Hamilton Cycles in Oriented Graphs." Combinatorics, Probability and Computing 2, no. 1 (1993): 25–32. http://dx.doi.org/10.1017/s0963548300000468.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

He, Qing-Bi, Hong-Gang Li, Mao-Ming Jin, Hui-Ming Duan, and Qing-Hua Zhang. "New necessary and sufficient condition and algorithm for directed hamiltonian graph based on boolean determinant theory." Journal of Discrete Mathematical Sciences and Cryptography 20, no. 3 (2017): 725–45. http://dx.doi.org/10.1080/09720529.2016.1226618.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Hastings, Matthew. "Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture." Quantum Information and Computation 13, no. 5&6 (2013): 393–429. http://dx.doi.org/10.26421/qic13.5-6-3.

Full text

Abstract:

We consider the entanglement properties of ground states of Hamiltonians which are sums of commuting projectors (we call these commuting projector Hamiltonians), in particular whether or not they have ``trivial" ground states, where a state is trivial if it is constructed by a local quantum circuit of bounded depth and range acting on a product state. It is known that Hamiltonians such as the toric code only have nontrivial ground states in two dimensions. Conversely, commuting projector Hamiltonians which are sums of two-body interactions have trivial ground states\cite{bv}. Using a coarse-graining procedure, this implies that any such Hamiltonian with bounded range interactions in one dimension has a trivial ground state. In this paper, we further explore the question of which Hamiltonians have trivial ground states. We define an ``interaction complex" for a Hamiltonian, which generalizes the notion of interaction graph and we show that if the interaction complex can be continuously mapped to a $1$-complex using a map with bounded diameter of pre-images then the Hamiltonian has a trivial ground state assuming one technical condition on the Hamiltonians holds (this condition holds for all stabilizer Hamiltonians, and we additionally prove the result for all Hamiltonians under one assumption on the $1$-complex). While this includes the cases considered by Ref.~\onlinecite{bv}, we show that it also includes a larger class of Hamiltonians whose interaction complexes cannot be coarse-grained into the case of Ref.~\onlinecite{bv} but still can be mapped continuously to a $1$-complex. One motivation for this study is an approach to the quantum PCP conjecture. We note that many commonly studied interaction complexes can be mapped to a $1$-complex after removing a small fraction of sites. For commuting projector Hamiltonians on such complexes, in order to find low energy trivial states for the original Hamiltonian, it would suffice to find trivial ground states for the Hamiltonian with those sites removed. Such trivial states can act as a classical witness to the existence of a low energy state. While this result applies for commuting Hamiltonians and does not necessarily apply to other Hamiltonians, it suggests that to prove a quantum PCP conjecture for commuting Hamiltonians, it is worth investigating interaction complexes which cannot be mapped to $1$-complexes after removing a small fraction of points. We define this more precisely below; in some sense this generalizes the notion of an expander graph. Surprisingly, such complexes do exist as will be shown elsewhere\cite{fh}, and have useful properties in quantum coding theory.

APA, Harvard, Vancouver, ISO, and other styles

37

Tamizh Chelvam, T., and S. Anukumar Kathirvel. "Generalized unit and unitary Cayley graphs of finite rings." Journal of Algebra and Its Applications 18, no. 01 (2019): 1950006. http://dx.doi.org/10.1142/s0219498819500063.

Full text

Abstract:

Let [Formula: see text] be a finite commutative ring with nonzero identity and [Formula: see text] be the set of all units of [Formula: see text] The graph [Formula: see text] is the simple undirected graph with vertex set [Formula: see text] in which two distinct vertices [Formula: see text] and [Formula: see text] are adjacent if and only if there exists a unit element [Formula: see text] in [Formula: see text] such that [Formula: see text] is a unit in [Formula: see text] In this paper, we obtain degree of all vertices in [Formula: see text] and in turn provide a necessary and sufficient condition for [Formula: see text] to be Eulerian. Also, we give a necessary and sufficient condition for the complement [Formula: see text] to be Eulerian, Hamiltonian and planar.

APA, Harvard, Vancouver, ISO, and other styles

38

Zhang, Rong, and Shu-Guang Guo. "On the least Q -eigenvalue of a non-bipartite hamiltonian graph." Linear Algebra and its Applications 538 (February 2018): 89–102. http://dx.doi.org/10.1016/j.laa.2017.10.012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Zhang, Wei, Shuwen Wang, Weijie Han, Hai Yu, and Zhiliang Zhu. "An Image Encryption Algorithm Based on Random Hamiltonian Path." Entropy 22, no. 1 (2020): 73. http://dx.doi.org/10.3390/e22010073.

Full text

Abstract:

In graph theory, Hamiltonian path refers to the path that visits each vertex exactly once. In this paper, we designed a method to generate random Hamiltonian path within digital images, which is equivalent to permutation in image encryption. By these means, building a Hamiltonian path across bit planes can shuffle the distribution of the pixel’s bits. Furthermore, a similar thought can be applied for the substitution of pixel’s grey levels. To ensure the randomness of the generated Hamiltonian path, an adjusted Bernoulli map is proposed. By adopting these novel techniques, a bit-level image encryption scheme was devised. Evaluation of simulation results proves that the proposed scheme reached fair performance. In addition, a common flaw in calculating correlation coefficients of adjacent pixels was pinpointed by us. After enhancement, correlation coefficient becomes a stricter criterion for image encryption algorithms.

APA, Harvard, Vancouver, ISO, and other styles

40

"Chemical Formula Encryption - using Hamiltonian Circuits and Graph Valued Functions." International Journal of Innovative Technology and Exploring Engineering 8, no. 12 (2019): 4843–46. http://dx.doi.org/10.35940/ijitee.l3711.1081219.

Full text

Abstract:

The ever expanding nature of graph theory has made it a convenient tool for a wide range of practical applications. This study prescribes an algorithmic approach of cryptographic decoding of chemical formula using Jump graphs and Line graphs. Hamiltonian graphs are used as the key for encryption and decryption.

APA, Harvard, Vancouver, ISO, and other styles

41

Bullock, Frank, Marietjie Frick, Joy Singleton, Susan Van Aardt, and Kieka (C M. ). Mynhardt. "Maximal Nontraceable Graphs with Toughness less than One." Electronic Journal of Combinatorics 15, no. 1 (2008). http://dx.doi.org/10.37236/742.

Full text

Abstract:

A graph $G$ is maximal nontraceable (MNT) if $G$ does not have a hamiltonian path but, for every $e\in E\left( \overline{G}\right) $, the graph $G+e$ has a hamiltonian path. A graph $G$ is 1-tough if for every vertex cut $S$ of $G$ the number of components of $G-S$ is at most $|S|$. We investigate the structure of MNT graphs that are not 1-tough. Our results enable us to construct several interesting new classes of MNT graphs.

APA, Harvard, Vancouver, ISO, and other styles

42

Malik, Shabnam, Ahmad Mahmood Qureshi, and Tudor Zamfirescu. "Hamiltonicity of Cubic 3-Connected k-Halin Graphs." Electronic Journal of Combinatorics 20, no. 1 (2013). http://dx.doi.org/10.37236/3188.

Full text

Abstract:

We investigate here how far we can extend the notion of a Halin graph such that hamiltonicity is preserved. Let $H = T \cup C$ be a Halin graph, $T$ being a tree and $C$ the outer cycle. A $k$-Halin graph $G$ can be obtained from $H$ by adding edges while keeping planarity, joining vertices of $H - C$, such that $G - C$ has at most $k$ cycles. We prove that, in the class of cubic $3$-connected graphs, all $14$-Halin graphs are hamiltonian and all $7$-Halin graphs are $1$-edge hamiltonian. These results are best possible.

APA, Harvard, Vancouver, ISO, and other styles

43

Asratian, Armen S., Jonas B. Granholm, and Nikolay K. Khachatryan. "A localization method in Hamiltonian graph theory." Journal of Combinatorial Theory, Series B, May 2020. http://dx.doi.org/10.1016/j.jctb.2020.04.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Ekstein, Jan. "Hamiltonian Cycles in the Square of a Graph." Electronic Journal of Combinatorics 18, no. 1 (2011). http://dx.doi.org/10.37236/690.

Full text

Abstract:

We show that under certain conditions the square of the graph obtained by identifying a vertex in two graphs with hamiltonian square is also hamiltonian. Using this result, we prove necessary and sufficient conditions for hamiltonicity of the square of a connected graph such that every vertex of degree at least three in a block graph corresponds to a cut vertex and any two these vertices are at distance at least four.

APA, Harvard, Vancouver, ISO, and other styles

45

DeBiasio, Louis, and Theodore Molla. "Semi-Degree Threshold for Anti-Directed Hamiltonian Cycles." Electronic Journal of Combinatorics 22, no. 4 (2015). http://dx.doi.org/10.37236/3610.

Full text

Abstract:

In 1960 Ghouila-Houri extended Dirac's theorem to directed graphs by proving that if $D$ is a directed graph on $n$ vertices with minimum out-degree and in-degree at least $n/2$, then $D$ contains a directed Hamiltonian cycle. For directed graphs one may ask for other orientations of a Hamiltonian cycle and in 1980 Grant initiated the problem of determining minimum degree conditions for a directed graph $D$ to contain an anti-directed Hamiltonian cycle (an orientation in which consecutive edges alternate direction). We prove that for sufficiently large even $n$, if $D$ is a directed graph on $n$ vertices with minimum out-degree and in-degree at least $\frac{n}{2}+1$, then $D$ contains an anti-directed Hamiltonian cycle. In fact, we prove the stronger result that $\frac{n}{2}$ is sufficient unless $D$ is one of two counterexamples. This result is sharp.

APA, Harvard, Vancouver, ISO, and other styles

46

DeBiasio, Louis, Safi Faizullah, and Imdadullah Khan. "Ore-degree threshold for the square of a Hamiltonian cycle." Discrete Mathematics & Theoretical Computer Science Vol. 17 no. 1, Graph Theory (2015). http://dx.doi.org/10.46298/dmtcs.2127.

Full text

Abstract:

Graph Theory International audience A classic theorem of Dirac from 1952 states that every graph with minimum degree at least n=2 contains a Hamiltonian cycle. In 1963, P´osa conjectured that every graph with minimum degree at least 2n=3 contains the square of a Hamiltonian cycle. In 1960, Ore relaxed the degree condition in the Dirac’s theorem by proving that every graph with deg(u) + deg(v) ≥ n for every uv =2 E(G) contains a Hamiltonian cycle. Recently, Chˆau proved an Ore-type version of P´osa’s conjecture for graphs on n ≥ n0 vertices using the regularity–blow-up method; consequently the n0 is very large (involving a tower function). Here we present another proof that avoids the use of the regularity lemma. Aside from the fact that our proof holds for much smaller n0, we believe that our method of proof will be of independent interest.

APA, Harvard, Vancouver, ISO, and other styles

47

Alahmadi, Adel, Robert E. L. Aldred, Ahmad Alkenani, Rola Hijazi, P. Solé, and Carsten Thomassen. "Extending a perfect matching to a Hamiltonian cycle." Discrete Mathematics & Theoretical Computer Science Vol. 17 no. 1, Graph Theory (2015). http://dx.doi.org/10.46298/dmtcs.2105.

Full text

Abstract:

Graph Theory International audience Ruskey and Savage conjectured that in the d-dimensional hypercube, every matching M can be extended to a Hamiltonian cycle. Fink verified this for every perfect matching M, remarkably even if M contains external edges. We prove that this property also holds for sparse spanning regular subgraphs of the cubes: for every d ≥7 and every k, where 7 ≤k ≤d, the d-dimensional hypercube contains a k-regular spanning subgraph such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle. We do not know if this result can be extended to k=4,5,6. It cannot be extended to k=3. Indeed, there are only three 3-regular graphs such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle, namely the complete graph on 4 vertices, the complete bipartite 3-regular graph on 6 vertices and the 3-cube on 8 vertices. Also, we do not know if there are graphs of girth at least 5 with this matching-extendability property.

APA, Harvard, Vancouver, ISO, and other styles

48

Chen, Wei-Guo, Zhi-Hong Chen, and Mei Lu. "Lai's Conditions for Spanning and Dominating Closed Trails." Electronic Journal of Combinatorics 22, no. 1 (2015). http://dx.doi.org/10.37236/4511.

Full text

Abstract:

A graph is supereulerian if it has a spanning closed trail. For an integer $r$, let ${\cal Q}_0(r)$ be the family of 3-edge-connected nonsupereulerian graphs of order at most $r$. For a graph $G$, define $\delta_L(G)=\min\{\max\{d(u), d(v) \}| \ \mbox{ for any $uv\in E(G)$} \}$. For a given integer $p\ge 2$ and a given real number $\epsilon$, a graph $G$ of order $n$ is said to satisfy a Lai's condition if $\delta_L(G)\ge \frac{n}{p}-\epsilon$. In this paper, we show that if $G$ is a 3-edge-connected graph of order $n$ with $\delta_L(G)\ge \frac{n}{p}-\epsilon$, then there is an integer $N(p, \epsilon)$ such that when $n> N(p,\epsilon)$, $G$ is supereulerian if and only if $G$ is not a graph obtained from a graph $G_p$ in the finite family ${\cal Q}_0(3p-5)$ by replacing some vertices in $G_p$ with nontrivial graphs. Results on the best possible Lai's conditions for Hamiltonian line graphs of 3-edge-connected graphs or 3-edge-connected supereulerian graphs are given, which are improvements of the results in [J. Graph Theory 42(2003) 308-319] and in [Discrete Mathematics, 310(2010) 2455-2459].

APA, Harvard, Vancouver, ISO, and other styles

49

de Mello Koch, Robert, Eunice Gandote, and Augustine Larweh Mahu. "Scrambling in Yang-Mills." Journal of High Energy Physics 2021, no. 1 (2021). http://dx.doi.org/10.1007/jhep01(2021)058.

Full text

Abstract:

Abstract Acting on operators with a bare dimension ∆ ∼ N2 the dilatation operator of U(N) $$ \mathcal{N} $$ N = 4 super Yang-Mills theory defines a 2-local Hamiltonian acting on a graph. Degrees of freedom are associated with the vertices of the graph while edges correspond to terms in the Hamiltonian. The graph has p ∼ N vertices. Using this Hamiltonian, we study scrambling and equilibration in the large N Yang-Mills theory. We characterize the typical graph and thus the typical Hamiltonian. For the typical graph, the dynamics leads to scrambling in a time consistent with the fast scrambling conjecture. Further, the system exhibits a notion of equilibration with a relaxation time, at weak coupling, given by t ∼ $$ \frac{\rho }{\lambda } $$ ρ λ with λ the ’t Hooft coupling.

APA, Harvard, Vancouver, ISO, and other styles

50

Heuer, Karl. "Hamiltonicity in Locally Finite Graphs: Two Extensions and a Counterexample." Electronic Journal of Combinatorics 25, no. 3 (2018). http://dx.doi.org/10.37236/6773.

Full text

Abstract:

We state a sufficient condition for the square of a locally finite graph to contain a Hamilton circle, extending a result of Harary and Schwenk about finite graphs. We also give an alternative proof of an extension to locally finite graphs of the result of Chartrand and Harary that a finite graph not containing $K^4$ or $K_{2,3}$ as a minor is Hamiltonian if and only if it is $2$-connected. We show furthermore that, if a Hamilton circle exists in such a graph, then it is unique and spanned by the $2$-contractible edges. The third result of this paper is a construction of a graph which answers positively the question of Mohar whether regular infinite graphs with a unique Hamilton circle exist.

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!