Log in

Relevant bibliographies by topics / Rainbow Hamilton cycle / Journal articles

To see the other types of publications on this topic, follow the link: Rainbow Hamilton cycle.

Journal articles on the topic 'Rainbow Hamilton cycle'

Author: Grafiati

Published: 25 May 2024

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

Select a source type:

Consult the top 15 journal articles for your research on the topic 'Rainbow Hamilton cycle.'

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

Harvey, Nicholas, and Christopher Liaw. "Rainbow Hamilton cycles and lopsidependency." Discrete Mathematics 340, no. 6 (June 2017): 1261–70. http://dx.doi.org/10.1016/j.disc.2017.01.026.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Frieze, Alan, and Po-Shen Loh. "Rainbow hamilton cycles in random graphs." Random Structures & Algorithms 44, no. 3 (February 13, 2013): 328–54. http://dx.doi.org/10.1002/rsa.20475.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Janson, Svante, and Nicholas Wormald. "Rainbow Hamilton cycles in random regular graphs." Random Structures and Algorithms 30, no. 1-2 (2006): 35–49. http://dx.doi.org/10.1002/rsa.20146.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Bal, Deepak, and Alan Frieze. "Rainbow matchings and Hamilton cycles in random graphs." Random Structures & Algorithms 48, no. 3 (July 6, 2015): 503–23. http://dx.doi.org/10.1002/rsa.20594.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Aigner-Horev, Elad, and Dan Hefetz. "Rainbow Hamilton Cycles in Randomly Colored Randomly Perturbed Dense Graphs." SIAM Journal on Discrete Mathematics 35, no. 3 (January 2021): 1569–77. http://dx.doi.org/10.1137/20m1332992.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Dudek, Andrzej, and Michael Ferrara. "Extensions of Results on Rainbow Hamilton Cycles in Uniform Hypergraphs." Graphs and Combinatorics 31, no. 3 (December 29, 2013): 577–83. http://dx.doi.org/10.1007/s00373-013-1391-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Bal, Deepak, Patrick Bennett, Xavier Pérez-Giménez, and Paweł Prałat. "Rainbow perfect matchings and Hamilton cycles in the random geometric graph." Random Structures & Algorithms 51, no. 4 (April 5, 2017): 587–606. http://dx.doi.org/10.1002/rsa.20717.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Ding, Jili, Hong Bian, and Haizheng Yu. "Anti-Ramsey Numbers in Complete k-Partite Graphs." Mathematical Problems in Engineering 2020 (September 7, 2020): 1–5. http://dx.doi.org/10.1155/2020/5136104.

Full text

Abstract:

The anti-Ramsey number ARG,H is the maximum number of colors in an edge-coloring of G such that G contains no rainbow subgraphs isomorphic to H. In this paper, we discuss the anti-Ramsey numbers ARKp1,p2,…,pk,Tn, ARKp1,p2,…,pk,ℳ, and ARKp1,p2,…,pk,C of Kp1,p2,…,pk, where Tn,ℳ, and C denote the family of all spanning trees, the family of all perfect matchings, and the family of all Hamilton cycles in Kp1,p2,…,pk, respectively.

APA, Harvard, Vancouver, ISO, and other styles

9

Dudek, Andrzej, Sean English, and Alan Frieze. "On Rainbow Hamilton Cycles in Random Hypergraphs." Electronic Journal of Combinatorics 25, no. 2 (June 22, 2018). http://dx.doi.org/10.37236/7274.

Full text

Abstract:

Let $H_{n,p,r}^{(k)}$ denote a randomly colored random hypergraph, constructed on the vertex set $[n]$ by taking each $k$-tuple independently with probability $p$, and then independently coloring it with a random color from the set $[r]$. Let $H$ be a $k$-uniform hypergraph of order $n$. An $\ell$-Hamilton cycle is a spanning subhypergraph $C$ of $H$ with $n/(k-\ell)$ edges and such that for some cyclic ordering of the vertices each edge of $C$ consists of $k$ consecutive vertices and every pair of adjacent edges in $C$ intersects in precisely $\ell$ vertices.In this note we study the existence of rainbow $\ell$-Hamilton cycles (that is every edge receives a different color) in $H_{n,p,r}^{(k)}$. We mainly focus on the most restrictive case when $r = n/(k-\ell)$. In particular, we show that for the so called tight Hamilton cycles ($\ell=k-1$) $p = e^2/n$ is the sharp threshold for the existence of a rainbow tight Hamilton cycle in $H_{n,p,n}^{(k)}$ for each $k\ge 4$.

APA, Harvard, Vancouver, ISO, and other styles

10

Dudek, Andrzej, Alan Frieze, and Andrzej Ruciński. "Rainbow Hamilton Cycles in Uniform Hypergraphs." Electronic Journal of Combinatorics 19, no. 1 (February 23, 2012). http://dx.doi.org/10.37236/2055.

Full text

Abstract:

Let $K_n^{(k)}$ be the complete $k$-uniform hypergraph, $k\ge3$, and let $\ell$ be an integer such that $1\le \ell\le k-1$ and $k-\ell$ divides $n$. An $\ell$-overlapping Hamilton cycle in $K_n^{(k)}$ is a spanning subhypergraph $C$ of $K_n^{(k)}$ with $n/(k-\ell)$ edges and such that for some cyclic ordering of the vertices each edge of $C$ consists of $k$ consecutive vertices and every pair of adjacent edges in $C$ intersects in precisely $\ell$ vertices.We show that, for some constant $c=c(k,\ell)$ and sufficiently large $n$, for every coloring (partition) of the edges of $K_n^{(k)}$ which uses arbitrarily many colors but no color appears more than $cn^{k-\ell}$ times, there exists a rainbow $\ell$-overlapping Hamilton cycle $C$, that is every edge of $C$ receives a different color. We also prove that, for some constant $c'=c'(k,\ell)$ and sufficiently large $n$, for every coloring of the edges of $K_n^{(k)}$ in which the maximum degree of the subhypergraph induced by any single color is bounded by $c'n^{k-\ell}$, there exists a properly colored $\ell$-overlapping Hamilton cycle $C$, that is every two adjacent edges receive different colors. For $\ell=1$, both results are (trivially) best possible up to the constants. It is an open question if our results are also optimal for $2\le\ell\le k-1$.The proofs rely on a version of the Lovász Local Lemma and incorporate some ideas from Albert, Frieze, and Reed.

APA, Harvard, Vancouver, ISO, and other styles

11

Ferber, Asaf. "Closing Gaps in Problems related to Hamilton Cycles in Random Graphs and Hypergraphs." Electronic Journal of Combinatorics 22, no. 1 (March 6, 2015). http://dx.doi.org/10.37236/5025.

Full text

Abstract:

We show how to adjust a very nice coupling argument due to McDiarmid in order to prove/reprove in a novel way results concerning Hamilton cycles in various models of random graph and hypergraphs. In particular, we firstly show that for $k\geq 3$, if $pn^{k-1}/\log n$ tends to infinity, then a random $k$-uniform hypergraph on $n$ vertices, with edge probability $p$, with high probability (w.h.p.) contains a loose Hamilton cycle, provided that $(k-1)|n$. This generalizes results of Frieze, Dudek and Frieze, and reproves a result of Dudek, Frieze, Loh and Speiss. Secondly, we show that there exists $K>0$ such for every $p\geq (K\log n)/n$ the following holds: Let $G_{n,p}$ be a random graph on $n$ vertices with edge probability $p$, and suppose that its edges are being colored with $n$ colors uniformly at random. Then, w.h.p. the resulting graph contains a Hamilton cycle with for which all the colors appear (a rainbow Hamilton cycle). Bal and Frieze proved the latter statement for graphs on an even number of vertices, where for odd $n$ their $p$ was $\omega((\log n)/n)$. Lastly, we show that for $p=(1+o(1))(\log n)/n$, if we randomly color the edge set of a random directed graph $D_{n,p}$ with $(1+o(1))n$ colors, then w.h.p. one can find a rainbow Hamilton cycle where all the edges are directed in the same way.

APA, Harvard, Vancouver, ISO, and other styles

12

Frieze, Alan, and Xavier Pérez‐Giménez. "Rainbow Hamilton cycles in random geometric graphs." Random Structures & Algorithms, November 27, 2023. http://dx.doi.org/10.1002/rsa.21201.

Full text

Abstract:

AbstractLet be chosen independently and uniformly at random from the unit ‐dimensional cube . Let be given and let . The random geometric graph has vertex set and an edge whenever . We show that if each edge of is colored independently from one of colors and has the smallest value such that has minimum degree at least two, then contains a rainbow Hamilton cycle asymptotically almost surely.

APA, Harvard, Vancouver, ISO, and other styles

13

Katsamaktsis, Kyriakos, Shoham Letzter, and Amedeo Sgueglia. "Rainbow Hamiltonicity in uniformly coloured perturbed digraphs." Combinatorics, Probability and Computing, May 13, 2024, 1–19. http://dx.doi.org/10.1017/s0963548324000130.

Full text

Abstract:

Abstract We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed digraph. We show that for every $\delta \in (0,1)$ there exists $C = C(\delta ) \gt 0$ such that the following holds. Let $D_0$ be an $n$ -vertex digraph with minimum semidegree at least $\delta n$ and suppose that each edge of the union of $D_0$ with a copy of the random digraph $\mathbf{D}(n,C/n)$ on the same vertex set gets a colour in $[n]$ independently and uniformly at random. Then, with high probability, $D_0 \cup \mathbf{D}(n,C/n)$ has a rainbow directed Hamilton cycle. This improves a result of Aigner-Horev and Hefetz ((2021) SIAM J. Discrete Math.35(3) 1569–1577), who proved the same in the undirected setting when the edges are coloured uniformly in a set of $(1 + \varepsilon )n$ colours.

APA, Harvard, Vancouver, ISO, and other styles

14

Bell, Tolson, and Alan Frieze. "Rainbow powers of a Hamilton cycle in G_n,p." Journal of Graph Theory, November 5, 2023. http://dx.doi.org/10.1002/jgt.23054.

Full text

Abstract:

AbstractWe show that the threshold for having a rainbow copy of a power of a Hamilton cycle in a randomly edge colored copy of is within a constant factor of the uncolored threshold. Our proof requires times the minimum number of colors.

APA, Harvard, Vancouver, ISO, and other styles

15

Gupta, Pranshu, Fabian Hamann, Alp Müyesser, Olaf Parczyk, and Amedeo Sgueglia. "A general approach to transversal versions of Dirac-type theorems." European Conference on Combinatorics, Graph Theory and Applications, no. 12 (August 28, 2023). http://dx.doi.org/10.5817/cz.muni.eurocomb23-072.

Full text

Abstract:

Given a collection of hypergraphs $\fH=(H_1, \ldots, H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such that $e\in E(H_{\phi(e)})$ for each $e\in E(F)$. How large does the minimum degree of each $H_i$ need to be so that $\fH$ necessarily contains a copy of $F$ that is a transversal? Each $H_i$ in the collection could be the same hypergraph, hence the minimum degree of each $H_i$ needs to be large enough to ensure that $F\subseteq H_i$. Since its general introduction by Joos and Kim~[Bull. Lond. Math. Soc., 2020, 52(3): 498–504], a growing body of work has shown that in many cases this lower bound is tight. In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamilton cycles. For example, we derive that any collection of $rn$ graphs on an $n$-vertex set, each with minimum degree at least $(r/(r+1)+o(1))n$, contains a transversal copy of the $r$-th power of a Hamilton cycle. This can be viewed as a rainbow version of the P\‘osa-Seymour conjecture.

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!