To see the other types of publications on this topic, follow the link: Hamiltonian graphs.
Dissertations / Theses on the topic 'Hamiltonian graphs'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses 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 dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Iturriaga-Velazquez, Claudia C. "Intersection graphs, fraternally orientable graphs and hamiltonian cycles." Thesis, University of Ottawa (Canada), 1994. http://hdl.handle.net/10393/6808.
Full textAbstract:
Consider a graph G(V, E), where V and E denote the vertex and edge sets of G(V, E), respectively. An orientation $\vec G$ of G(V, E) is the result of giving an orientation to the edges of G. A directed graph is fraternally oriented if for every three vertices u, v, w, the existence of the edges $u\to w$ and $v\to w$ implies that $u\to v$ or $v\to u$. A graph G is fraternally orientable if there exists an orientation $\vec G$ that is fraternally oriented. In this thesis we study some properties of fraternally orientable graphs, and we describe an algorithm to find a hamiltonian cycle in strongly connected fraternally oriented graphs $\vec G$.
2
Streib, Noah Sametz. "Planar and hamiltonian cover graphs." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/43744.
Full textAbstract:
This dissertation has two principal components: the dimension of posets with planar cover graphs, and the cartesian product of posets whose cover graphs have hamiltonian cycles that parse into symmetric chains. Posets of height two can have arbitrarily large dimension. In 1981, Kelly provided an infinite sequence of planar posets that shows that the dimension of planar posets can also be arbitrarily large. However, the height of the posets in this sequence increases with the dimension. In 2009, Felsner, Li, and Trotter conjectured that for each integer h at least 2, there exists a least positive integer c(h) so that if P is a poset with a planar cover graph (the class of posets with planar cover graphs includes the class of planar posets) and the height of P is h, then the dimension of P is at most c(h). In the first principal component of this dissertation we prove this conjecture. We also give the best known lower bound for c(h), noting that this lower bound is far from the upper bound. In the second principal component, we consider posets with the Hamiltonian Cycle--Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a hamiltonian cycle which parses into w symmetric chains. This definition is motivated by a proof of Sperner's theorem that uses symmetric chains, and was intended as a possible method of attack on the Middle Two Levels Conjecture. We show that the subset lattices have the HC-SCP property by showing that the class of posets with the strong HC-SCP property, a slight strengthening of the HC-SCP property, is closed under cartesian product with a two-element chain. Furthermore, we show that the cartesian product of any two posets from this strong class has the (weak) HC-SCP property.
3
Ghenciu, Petre Ion. "Hamiltonian cycles in subset and subspace graphs." Thesis, University of North Texas, 2004. https://digital.library.unt.edu/ark:/67531/metadc4662/.
Full textAbstract:
In this dissertation we study the Hamiltonicity and the uniform-Hamiltonicity of subset graphs, subspace graphs, and their associated bipartite graphs. In 1995 paper "The Subset-Subspace Analogy," Kung states the subspace version of a conjecture. The study of this problem led to a more general class of graphs. Inspired by Clark and Ismail's work in the 1996 paper "Binomial and Q-Binomial Coefficient Inequalities Related to the Hamiltonicity of the Kneser Graphs and their Q-Analogues," we defined subset graphs, subspace graphs, and their associated bipartite graphs. The main emphasis of this dissertation is to describe those graphs and study their Hamiltonicity. The results on subset graphs are presented in Chapter 3, on subset bipartite graphs in Chapter 4, and on subspace graphs and subspace bipartite graphs in Chapter 5. We conclude the dissertation by suggesting some generalizations of our results concerning the panciclicity of the graphs.
4
High, David. "On 4-Regular Planar Hamiltonian Graphs." TopSCHOLAR®, 2006. http://digitalcommons.wku.edu/theses/277.
Full textAbstract:
In order to research knots with large crossing numbers, one would like to be able to select a random knot from the set of all knots with n crossings with as close to uniform probability as possible. The underlying graph of a knot diagram can be viewed as a 4-regular planar graph. The existence of a Hamiltonian cycle in such a graph is necessary in order to use the graph to compute an upper bound on rope length for a given knot. The algorithm to generate such graphs is discussed and an exact count of the number of graphs is obtained. In order to allow for the existence of such a count, a somewhat technical definition of graph equivalence is used. The main result of the thesis is the asymptotic results of how fast the number of graphs with n vertices (crossings) grows with n.
5
Li, Mingchu. "Hamiltonian properties of claw-free graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/tape15/PQDD_0001/NQ35223.pdf.
Full text
6
Alabdullatif, Mosaad. "Extremal graphs with Hamiltonian related properties." Thesis, Keele University, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.362161.
Full text
7
Yang, Weihua. "Supereulerian graphs, Hamiltonicity of graphes and several extremal problems in graphs." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00877793.
Full textAbstract:
In this thesis, we focus on the following topics: supereulerian graphs, hamiltonian line graphs, fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, and several extremal problems on the (minimum and/or maximum) size of graphs under a given graph property. The thesis includes six chapters. The first one is to introduce definitions and summary the main results of the thesis, and in the last chapter we introduce the furture research of the thesis. The main studies in Chapters 2 - 5 are as follows. In Chapter 2, we explore conditions for a graph to be supereulerian.In Section 1 of Chapter 2, we characterize the graphs with minimum degree at least 2 and matching number at most 3. By using the characterization, we strengthen the result in [93] and we also address a conjecture in the paper.In Section 2 of Chapter 2, we prove that if $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$, then $G$ is collapsible except for several special graphs, where $p(n)=0$ for $n$ even and $p(n)=1$ for $n$ odd. As a corollary, a characterization for graphs satisfying $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$ to be supereulerian is obtained. This result extends the result in [21].In Section 3 of Chapter 2, we focus on a conjecture posed by Chen and Lai [Conjecture~8.6 of [33]] that every 3-edge connected and essentially 6-edge connected graph is collapsible. We find a kind of sufficient conditions for a 3-edge connected graph to be collapsible.In Chapter 3, we mainly consider the hamiltonicity of 3-connected line graphs.In the first section of Chapter 3, we give several conditions for a line graph to be hamiltonian, especially we show that every 3-connected, essentially 11-connected line graph is hamilton- connected which strengthens the result in [91].In the second section of Chapter 3, we show that every 3-connected, essentially 10-connected line graph is hamiltonian-connected.In the third section of Chapter 3, we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is hamiltonian. Moreover, if $G$ has 10 vertices of degree 3 and its line graph is not hamiltonian, then $G$ can be contractible to the Petersen graph.In Chapter 4, we consider edge fault-tolerant hamiltonicity of Cayley graphs generated by transposition trees. We first show that for any $F\subseteq E(Cay(B:S_{n}))$, if $|F|\leq n-3$ and $n\geq4$, then there exists a hamiltonian path in $Cay(B:S_{n})-F$ between every pair of vertices which are in different partite sets. Furthermore, we strengthen the above result in the second section by showing that $Cay(S_n,B)-F$ is bipancyclic if $Cay(S_n,B)$ is not a star graph, $n\geq4$ and $|F|\leq n-3$.In Chapter 5, we consider several extremal problems on the size of graphs.In Section 1 of Chapter 5, we bounds the size of the subgraph induced by $m$ vertices of hypercubes. We show that a subgraph induced by $m$ (denote $m$ by $\sum\limits_{i=0}^ {s}2^{t_i}$, $t_0=[\log_2m]$ and $t_i= [\log_2({m-\sum\limits_{r=0}^{i-1}2 ^{t_r}})]$ for $i\geq1$) vertices of an $n$-cube (hypercube) has at most $\sum\limits_{i=0}^{s}t_i2^{t_i-1} +\sum\limits_{i=0}^{s} i\cdot2^{t_i}$ edges. As its applications, we determine the $m$-extra edge-connectivity of hypercubes for $m\leq2^{[\frac{n}2]}$ and $g$-extra edge-connectivity of the folded hypercube for $g\leq n$.In Section 2 of Chapter 5, we partially study the minimum size of graphs with a given minimum degree and a given edge degree. As an application, we characterize some kinds of minimumrestricted edge connected graphs.In Section 3 of Chapter 5, we consider the minimum size of graphs satisfying Ore-condition.
8
Vandegriend, Basil. "Finding Hamiltonian cycles, algorithms, graphs and performance." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp04/mq28995.pdf.
Full text
9
Madden, Yale. "Loop Edge Estimation in 4-Regular Hamiltonian Graphs." TopSCHOLAR®, 2007. http://digitalcommons.wku.edu/theses/406.
Full textAbstract:
In knot theory, a knot is defined as a closed, non-self-intersecting curve embedded in three-dimensional space that cannot be untangled to produce a simple planar loop. A mathematical knot is essentially a conventional knot tied with rope where the ends of the rope have been glued together. One way to sample large knots is based on choosing a 4-regular Hamiltonian planar graph. A method for generating rooted 4-regular Hamiltonian planar graphs with n vertices is discussed in this thesis. In the generation process of these graphs, some vertices are introduced that can be easily eliminated from the resulting knot diagram. The main result of this thesis is the estimation of the expected number of loop edges in a 4-regular Hamiltonian planar graphs of n vertices; in particular, it is shown that the expected number of loop edges L(n) in such a graph has asymptotic order n/6.
10
Ascigil, Mehmet. "An Algorithm to Generate 4-Regular Planar Hamiltonian Graphs." TopSCHOLAR®, 2006. http://digitalcommons.wku.edu/theses/440.
Full textAbstract:
In this paper, the problem of randomly generating 4-regular planar Hamiltonian graphs is discussed and a solution is described. An algorithm which efficiently generates the graphs in linear time and in a near-uniform manner is given. In addition, a formula is provided that determines the total number of such graphs. The generation of graphs starts with forming the Hamiltonian cycle of the final graph. Each vertex is randomly assigned to be connected with zero. one. Or two edges in the area bounded by the Hamiltonian cycle. A positive prefix vector is used to determine all the edges in the area bounded by the Hamiltonian cycle. Another positive prefix vector is used for determining the edges in the area not bounded by the Hamiltonian cycle, forming the final graph.
11
Mofokeng, Tshenolo. "Hamiltonian cycles in maximal planar graphs and planar triangulations." Master's thesis, University of Cape Town, 2017. http://hdl.handle.net/11427/25389.
Full textAbstract:
In this thesis we study planar graphs, in particular, maximal planar graphs and general planar triangulations. In Chapter 1 we present the terminology and notations that will be used throughout the thesis and review some elementary results on graphs that we shall need. In Chapter 2 we study the fundamentals of planarity, since it is the cornerstone of this thesis. We begin with the famous Euler's Formula which will be used in many of our results. Then we discuss another famous theorem in graph theory, the Four Colour Theorem. Lastly, we discuss Kuratowski's Theorem, which gives a characterization of planar graphs. In Chapter 3 we discuss general properties of a maximal planar graph, G particularly concerning connectivity. First we discuss maximal planar graphs with minimum degree i, for i = 3; 4; 5, and the subgraph induced by the vertices of G with the same degree. Finally we discuss the connectivity of G, a maximal planar graph with minimum degree i. Chapter 4 will be devoted to Hamiltonian cycles in maximal planar graphs. We discuss the existence of Hamiltonian cycles in maximal planar graphs. Whitney proved that any maximal planar graph without a separating triangle is Hamiltonian, where a separating triangle is a triangle such that its removal disconnects the graph. Chen then extended Whitney's results and allowed for one separating triangle and showed that the graph is still Hamiltonian. Helden also extended Chen's result and allowed for two separating triangles and showed that the graph is still Hamiltonian. G. Helden and O. Vieten went further and allowed for three separating triangles and showed that the graph is still Hamiltonian. In the second section we discuss the question by Hakimi and Schmeichel: what is the number of cycles of length p that a maximal planar graph on n vertices could have in terms of n? Then in the last section we discuss the question by Hakimi, Schmeichel and Thomassen: what is the minimum number of Hamiltonian cycles that a maximal planar graph on n vertices could have, in terms of n? In Chapter 5, we look at general planar triangulations. Note that every maximal planar graph on n ≥ 3 vertices is a planar triangulation. In the first section we discuss general properties of planar triangulations and then end with Hamiltonian cycles in planar triangulations.
12
Dey, Sanjoy. "Structural properties of visibility and weak visibility graphs." Virtual Press, 1997. http://liblink.bsu.edu/uhtbin/catkey/1048394.
Full textAbstract:
Given a finite set S of n nonintersecting line segments with no three end points collinear, the segment end point visibility graph is defined as the graph whose vertices are the end points of the line segments in S and two vertices are adjacent if the straight line segment joining two end points does not intersect any element of S, or if they are end points of the same segment. Segment end point visibility graphs have a wide variety of applications in VLSI circuit design, study of art gallery problems, and other areas of computational geometry. This thesis contains a survey of the important results that are currently known regarding the characterization of these graphs. Also a weak visibility dual of a segment end point visibility graph is defined and some structural properties of such graphs are presented. Some open problems and questions related to the characterization of weak visibility graphs are also discussed.Department of Mathematical Sciences
13
Muche, Tilahun Abay. "Hamiltonian Sets of Polygonal Paths in 4-Valent Spatial Graphs." Scholar Commons, 2012. http://scholarcommons.usf.edu/etd/4177.
Full textAbstract:
Spatial graphs with 4–valent rigid vertices and two single valent endpoints, called assembly graphs, model DNA recombination processes that appear in certain species of ciliates. Recombined genes are modeled by certain types of paths in an assembly graph that make a ”oper pendicular ” turn at each 4–valent vertex of the graph called polygonal paths. The assembly number of an assembly graph is the minimum number of polygonal paths that visit each vertex exactly once. In particular, an assembly graph is called realizable if the graph has a Hamiltonian polygonal path.
An assembly graph ɣ^ obtained from a given assembly graph γ by substituting every edge of γ by a loop is called a loop-saturated graph. We show that a loop- saturated graph ɣ^ has an assembly number a unit larger than the size of ɣ. For a positive integer n, the minimum realization number for n is defined by Rmin(n) = min{|ɣ| : An(ɣ) = n}, where |γ| is the number of 4-valent vertices in γ. A graph γ that gives the minimum for Rmin(n) is called a realization of assembly number n. We denote by Rmin(n) the set of realization graphs for n. We prove that loop-saturated graphs with assembly number nachieve the upper bound of Rmin(n). If a simple assembly graph γ has no loops then γ is not in Rmin(n).
With the introduction of left –additive, right–additive
and middle additive operations, we study the properties of assembly graphs when composing increases their assembly number. We also introduce the notion of height sequence, a non-increasing sequence of positive integers, that counts the number of 4-valent vertices which the polygonal paths contain. We show properties of a height sequence for loop–saturated graphs.
Assembly graphs are represented by double-occurrence words called assembly words. An assembly word is strongly-irreducible if it does not contain a proper subword that is also a double-occurrence word. We prove that, for every positive integer n there is a strongly-irreducible assembly graph with assembly number n, and if a simple assembly graph is strongly-irreducible, then γ ̸∈ Rmin(n).
14
Zhan, Mingquan. "Eulerian subgraphs and Hamiltonicity of claw-free graphs." Morgantown, W. Va. : [West Virginia University Libraries], 2003. http://etd.wvu.edu/templates/showETD.cfm?recnum=3024.
Full textAbstract:
Thesis (Ph. D.)--West Virginia University, 2003.Title from document title page. Document formatted into pages; contains vi, 52 p. : ill. Includes abstract. Includes bibliographical references (p. 50-52).
15
Ozkan, Sibel. "Hamilton decompositions of graphs with primitive complements." Auburn, Ala., 2007. http://repo.lib.auburn.edu/2007%20Spring%20Dissertations/OZKAN_SIBEL_27.pdf.
Full text
16
Rudoy, Mikhail. "Hamiltonian cycle and related problems : vertex-breaking, grid graphs, and Rubik's Cubes." Thesis, Massachusetts Institute of Technology, 2017. http://hdl.handle.net/1721.1/113112.
Full textAbstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 123-124).
In this thesis, we analyze the computational complexity of several problems related to the Hamiltonian Cycle problem. We begin by introducing a new problem, which we call Tree-Residue Vertex-Breaking (TRVB). Given a multigraph G some of whose vertices are marked "breakable," TRVB asks whether it is possible to convert G into a tree via a sequence of applications of the vertex-breaking operation: disconnecting the edges at a degree-G breakable vertex by replacing that vertex with G degree-1 vertices. We consider the special cases of TRVB with any combination of the following additional constraints: G must be planar, G must be a simple graph, the degree of every breakable vertex must belong to an allowed list G, and the degree of every unbreakable vertex must belong to an allowed list G. We fully characterize these variants of TRVB as polynomially solvable or NP-complete. The TRVB problem is useful when analyzing the complexity of what could be called single-traversal problems, where some space (i.e., a configuration graph or a grid) must be traversed in a single path or cycle subject to local constraints. When proving such a problem NP-hard, a reduction from TRVB can often be used as a simpler alternative to reducing from a hard variant of Hamiltonian Cycle. Next, we analyze several variants of the Hamiltonian Cycle problem whose complexity was left open in a 2007 paper by Arkin et al [3]. That paper is a systematic study of the complexity of the Hamiltonian Cycle problem on square, triangular, or hexagonal grid graphs, restricted to polygonal, thin, super-thin, degree-bounded, or solid grid graphs. The authors solved many combinations of these problems, proving them either polynomially solvable or NP-complete, but left three combinations open. We prove two of these unsolved combinations to be NP-complete: Hamiltonian Cycle in Square Polygonal Grid Graphs and Hamiltonian Cycle in Hexagonal Thin Grid Graphs. We also consider a new restriction, where the grid graph is both thin and polygonal, and prove that the Hamiltonian Cycle problem then becomes polynomially solvable for square, triangular, and hexagonal grid graphs. Several of these results are shown by application of the TRVB results, demonstrating the usefulness of that problem. Finally, we apply the Square Grid Graph Hamiltonian Cycle problem to close a longstanding open problem: we prove that optimally solving an n x n x n Rubik's Cube is NP-complete. This improves the previous result that optimally solving an n x n x n Rubik's Cube with missing stickers is NP-complete. We prove this result first for the simpler case of the Rubik's Square -- an n x n x 1 generalization of the Rubik's Cube -- and then proceed with a similar but more complicated proof for the Rubik's Cube case.
by Mikhail Rudoy.
M. Eng.
17
Teska, Jakub University of Ballarat. "Graphs and subgraphs with bounded degree." Author, 2008. http://archimedes.ballarat.edu.au:8080/vital/access/HandleResolver/1959.17/12806.
Full textAbstract:
"The topology of a network (such as a telecommunications, multiprocessor, or local area network, to name just a few) is usually modelled by a graph in which vertices represent 'nodes' (stations or processors) while undirected or directed edges stand for 'links' or other types of connections, physical or virtual. A cycle that contains every vertex of a graph is called a hamiltonian cycle and a graph which contains a hamiltonian cycle is called a hamiltonian graph. The problem of the existence of a hamiltonian cycle is closely related to the well known problem of a travelling salesman. These problems are NP-complete and NP-hard, respectively. While some necessary and sufficient conditions are known, to date, no practical characterization of hamiltonian graphs has been found. There are several ways to generalize the notion of a hamiltonian cycle. In this thesis we make original contributions in two of them, namely k-walks and r-trestles." --Abstract.Doctor of Philosophy
18
Teska, Jakub. "Graphs and subgraphs with bounded degree." Author, 2008. http://archimedes.ballarat.edu.au:8080/vital/access/HandleResolver/1959.17/15398.
Full textAbstract:
"The topology of a network (such as a telecommunications, multiprocessor, or local area network, to name just a few) is usually modelled by a graph in which vertices represent 'nodes' (stations or processors) while undirected or directed edges stand for 'links' or other types of connections, physical or virtual. A cycle that contains every vertex of a graph is called a hamiltonian cycle and a graph which contains a hamiltonian cycle is called a hamiltonian graph. The problem of the existence of a hamiltonian cycle is closely related to the well known problem of a travelling salesman. These problems are NP-complete and NP-hard, respectively. While some necessary and sufficient conditions are known, to date, no practical characterization of hamiltonian graphs has been found. There are several ways to generalize the notion of a hamiltonian cycle. In this thesis we make original contributions in two of them, namely k-walks and r-trestles." --Abstract.Doctor of Philosophy
19
Wagner, Andrew. "On the Existence of a Second Hamilton Cycle in Hamiltonian Graphs With Symmetry." Thèse, Université d'Ottawa / University of Ottawa, 2013. http://hdl.handle.net/10393/30290.
Full textAbstract:
In 1975, Sheehan conjectured that every simple 4-regular hamiltonian graph has a second Hamilton cycle. If Sheehan's Conjecture holds, then the result can be extended to all simple d-regular hamiltonian graphs with d at least 3.
First, we survey some previous results which verify the existence of a second Hamilton cycle if d is large enough. We will then demonstrate some techniques for finding a second Hamilton cycle that will be used throughout this paper. Finally, we use these techniques and show that for certain 4-regular Hamiltonian graphs whose automorphism group is large enough, a second Hamilton cycle exists.
20
He, Weihua. "Cycles in graphs and arc colorings in digraphs." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112352.
Full textAbstract:
Dans cette thèse nous étudions quatre problèmes de théorie des graphes. En particulier,Nous étudions le problème du cycle hamiltonien dans les line graphes, et aussi nous prouvons l’existence de cycles hamiltoniens dans certains sous graphes couvrants d’un line graphe. Notre résultat principal est: Si L(G) est hamiltonien, alors SL(G) est hamiltonien. Grâce à ce résultat nous proposons une conjecture équivalente à des conjectures célèbres. Et nous obtenons deux résultats sur les cycles hamiltoniens disjoints dans les line graphes.Nous considérons alors la bipancyclicité résistante aux pannes des graphes de Cayley engendrés par transposition d’arbres. Nous prouvons que de tels graphes de Cayley excepté le “star graph” ont une bipancyclicité (n − 3)-arête résistante aux pannes.Ensuite nous introduisons la coloration des arcs d’un digraphe sommet distinguant. Nous étudions la relation entre cette notion et la coloration d’arêtes sommet distinguant dans les graphes non orientés. Nous obtenons quelques résultats sur le nombre arc chromatique des graphes orientés (semi-)sommet-distinguant et proposons une conjecture sur ce paramètre. Pour vérifier cette conjecture nous étudions la coloration des arcs d’un digraphe sommet distinguant des graphes orientés réguliers.Finalement nous introduisons la coloration acyclique des arcs d’un graphe orienté. Nous calculons le nombre chromatique acyclique des arcs de quelques familles de graphes orientés et proposons une conjecture sur ce paramètre. Nous considérons les graphes orientés de grande maille et utilisons le Lemme Local de Lovász; d’autre part nous considérons les graphes orientés réguliers aléatoires. Nous prouvons que ces deux classes de graphes vérifient la conjectureIn this thesis, we study four problems in graph theory, the Hamiltonian cycle problem in line graphs, the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees, the vertex-distinguishing arc colorings in digraph- s and the acyclic arc coloring in digraphs. The first two problems are the classic problem on the cycles in graphs. And the other two arc coloring problems are related to the modern graph theory, in which we use some probabilistic methods. In particular,We first study the Hamiltonian cycle problem in line graphs and find the Hamiltonian cycles in some spanning subgraphs of line graphs SL(G). We prove that: if L(G) is Hamiltonian, then SL(G) is Hamiltonian. Due to this, we propose a conjecture, which is equivalent to some well-known conjectures. And we get two results about the edge-disjoint Hamiltonian cycles in line graphs.Then, we consider the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees. And we prove that the Cayley graph generated by transposition tree is (n − 3)-edge-fault-tolerant bipancyclic if it is not a star graph.Later, we introduce the vertex-distinguishing arc coloring in digraphs. We study the relationship between the vertex-distinguishing edge coloring in undirected graphs and the vertex-distinguishing arc coloring in digraphs. And we get some results on the (semi-) vertex-distinguishing arc chromatic number for digraphs and also propose a conjecture about it. To verify the conjecture we study the vertex-distinguishing arc coloring for regular digraphs.Finally, we introduce the acyclic arc coloring in digraphs. We calculate the acyclic arc chromatic number for some digraph families and propose a conjecture on the acyclic arc chromatic number. Then we consider the digraphs with high girth by using the Lovász Local Lemma and we also consider the random regular digraphs. And the results of the digraphs with high girth and the random regular digraphs verify the conjecture
21
Becker, Kai Helge. "Twin-constrained Hamiltonian paths on threshold graphs : an approach to the minimum score separation problem." Thesis, London School of Economics and Political Science (University of London), 2010. http://etheses.lse.ac.uk/3209/.
Full textAbstract:
The Minimum Score Separation Problem (MSSP) is a combinatorial problem that has been introduced in JORS 55 as an open problem in the paper industry arising in conjunction with the cutting-stock problem. During the process of producing boxes, áat papers are prepared for folding by being scored with knives. The problem is to determine if and how a given production pattern of boxes can be arranged such that a certain minimum distance between the knives can be kept. While it was originally suggested to analyse the MSSP as a specific variant of a Generalized Travelling Salesman Problem, the thesis introduces the concept of twin-constrained Hamiltonian cycles and models the MSSP as the problem of finding a twin-constrained Hamiltonian path on a threshold graph (threshold graphs are a specific type of interval graphs). For a given undirected graph G(N,E) with an even node set N and edge set E, and a bijective function b on N that assigns to every node i in N a "twin node" b(i)6=i, we define a new graph G'(N,E') by adding the edges {i,b(i)} to E. The graph G is said to have a twin-constrained Hamiltonian path with respect to b if there exists a Hamiltonian path on G' in which every node has its twin node as its predecessor (or successor). We start with presenting some general Öndings for the construction of matchings, alternating paths, Hamiltonian paths and alternating cycles on threshold graphs. On this basis it is possible to develop criteria that allow for the construction of twin-constrained Hamiltonian paths on threshold graphs and lead to a heuristic that can quickly solve a large percentage of instances of the MSSP. The insights gained in this way can be generalized and lead to an (exact) polynomial time algorithm for the MSSP. Computational experiments for both the heuristic and the polynomial-time algorithm demonstrate the efficiency of our approach to the MSSP. Finally, possible extensions of the approach are presented.
22
Bedenknecht, Wiebke [Verfasser], and Christian [Akademischer Betreuer] Reiher. "Local density properties of Andrásfai graphs and powers of Hamiltonian cycles in hypergraphs / Wiebke Bedenknecht ; Betreuer: Christian Reiher." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2018. http://d-nb.info/1166851176/34.
Full text
23
Bedenknecht, Wiebke Verfasser], and Christian [Akademischer Betreuer] [Reiher. "Local density properties of Andrásfai graphs and powers of Hamiltonian cycles in hypergraphs / Wiebke Bedenknecht ; Betreuer: Christian Reiher." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2018. http://nbn-resolving.de/urn:nbn:de:gbv:18-92958.
Full text
24
Bergougnoux, Benjamin. "Matrix decompositions and algorithmic applications to (hyper)graphs." Thesis, Université Clermont Auvergne (2017-2020), 2019. http://www.theses.fr/2019CLFAC025/document.
Full textAbstract:
Durant ces dernières décennies, d'importants efforts et beaucoup de café ont été dépensés en vue de caractériser les instances faciles des problèmes NP-difficiles. Dans ce domaine de recherche, une approche s'avère être redoutablement efficace : la théorie de la complexité paramétrée introduite par Downey et Fellows dans les années 90.Dans cette théorie, la complexité d'un problème n'est plus mesurée uniquement en fonction de la taille de l'instance, mais aussi en fonction d'un paramètre .Dans cette boite à outils, la largeur arborescente est sans nul doute un des paramètres de graphe les plus étudiés.Ce paramètre mesure à quel point un graphe est proche de la structure topologique d'un arbre.La largeur arborescente a de nombreuses propriétés algorithmiques et structurelles.Néanmoins, malgré l'immense intérêt suscité par la largeur arborescente, seules les classes de graphes peu denses peuvent avoir une largeur arborescente bornée.Mais, de nombreux problèmes NP-difficiles s'avèrent faciles dans des classes de graphes denses.La plupart du temps, cela peut s'expliquer par l'aptitude de ces graphes à se décomposer récursivement en bipartitions de sommets $(A,B)$ où le voisinage entre $A$ et $B$ possède une structure simple.De nombreux paramètres -- appelés largeurs -- ont été introduits pour caractériser cette aptitude, les plus remarquables sont certainement la largeur de clique , la largeur de rang , la largeur booléenne et la largeur de couplage induit .Dans cette thèse, nous étudions les propriétés algorithmiques de ces largeurs.Nous proposons une méthode qui généralise et simplifie les outils développés pour la largeur arborescente et les problèmes admettant une contrainte d'acyclicité ou de connexité tel que Couverture Connexe , Dominant Connexe , Coupe Cycle , etc.Pour tous ces problèmes, nous obtenons des algorithmes s'exécutant en temps $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ et $n^{O(k)}$ avec $k$ étant, respectivement, la largeur de clique, la largeur de Q-rang, la larguer de rang et la largueur de couplage induit.On prouve aussi qu'il existe un algorithme pour Cycle Hamiltonien s'exécutant en temps $n^{O(k)}$ quand une décomposition de largeur de clique $k$ est donné en entrée.Finalement, nous prouvons qu'on peut compter en temps polynomial le nombre de transversaux minimaux d'hypergraphes $\beta$-acyclique ainsi que le nombre de dominants minimaux de graphes fortement triangulés.Tous ces résultats offrent des pistes prometteuses en vue d'une généralisation des largeurs et de leurs applications algorithmiquesIn the last decades, considerable efforts have been spent to characterize what makes NP-hard problems tractable. A successful approach in this line of research is the theory of parameterized complexity introduced by Downey and Fellows in the nineties.In this framework, the complexity of a problem is not measured only in terms of the input size, but also in terms of a parameter on the input.One of the most well-studied parameters is tree-width, a graph parameter which measures how close a graph is to the topological structure of a tree.It appears that tree-width has numerous structural properties and algorithmic applications.However, only sparse graph classes can have bounded tree-width.But, many NP-hard problems are tractable on dense graph classes.Most of the time, this tractability can be explained by the ability of these graphs to be recursively decomposable along vertex bipartitions $(A,B)$ where the adjacency between $A$ and $B$ is simple to describe.A lot of graph parameters -- called width measures -- have been defined to characterize this ability, the most remarkable ones are certainly clique-width, rank-width, and mim-width.In this thesis, we study the algorithmic properties of these width measures.We provide a framework that generalizes and simplifies the tools developed for tree-width and for problems with a constraint of acyclicity or connectivity such as Connected Vertex Cover, Connected Dominating Set, Feedback Vertex Set, etc.For all these problems, we obtain $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ time algorithms parameterized respectively by clique-width, Q-rank-width, rank-width and mim-width.We also prove that there exists an algorithm solving Hamiltonian Cycle in time $n^{O(k)}$, when a clique-width decomposition of width $k$ is given.Finally, we prove that we can count in polynomial time the minimal transversals of $\beta$-acyclic hypergraphs and the minimal dominating sets of strongly chordal graphs.All these results offer promising perspectives towards a generalization of width measures and their algorithmic applications
25
Granholm, Jonas. "Some cyclic properties of graphs with local Ore-type conditions." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-129213.
Full textAbstract:
A Hamilton cycle in a graph is a cycle that passes through every vertex of the graph. A graph is called Hamiltonian if it contains such a cycle. In this thesis we investigate two classes of graphs, defined by local criteria. Graphs in these classes, with a simple set of exceptions K, were proven to be Hamiltonian by Asratian, Broersma, van den Heuvel, and Veldman in 1996 and by Asratian in 2006, respectively. We prove here that in addition to being Hamiltonian, graphs in these classes have stronger cyclic properties. In particular, we prove that if a graph G belongs to one of these classes, then for each vertex x in G there is a sequence of cycles such that each cycle contains the vertex x, and the shortest cycle in the sequence has length at most 5; the longest cycle in the sequence is a Hamilton cycle (unless G belongs to the set of exceptions K, in which case the longest cycle in the sequence contains all but one vertex of G); each cycle in the sequence except the first contains all vertices of the previous cycle, and at most two other vertices. Furthermore, for each edge e in G that does not lie on a triangle, there is a sequence of cycles with the same three properties, such that each cycle in the sequence contains the edge e.
26
Borozan, Valentin. "Proper and weak-proper trees in edges-colored graphs and multigraphs." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00738959.
Full textAbstract:
Dans la présente thèse nous étudions l'extraction d'arbres dans des graphes arêtes-coloriés.Nous nous concentrons sur la recherche d'arbres couvrants proprement arête-coloriés et faiblement arête-coloriés, notée PST et WST. Nous montrons que les versions d'optimisation de ces problèmes sont NP-Complete dans le cas général des graphes arêtes-coloriés, et nous proposons des algorithmes pour trouver ces arbres dans le cas des graphes arêtes-coloriés sans cycles proprement arêtes-coloriés.Nous donnons également quelques limites de nonapproximabilité. Nous proposons des conditions suffisantes pour l'existence de la PST dans des graphes arêtes-coloriés (pas forcément propre), en fonction de différents paramètres de graphes, tels que : nombre total de couleurs, la connectivité et le nombre d'arêtes incidentes dedifférentes couleurs pour un sommet. Nous nous intéressons aux chemins hamiltoniens proprement arêtes-coloriés dans le casdes multigraphes arêtes-coloriés. Ils présentent de l'intérêt pour notre étude, car ce sontégalement des arbres couvrants proprement arêtes-coloriés. Nous établissons des conditions suffisantes pour qu'un multigraphe contienne un chemin hamiltonien proprement arêtes-coloriés, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré d'arêtes, etc. Puisque l'une des conditions suffisantes pour l'existence des arbres couvrants proprement arêtes-coloriés est la connectivité, nous prouvons plusieurs bornes supérieures pour le plus petit nombre de couleurs nécessaires pour la k-connectivité-propre. Nous énonçons plusieurs conjectures pour les graphes généraux et bipartis, et on arrive à les prouver pour k = 1.
27
Montero, Leandro Pedro. "Graphes et couleurs : graphes arêtes-coloriés, coloration d'arêtes et connexité propre." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00776899.
Full textAbstract:
Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtes-coloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu $O(n^4)$ pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément, 1) Nous étudions d'abord le nombre $k$-connexité-propre des graphes, noté $pc_k(G)$, ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre chaque paire de sommets, ils existent $k$ chemins intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour $pc_k(G)$. Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où $k = 1$. 2) Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc. 3) Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe $k$-dégénéré où, $k$ est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux. 4) Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme $O(n+m)$ pour reconnaître les graphes convergents et divergents en améliorant l'algorithme $O(n^4)$.
28
Sun, Qiang. "A contribution to the theory of (signed) graph homomorphism bound and Hamiltonicity." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLS109/document.
Full textAbstract:
Dans cette thèse, nous etudions deux principaux problèmes de la théorie des graphes: problème d’homomorphisme des graphes planaires (signés) et problème de cycle hamiltonien.Comme une extension du théorème des quatre couleurs, il est conjecturé([80], [41]) que chaque graphe signé cohérent planaire de déséquilibré-maille d+1(d>1) admet un homomorphisme à cube projective signé SPC(d) de dimension d. La question suivant étalés naturelle:Est-ce que SPC(d) une borne optimale de déséquilibré-maille d+1 pour tous les graphes signés cohérente planaire de déséquilibré-maille d+1?Au Chapitre 2, nous prouvons que: si (B,Ω) est un graphe signé cohérente dedéséquilibré-maille d qui borne la classe des graphes signés cohérents planaires de déséquilibré-maille d+1, puis |B| ≥2^{d−1}. Notre résultat montre que si la conjecture ci-dessus est vérifiée, alors le SPC(d) est une borne optimale à la fois en terme du nombre des sommets et du nombre de arêtes.Lorsque d=2k, le problème est équivalent aux problème des graphes:est-ce que PC(2k) une borne optimale de impair-maille 2k+1 pour P_{2k+1} (tous les graphes planaires de impair-maille au moins 2k+1)? Notez que les graphes K_4-mineur libres sont les graphes planaires, est PC(2k) aussi une borne optimale de impair-maille 2k+1 pour tous les graphes K_4-mineur libres de impair-maille 2k+1? La réponse est négative, dans[6], est donné une famille de graphes d’ordre O(k^2) que borne les graphes K_4-mineur libres de impair-maille 2k+1. Est-ce que la borne optimale? Au Chapitre 3, nous prouvons que: si B est un graphe de impair-maille 2k+1 qui borne tous les graphes K_4-mineur libres de impair-maille 2k+1, alors |B|≥(k+1)(k+2)/2. La conjonction de nos résultat et le résultat dans [6] montre que l’ordre O(k^2) est optimal. En outre, si PC(2k) borne P_{2k+1}, PC(2k) borne également P_{2r+1}(r>k).Cependant, dans ce cas, nous croyons qu’un sous-graphe propre de P(2k) serait suffisant à borner P_{2r+1}, alors quel est le sous-graphe optimal de PC2k) qui borne P_{2r+1}? Le premier cas non résolu est k=3 et r= 5. Dans ce cas, Naserasr [81] a conjecturé que le graphe Coxeter borne P_{11}. Au Chapitre 4, nous vérifions cette conjecture pour P_{17}.Au Chapitres 5, 6, nous étudions les problèmes du cycle hamiltonien. Dirac amontré en 1952 que chaque graphe d’ordre n est hamiltonien si tout sommet a un degré au moins n/2. Depuis, de nombreux résultats généralisant le théorème de Dirac sur les degré ont été obtenus. Une approche consiste à construire un cycle hamiltonien à partir d'un ensemble de sommets en contrôlant leur position sur le cycle. Dans cette thèse, nous considérons deux conjectures connexes. La première est la conjecture d'Enomoto: si G est un graphe d’ordre n≥3 et δ(G)≥n/2+1, pour toute paire de sommets x,y dans G, il y a un cycle hamiltonien C de G tel que dist_C(x,y)=n/2.Notez que l’ ́etat de degre de la conjecture de Enomoto est forte. Motivé par cette conjecture, il a prouvé, dans [32], qu’une paire de sommets peut être posé des distances pas plus de n/6 sur un cycle hamiltonien. Dans [33], les cas δ(G)≥(n+k)/2 sont considérés, il a prouvé qu’une paire de sommets à une distance entre 2 à k peut être posé sur un cycle hamiltonien. En outre, Faudree et Li ont proposé une conjecture plus générale: si G est un graphe d’ordre n≥3 et δ(G)≥n/2+1, pour toute paire de sommets x,y dans G et tout entier 2≤k≤n/2, il existe un cycle hamiltonien C de G tel que dist_C(x,y)=k. Utilisant de Regularity Lemma et Blow-up Lemma, au chapitre 5, nous donnons une preuve de la conjeture d'Enomoto conjecture pour les graphes suffisamment grand, et dans le chapitre 6, nous donnons une preuve de la conjecture de Faudree et Li pour les graphe suffisamment grandIn this thesis, we study two main problems in graph theory: homomorphism problem of planar (signed) graphs and Hamiltonian cycle problem.As an extension of the Four-Color Theorem, it is conjectured ([80],[41]) that every planar consistent signed graph of unbalanced-girth d+1(d>1) admits a homomorphism to signed projective cube SPC(d) of dimension d. It is naturally asked that:Is SPC(d) an optimal bound of unbalanced-girth d+1 for all planar consistent signed graphs of unbalanced-girth d+1?In Chapter 2, we prove that: if (B,Ω) is a consistent signed graph of unbalanced-girth d which bounds the class of consistent signed planar graphs of unbalanced-girth d, then |B|≥2^{d-1}. Furthermore,if no subgraph of (B,Ω) bounds the same class, δ(B)≥d, and therefore,|E(B)|≥d·2^{d-2}.Our result shows that if the conjecture above holds, then the SPC(d) is an optimal bound both in terms of number of vertices and number of edges.When d=2k, the problem is equivalent to the homomorphisms of graphs: isPC(2k) an optimal bound of odd-girth 2k+1 for P_{2k+1}(the class of all planar graphs of odd-girth at least 2k+1)? Note that K_4-minor free graphs are planar graphs, is PC(2k) also an optimal bound of odd-girth 2k+1 for all K_4-minor free graphs of odd-girth 2k+1 ? The answer is negative, in [6], a family of graphs of order O(k^2) bounding the K_4-minor free graphs of odd-girth 2k+1 were given. Is this an optimal bound? In Chapter 3, we prove that: if B is a graph of odd-girth 2k+1 which bounds all the K_4-minor free graphs of odd-girth 2k+1,then |B|≥(k+1)(k+2)/2. Our result together with the result in [6] shows that order O(k^2) is optimal.Furthermore, if PC(2k) bounds P_{2k+1},then PC(2k) also bounds P_{2r+1}(r>k). However, in this case we believe that a proper subgraph of PC(2k) would suffice to bound P_{2r+1}, then what’s the optimal subgraph of PC(2k) that bounds P_{2r+1}? The first case of this problem which is not studied is k=3 and r=5. For this case, Naserasr [81] conjectured that the Coxeter graph bounds P_{11} . Supporting this conjecture, in Chapter 4, we prove that the Coxeter graph bounds P_{17}.In Chapter 5,6, we study the Hamiltonian cycle problems. Dirac showed in 1952that every graph of order n is Hamiltonian if any vertex is of degree at least n/2. This result started a new approach to develop sufficient conditions on degrees for a graph to be Hamiltonian. Many results have been obtained in generalization of Dirac’s theorem. In the results to strengthen Dirac’s theorem, there is an interesting research area: to control the placement of a set of vertices on a Hamiltonian cycle such that thesevertices have some certain distances among them on the Hamiltonian cycle.In this thesis, we consider two related conjectures, one is given by Enomoto: if G is a graph of order n≥3, and δ(G)≥n/2+1, then for any pair of vertices x, y in G, there is a Hamiltonian cycle C of G such that dist_C(x, y)=n/2. Motivated by this conjecture, it is proved,in [32],that a pair of vertices are located at distances no more than n/6 on a Hamiltonian cycle. In [33], the cases δ(G) ≥(n+k)/2 are considered, it is proved that a pair of vertices can be located at any given distance from 2 to k on a Hamiltonian cycle. Moreover, Faudree and Li proposed a more general conjecture: if G is a graph of order n≥3, and δ(G)≥n/2+1, then for any pair of vertices x, y in G andany integer 2≤k≤n/2, there is a Hamiltonian cycle C of G such that dist_C(x, y) = k. Using Regularity Lemma and Blow-up Lemma, in Chapter 5, we give a proof ofEnomoto’s conjecture for graphs of sufficiently large order, and in Chapter 6, we give a proof of Faudree and Li’s conjecture for graphs of sufficiently large order
29
Manoussakis, Yannis. "Existence de cycles et chaines dans des graphes orientés ou non en liaison avec des paramètres de ces graphes (connexité, stabilité, degré)." Paris 11, 1985. http://www.theses.fr/1985PA112038.
Full textAbstract:
Dans cette thèse nous avons étudié, pour des graphes non orientés ou orientés, des conditions impliquant l'existence de : - cycles hamiltoniens, -cycles de longueur supérieure à une borne donnée. - chaînes de longueur bornée inférieurement ou supérieurement (problèmes de diamètre et de graphes hamilton-connectés). -une couverture des sommets par des cycles. Ces conditions concernent l'ordre, la taille, la connexité, la stabilité et les degrés du grapheIn this thesis we study conditions which imply for graphs or digraphs the existence of: - Hamiltonian cycles. - Cycles of length greater than a given bound. - Paths of bounded length (problems of diameter and of Hamilton-connected graphs). - Cycle coverings for the vertices. These conditions concern the order, the size, the connectivity, the independence number and the degrees of the graphs
30
Hocini, Fadila. "Combinatoire énumérative de plusieurs structures finies." Paris 6, 1986. http://www.theses.fr/1986PA066210.
Full textAbstract:
On construit deux bijections entre d'une part l'ensemble des "forêts standards ordinaires" et l'ensemble des "ponts ordinaires" et d'autre part entre l'ensemble des "forêts standards pondérés" et l'ensemble des "ponts faiblement surdiagonaux dont les longueurs des sauts et des paliers sont paires". On construit aussi une bijection entre l'ensemble des "forêts standards pondérés de poids n, ayant deux arbres" et l'ensemble des "forêts standards pondérés de poids n, ayant trois arbres.
31
Santos, Marcelo de Souza. "Ciclos hamiltonianos em grafos." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2016. http://hdl.handle.net/10183/150239.
Full textAbstract:
Neste trabalho tratamos de um problema clássico bem conhecido em Teoria dos Grafos: o problema da existência de um ciclo hamiltoniano. Um grafo é dito hamiltoniano se possui um ciclo hamiltoniano, ou seja, apresenta um ciclo que percorre todos os vértices do grafo. Estudamos problemas clássicos associados a este problema em termos do número de arestas, do grau mínimo e da sequência de graus dos vértices de um grafo. Além disso, estudamos resultados espectrais para o problema de hamiltonicidade referentes às matrizes de adjacências e laplaciana. A principal contribuição deste trabalho é a apresentação detalhada de condições suficientes e condições necessárias que garantem um ciclo hamiltoniano em um grafo já existentes na bibliografia.In this work we study a well-known problem in Graph Theory: the existence of a Hamilton cycle, namely a cycle that goes through every vertex in the graph. We consider classical su cient conditions related with this problem in terms of the number of edges, the minimum degree and the vertex degree sequence of a graph. Furthermore, we study spectral results for the hamiltonian problem in terms of the adjacency and laplacian matrix. The main contribution of this work is our detailed presentation of necessary and su cient conditions for the existence of a Hamilton cycle in a graph.
32
Lignos, Ioannis. "Reconfigurations of combinatorial problems : graph colouring and Hamiltonian cycle." Thesis, Durham University, 2017. http://etheses.dur.ac.uk/12098/.
Full textAbstract:
We explore algorithmic aspects of two known combinatorial problems, Graph Colouring and Hamiltonian Cycle, by examining properties of their solution space. One can model the set of solutions of a combinatorial problem $P$ by the solution graph $R(P)$, where vertices are solutions of $P$ and there is an edge between two vertices, when the two corresponding solutions satisfy an adjacency reconfiguration rule. For example, we can define the reconfiguration rule for graph colouring to be that two solutions are adjacent when they differ in colour in exactly one vertex. The exploration of the properties of the solution graph $R(P)$ can give rise to interesting questions. The connectivity of $R(P)$ is the most prominent question in this research area. This is reasonable, since the main motivation for modelling combinatorial solutions as a graph is to be able to transform one into the other in a stepwise fashion, by following paths between solutions in the graph. Connectivity questions can be made binary, that is expressed as decision problems which accept a 'yes' or 'no' answer. For example, given two specific solutions, is there a path between them? Is the graph of solutions $R(P)$ connected? In this thesis, we first show that the diameter of the solution graph $R_{l}(G)$ of vertex $l$-colourings of k-colourable chordal and chordal bipartite graphs $G$ is $O(n^2)$, where $l > k$ and n is the number of vertices of $G$. Then, we formulate a decision problem on the connectivity of the graph colouring solution graph, where we allow extra colours to be used in order to enforce a path between two colourings with no path between them. We give some results for general instances and we also explore what kind of graphs pose a challenge to determine the complexity of the problem for general instances. Finally, we give a linear algorithm which decides whether there is a path between two solutions of the Hamiltonian Cycle Problem for graphs of maximum degree five, and thus providing insights towards the complexity classification of the decision problem.
33
Bajo, Calderon Erica. "An Exploration on the Hamiltonicity of Cayley Digraphs." Youngstown State University / OhioLINK, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=ysu161982054497591.
Full text
34
Fraisse, Pierre. "Longs cycles dans les graphes : applications aux réseaux de Pétri." Paris 11, 1986. http://www.theses.fr/1986PA112037.
Full textAbstract:
Cette thèse se compose de plusieurs chapitres. Le premier porte sur l’existence de certains longs cycles dans des graphes de grand degré, cycles hamiltoniens et p-dominants en particulier. Il se compose des articles 1 à 5. Le second porte sur les facteurs de graphes, et contient les articles 6 à 7. Le troisième porter sur les couvertures des arêtes et des sommets d’un graphe par une famille de cycles de longueur totale minimale (article 8). Le quatrième donne un premier résultat sur l’index chromatique des graphes aléatoires réguliers. Il permet de conjecturer que presque tout graphe r-régulier est r-arête-coloriable (article 9). Enfin le cinquième traite d’une application de la théorie des graphes à la théorie des réseaux de Pétri (article 10)This thesis is constituted by several chapters. The first one deals with the existence of certain cycles in graphs of large degree. It gives sufficient conditions for the existence of cycles of length greater than a given number m, or dominating cycles, or circuits containing a set of s vertices and of length at most 2s. The second one gives sufficient conditions for the existence of f-factors in graphs, with conditions on the independence number, connectivity and number of edges, and also by assuming the existence of f-factors in some subgraphs. The third deals with covering of edges and vertices of a graph by cycles, the sum of the length of the cycles being minimal. The fourth attempts to find the chromatic index of random regular graphs. Finally, the fifth is an application of the graph theory to Petri nets. It gives sufficient conditions for liveness on a class of nets
35
Chera, Catalin-Marian. "Contribution à l'extension de l'approche énergétique à la représentation des systèmes à paramètres distribués." Phd thesis, Ecole Centrale de Lille, 2009. http://tel.archives-ouvertes.fr/tel-00578842.
Full textAbstract:
Tout phénomène, qu'il soit biologique, géologique ou mécanique peut être décrit à l'aide de lois de la physique en termes d'équations différentielles, algébriques ou intégrales, mettant en relation différentes variables physiques. Les objectifs de la thèse sont de montrer comment les systèmes à paramètres distribués peuvent être modélisés par un modèle bond graph, qui est par nature un modèle à paramètres localisés. Deux approches sont possibles : - utiliser une technique d'approximation qui discrétise le modèle initialement sous forme d'équations aux dérivées partielles (EDP) dans le domaine spatial, en supposant que les phénomènes physiques distribués peuvent être considérés comme homogènes dans certaines parties de l'espace, donc localisés. - déterminer la solution des EDP qui dépend du temps et de l'espace, puis à approximer cette solution avec différents outils numériques. Le premier chapitre rappelle quelques méthodes classiques utilisées pour l'approximation des EDP et les modèles bond graphs correspondants.Dans le deuxième chapitre, l'approche port-Hamiltonienne est présentée et son extension aux systèmes à paramètres distribués est proposée. Dans le troisième chapitre, les principaux modèles utilisés pour la représentation des flux de trafic routier sont rappelés et mis en œuvre en simulation. Ceci conduit à des comparaisons, d'une part entre différentes méthodes de résolution numérique et d'autre part entre différents modèles. Dans le quatrième chapitre, une approche originale propose d'étendre la représentation bond graph issue de la méthodologie Computational Fluid Dynamics au flux de trafic, en utilisant un modèle EDP à deux équations proposé par Jiang
36
Gancarzewicz, Grzegorz. "Problèmes extrémaux en théorie des graphes, généralisations du problème hamiltonien." Paris 11, 2004. http://www.theses.fr/2004PA112105.
Full textAbstract:
La description de la théorie extrémale des graphes donnée par B. Bollobásest la suivante :La théorie extrémale des graphes est une branche de la théorie des graphes qui consiste à trouver des relations entre divers invariants de graphes comme l'ordre, les degrés maximum et minimum, le minimum de la somme des degrés pris pour toute paire de sommets non adjacents. Plus généralement, à trouver les valeurs extrêmes de ces invariants qui assurent qu'un graphe possède une propriété donnée. Dans un graphe G un cycle qui contient tous les sommets de G est un cycle hamiltonien de G, Un graphe est hamiltonien si et seulement s'il contient un cycle hamiltonien. En général, le problème hamiltonien est un problème qui consiste à trouver des conditions suffisantes pour qu'un graphe possède un chemin hamiltonien ou un cycle hamiltonien. C'est l'un des problèmes les plus connus en théorie des graphes. Deux des résultats les plus connus de ce type sont le résultat de O. Ore sur la somme des degrés des sommets indépendants et le résultat de G. Fan sur le maximum des degrés des sommets de distance 2. Nous donnons quelques généralisations de ces deux theorèmes. Avec des conditions portants sur les degrés des sommets nous obtenons des cycles hamiltoniens ou non, contenant un couplage ou des cycles contenant un ensemble donné des sommets. Les résultats sont obtenus pour n'importe quel graphe ou dans le cas particulier des graphes bipartis. Dans certains cas, nous donnons des exemples qui montrent que les résultats obtenus sont les meilleurs possiblesThe description of extremal graph theory given by B. Bollob\'as is the following:Extremal graph theory is a branch of graph theory concerning with finding relations between various graph invariants like order, minimal and maximal degrees, minimal sum of degrees of nonadjacent vertices. More generally, with finding the extremal values of these invariants ensuring that a graph has a given property. Note that many problems in graph theory could be formulated as extremal problems. In a graph G a cycle that contains every vertex of G is called a hamiltonian cycle of G. A graph is Hamiltonian iff it contains a hamiltonian cycle. In general the hamiltonian problem is a problem concerning with finding sufficient conditions under which the graph has a hamiltonian path or cycle. It is one of the most known problems in graph theory. Two of the most known results of this type are the result of O. Ore with the sum of degrees of independent vertices and the result of G. Fan with the maximum of degrees of vertices of distance two. We give some generalization of these results. Under conditions on the sum of degrees of independent vertices we obtain a cycle or a hamiltonian cycle containing a set of independent edges or a cycle containing a given set of vertices. The obtained results are for arbitrary graphs or for the special case of bipartite graphs. In some cases we give examples showing that the results are best possible
37
Bruno, Nicholas J. "A Sufficient Condition for Hamiltonian Connectedness in Standard 2-Colored Multigraphs." Miami University / OhioLINK, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=miami1438385443.
Full text
38
Costa, Polyanna Possani da [UNESP]. "Teoria dos grafos e suas aplicações." Universidade Estadual Paulista (UNESP), 2011. http://hdl.handle.net/11449/94358.
Full textAbstract:
Made available in DSpace on 2014-06-11T19:27:10Z (GMT). No. of bitstreams: 0
Previous issue date: 2011-12-01Bitstream added on 2014-06-13T19:06:46Z : No. of bitstreams: 1
costa_pp_me_rcla.pdf: 598986 bytes, checksum: 67c1c7e0c368ded41dbfb9631bdf1362 (MD5)Neste trabalho estudamos a Teoria de Grafos e a aplicamos na solução de alguns problemas clássicos, como por exemplo O Problema das Pontes de Königsberg, O Problema do Caixeiro Viajante, Classificação dos Poliedros Regulares e Coloração de Mapas. As ferramentas básicas foram Topologia Geral e Álgebra
In this work we study Graph Theory and we apply it in the solution of some classical problems, for example Königsberg Bridges Problem, Travelling Salesman Problem, Classification of Regular Polyhedra and Map Coloring. The prerequisites are General Topology and Algebra
39
Pucohuaranga, Jorge Luis Barbieri. "Ciclos hamiltonianos em produtos cartesianos de grafos." reponame:Repositório Institucional da UFABC, 2015.
Find full textAbstract:
Orientador: Prof. Dr. Letícia Rodrigues BuenoDissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2015.
Given a graph G, the hamiltonian cycle problem consists in determining if there is a cycle containing all vertices of G exactly once. This problem is known to be NP-Complete, therefore a recent trend is to searching for long cycles in order to determine the cycle with the largest possible number of vertices. Another trend is searching for related structures. In this aspect, being prism-hamiltonian has been an interesting relaxation of being hamiltonian. The prism over a graph G consists of two copies of G with an edge joining the corresponding vertices. A graph G is prism-hamiltonian if the prism over G contains a hamiltonian cycle. In this work, we study a conjecture which claims that every 4-connected 4-regular graph is prism-hamiltonian. We prove the conjecture for claw-free graphs. In fact, for a subclass of claw-free 4-connected 4-regular graphs, we prove a stronger result: its hamiltonicity; therefore, corroborating to another conjecture from 1993 which states that claw-free 4-connected 4-regular graphs are hamiltonian. Given a graph G, let G1 = GK2 and Gq = Gq..1K2, for q > 1. For every connected graph G, we prove that Gq is hamiltonian for q dlog2 (G)e, where (G) is the maximum degree of G.
40
Costa, Polyanna Possani da. "Teoria dos grafos e suas aplicações /." Rio Claro : [s.n.], 2011. http://hdl.handle.net/11449/94358.
Full textAbstract:
Orientador: Thiago de MeloBanca: Elíris Cristina Rizziolli
Banca: Luiz Roberto Hartmann Junior
Resumo: Neste trabalho estudamos a Teoria de Grafos e a aplicamos na solução de alguns problemas clássicos, como por exemplo O Problema das Pontes de Königsberg, O Problema do Caixeiro Viajante, Classificação dos Poliedros Regulares e Coloração de Mapas. As ferramentas básicas foram Topologia Geral e Álgebra
Abstract: In this work we study Graph Theory and we apply it in the solution of some classical problems, for example Königsberg Bridges Problem, Travelling Salesman Problem, Classification of Regular Polyhedra and Map Coloring. The prerequisites are General Topology and Algebra
Mestre
41
Al-Mashhadani, Israa Badr. "Integrating bond graph with Port-Hamiltonian formulation for memristor non-linear circuit elements." Thesis, University of Reading, 2017. http://centaur.reading.ac.uk/78141/.
Full textAbstract:
The discovery of flux controlled memristors (Memory Resistor) by Leon Chua in 1971 as the missing element relating flux to charge, opens up possibilities for the development of a novel class of dielectrics over the coming years. With memristive components there is a departure from linearity; and components exhibit nonlinear characteristics. These properties enable the memristive elements to be used for the successful modeling of a number of physical devices and systems. The Bond Graph is one of graph theory modeling techniques, whose graphical description directly reveals the allocation and management of energy in the system (storage and dissipation) as well as the interconnection structure through which internal and external power exchange occurs via power ports. The graphical expansion of bond graph with the causal relationships among the system variables leads into a formulation of different types of mathematical models such as Port-Hamiltonian Systems. Incorporation of memory based elements leads to circuits with far more complex behaviour than normal dielectrics display. System dynamics may be studied using differential algebraic models arising from descriptor representations of the derived Port-Hamiltonian systems through Bond graph analysis. A derivation of unique generic Input-State-Output Port-Hamiltonian (ISO PHS) formulation from Bond graph representation of memristive circuits is proposed, which is suitable for simulation as well as providing engineering insight through analysis. In the proposed framework, the dissipation field splits into resistive and memristive parts in order to derive the Input-State-Output Port-Hamiltonian expressions and discuss different classes of systems of the proposed framework. Applications of the generic bond graph ISO PHS formulation using case studies with a memristive element are presented as examples of the proposed analysis. Consistency of the formulation is shown with transfer function formulations as well as with hybrid systems modelling. The nonlinear bond graph port-Hamiltonian methodology has applications in nonlinear network analysis and enables the formulation of input-output models of complex components embedded in non-linear circuits and systems.
42
Carvalho, Marcelo Dantas de. "Classificação dos digrafos semicompletos hamiltonianos." [s.n.], 2000. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306861.
Full textAbstract:
Orientador: Claudina Izepe RodriguesDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-07-26T16:57:25Z (GMT). No. of bitstreams: 1 Carvalho_MarceloDantasde_M.pdf: 1298387 bytes, checksum: 14167c08257e5465066717df5f9963e6 (MD5) Previous issue date: 2000
Resumo: 0 objetivo principal deste trabalho é apresentar uma classificação para os dígrafos semicompletos hamiltonianos, extendendo os resultados obtidos para os torneios. Para isso utilizamos da teoria da homotopia regular de grafos de Davide C. Demaria, apresentando resultados sobre torneios simplemente desconexos, a caracterização de torneios por 3-ciclos e o conceito de ciclo conado e não-conado para dígrafos, introduzido por Kiihl e Tironi. Com a noção de ciclo minimal e característico para dígrafo uma classificação para os dígrafos semicompletos hamiltonianos surge então naturalmente. Esses resultados, quando encontrados para torneios, proporcionaram a obtenção de uma classe de torneios reconstrutíveis (torneios normais) e pesquisa nesse sentido deve ser efetuada para dígrafos. Apresentamos em apêndice a matriz de um dígrafo, os torneios de moon, normais e, brevemente, o problema da reconstrução de grafos
Abstract: The main target in this work is to present a classification for the hamiltonian semicomplete digraphs, extending the results previously obtained for the tournaments. In this way we apply the regular homotopy of finite directed graphs theory developed by Davide G. Demaria, presenting results on simply disconnected tournaments, on the caracterization of tournaments by 3-cicles and the concept of coned and non-coned cicle for digraphs, introduced by Kiihl and Tironi. With the notion of minimal and caracteristic cicle we naturally get a classification of the semicomplete hamiltonian digraphs. These results, when used for tournaments led to a new class of reconstructible ones (named normal) and future research on the extension of these results for digraphs in general seems to be interesting. We present in appendixes the array of a digraph, the tournaments of Moon, Normal and, briefly, the reconstruction problem for graphs
Mestrado
Mestre em Matemática
43
Amar, Denise. "Théorie des graphes, étude de cycles dans les graphes orientés et non orientés : plus long cycle, cycles de longueur donnée, hamiltonisme, pancyclisme." Bordeaux 1, 1985. http://www.theses.fr/1985BOR10617.
Full textAbstract:
Etude des cycles d'un graphe oriente ou non, satisfaisant des conditions sur divers parametres : stabilite, connexite, degre minimum, nombre d'aretes. Problemes concernant la longueur maximum d'un cycle, l'hamiltonisme, le pancyclisme, la couverture des sommets du graphe par des cycles de longueur fixee. Problemes algorithmiques
44
Adamus, Lech. "Sufficient conditions for existence of long cycles in graphs." Paris 11, 2008. http://www.theses.fr/2008PA112203.
Full textAbstract:
Le but de cette thèse est de présenter des conditions suffisantes pour l'existence de longs cycles dans les graphes simples et les graphes orientés, c'est à dire des cycles passant par plus de la moitié des sommets d'un graphe donné. Plus précisément, nous voulons trouver la taille minimale d'un graphe donné G garantissant qu'un cycle de longueur prescrite est contenu dans G. On pourra considérer une modification de cette condition en ajoutant une borne sur le degré minimum de G. Nous étudions ce problème pour les graphes simples, en particulier les graphes bipartis et aussi les graphes orientés dans lesquels on considère toutes les orientations possibles d'un cycle de longueur donnéeThe aim of this thesis is to present sufficient conditions for existence of long cycles in simple graphs and in directed graphs, that is, cycles which pass through more than half of the vertices in a given graph. Namely, we want to find the minimal size of a given graph G guaranteeing that a cycle of prescribed length is contained in G. Optionally we consider a modification of this condition by adding a bound on the minimal degree of G. We investigate this problem for simple graphs, particularly bipartite, and also for digraphs, where all possible orientations of a cycle of given length are considered
45
Kadi, Abderrezzak Mohamed El. "Existence de cycles dans les graphes bipartis et dans plusieurs familles de graphes généralisant la classe des graphes sans K₁,₃." Paris 11, 1999. http://www.theses.fr/1999PA112401.
Full textAbstract:
Dans cette thèse, nous apportons une contribution à l'étude de l'existence de cycles de longueur donnée dans certaines familles de graphes. La thèse se divise en deux parties. La première partie est dédiée aux graphes bipartis. Nous nous y intéressons aux graphes bipartis équilibrés hamiltoniens, bipancycliques, S-cyclables et S-pancyclables. Les conditions envisagées portent sur les degrés, le nombre d'indépendance biparti et la k-bifermeture. La seconde partie concerne les graphes sans K₁,₃ que nous appellerons aussi graphes "claw-free". On examine dans cette partie plusieurs familles de graphes qui généralisent la classe des graphes sans K₁,₃ , en particulier la famille des graphes λ-claw-free et celle des graphes sans S(K₁,₃), et l'on s'intéresse aux propriétés d'existence de cycles dans ces familles de graphes ou dans leurs carrésIn this thesis, we study sufficient conditions for the existence of cycles of given length in several families of graphs. The thesis consists of two parts: The first one is dedicated to bipartite graphs. We consider mainly bipartite balanced graphs that are hamiltonian, bipancyclic, S-cyclable and S-pancyclable. The conditions we investigate concern degree, independence number and k-biclosure. The second part concerns claw-free graphs. We examine several families that generalize the claw-free graphs family, mainly the λ-claw-free graphs and the S(K₁,₃)-free graphs. We look for sufficient conditions that insure some special cycles in those families of graphs or in their squares
46
Jurkiewicz, Samuel. "Theorie des graphes : cycles hamiltoniens, coloration d'aretes et problemes de pavages." Paris 6, 1996. http://www.theses.fr/1996PA066206.
Full textAbstract:
Ce travail aborde dans trois parties trois problemes de la theorie des graphes. Dans la premiere partie, cycles hamiltoniens et graphes planaires, nous developpons une procedure de construction de certaines familles de graphes planaires 3-connexes, hamiltoniens et non hamiltoniens. Ces graphes echappent aux caracterisations donnees par les theoremes de tutte et whitney d'une part (conditions suffisantes) et par le theoreme de grinberg d'autre part (conditions necessaires). Cette procedure s'avere utile pour la production d'exemples de graphes en vue de tester des heuristiques pour trouver des chemins hamiltoniens, ce qui est un probleme np-complet. Dans la deuxieme partie, generalisations du delta-sous-graphe pour les multigraphes, nous nous proposons d'etendre aux multigraphes des concepts deja utilises pour les colorations d'aretes d'un graphe simple. Dans la troisieme partie, pavages de figures par des dominos, nous developpons une procedure d'obtention systematique de tous les pavages d'une figure pavable, en mettant en evidence la structure de treillis formee par l'ensemble de ces pavages. Pour cela, nous commencons par exposer, dans le chapitre 7, des resultats specifiques obtenus a partir de la presentation par thurston, en 1990, d'un algorithme lineaire pour la pavage d'une figure plane par dominos, qui utilise l'approche de la theorie des groupes. Nous privilegions, cependant, l'approche de fournier, dont l'etude de l'algorithme de thurston met en evidence le rapport entre la pavabilite d'une figure et la condition de hall pour les couplages
47
Fernandes, Antonio M. "A study of nonlinear physical systems in generalized phase space." Virtual Press, 1996. http://liblink.bsu.edu/uhtbin/catkey/1020161.
Full textAbstract:
Classical mechanics provides a phase space representation of mechanical systems in terms of position and momentum state variables. The Hamiltonian system, a set of partial differential equations, defines a vector field in phase space and uniquely determines the evolutionary process of the system given its initial state.A closed form solution describing system trajectories in phase space is only possible if the system of differential equations defining the Hamiltonian is linear. For nonlinear cases approximate and qualitative methods are required.Generalized phase space methods do not confine state variables to position and momentum, allowing other observables to describe the system. Such a generalization adjusts the description of the system to the required information and provides a method for studying physical systems that are not strictly mechanical.This thesis presents and uses the methods of generalized phase space to compare linear to nonlinear systems.Ball State UniversityMuncie, IN 47306Department of Physics and Astronomy
48
Steelman, Andrea Elizabeth. "Degree sum ensuring hamiltonicity." [Pensacola, Fla.] : University of West Florida, 2007. http://purl.fcla.edu/fcla/etd/WFE0000012.
Full text
49
Gusmão, Andréia Cristina dos Santos. "Um algoritmo paralelo para ciclos Hamiltonianos em grafos Kneser." reponame:Repositório Institucional da UFABC, 2013.
Find full text
50
Lima, Nailson Amorim de. "Uma classificação para os torneios hamiltonianos." [s.n.], 1995. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307366.
Full textAbstract:
Orientador: Jose Carlos de Souza KuhlDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica
Made available in DSpace on 2018-07-20T13:55:09Z (GMT). No. of bitstreams: 1 Lima_NailsonAmorimde_M.pdf: 766815 bytes, checksum: b725105565b47ceb8ef745351ae2f179 (MD5) Previous issue date: 1995
Resumo: Não informado
Abstract: Not informed
Mestrado
Mestre em Matemática