Bibliografías temáticas / Partitioning into vertex-disjoint cycles / Artículos de revistas

Artículos de revistas sobre el tema "Partitioning into vertex-disjoint cycles"

Siga este enlace para ver otros tipos de publicaciones sobre el tema: Partitioning into vertex-disjoint cycles.
Autor: Grafiati
Publicado: 4 de mayo de 2024

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Consulte los 50 mejores artículos de revistas para su investigación sobre el tema "Partitioning into vertex-disjoint cycles".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Explore artículos de revistas sobre una amplia variedad de disciplinas y organice su bibliografía correctamente.

1

ŁUCZAK, TOMASZ, VOJTĚCH RÖDL y ENDRE SZEMERÉDI. "Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles". Combinatorics, Probability and Computing 7, n.º 4 (diciembre de 1998): 423–36. http://dx.doi.org/10.1017/s0963548398003599.

Texto completo
Resumen
We prove that there exists n0, such that, for every n[ges ]n0 and every 2-colouring of the edges of the complete graph Kn, one can find two vertex-disjoint monochromatic cycles of different colours which cover all vertices of Kn.
Los estilos APA, Harvard, Vancouver, ISO, etc.
2

Lin, Mugang, Jianxin Wang, Qilong Feng y Bin Fu. "Randomized Parameterized Algorithms for the Kidney Exchange Problem". Algorithms 12, n.º 2 (25 de febrero de 2019): 50. http://dx.doi.org/10.3390/a12020050.

Texto completo
Resumen
In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant L (typically 2 ≤ L ≤ 5), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases L = 3 and L ≥ 3 , and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively.
Los estilos APA, Harvard, Vancouver, ISO, etc.
3

Korostil, Alexander V. y Andrei V. Nikolaev. "Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph". Modeling and Analysis of Information Systems 28, n.º 1 (24 de marzo de 2021): 6–21. http://dx.doi.org/10.18255/1818-1015-2021-1-6-21.

Texto completo
Resumen
We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. It is known that verifying vertex non-adjacency in the 1-skeleton of the symmetric and asymmetric traveling salesperson polytopes is an NP-complete problem. On the other hand, a suffcient condition for two vertices to be non-adjacent can be formulated as a combinatorial problem of finding a Hamiltonian decomposition of a 4-regular multigraph. We present two backtracking algorithms for verifying vertex non-adjacency in the 1-skeleton of the traveling salesperson polytope and constructing a Hamiltonian decomposition: an algorithm based on a simple path extension and an algorithm based on the chain edge fixing procedure. Based on the results of the computational experiments for undirected multigraphs, both backtracking algorithms lost to the known heuristic general variable neighborhood search algorithm. However, for directed multigraphs, the algorithm based on chain fixing of edges showed comparable results with heuristics on instances with existing solutions, and better results on instances of the problem where the Hamiltonian decomposition does not exist.
Los estilos APA, Harvard, Vancouver, ISO, etc.
4

RAJASINGH, INDRA, M. AROCKIARAJ, BHARATI RAJAN y PAUL MANUEL. "CIRCULAR WIRELENGTH OF GENERALIZED PETERSEN GRAPHS". Journal of Interconnection Networks 12, n.º 04 (diciembre de 2011): 319–35. http://dx.doi.org/10.1142/s0219265911003027.

Texto completo
Resumen
In this paper we formulate the Vertex Congestion Lemma leading to a new technique in computing the exact wirelength of an embedding. We compute the circular wirelength of generalized Petersen graphs by partitioning the vertices as well as the edges of cycles. Further we obtain the linear wirelength of circular ladders. Our algorithms produce optimal values in linear time.
Los estilos APA, Harvard, Vancouver, ISO, etc.
5

Nöllenburg, Martin, Roman Prutkin y Ignaz Rutter. "Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions". International Journal of Computational Geometry & Applications 27, n.º 01n02 (marzo de 2017): 121–58. http://dx.doi.org/10.1142/s0218195917600068.

Texto completo
Resumen
A greedily routable region (GRR) is a closed subset of [Formula: see text], in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected.
Los estilos APA, Harvard, Vancouver, ISO, etc.
6

BODLAENDER, HANS L. "ON DISJOINT CYCLES". International Journal of Foundations of Computer Science 05, n.º 01 (marzo de 1994): 59–68. http://dx.doi.org/10.1142/s0129054194000049.

Texto completo
Resumen
It is shown, that for each constant k≥1, the following problems can be solved in [Formula: see text] time: given a graph G, determine whether G has k vertex disjoint cycles, determine whether G has k edge disjoint cycles, determine whether G has a feedback vertex set of size ≤k. Also, every class [Formula: see text], that is closed under minor taking, taking, and that does not contain the graph consisting of k disjoint copies of K3, has an [Formula: see text] membership test algorithm.
Los estilos APA, Harvard, Vancouver, ISO, etc.
7

Li, Jianping y George Steiner. "Partitioning a graph into vertex-disjoint paths". Studia Scientiarum Mathematicarum Hungarica 42, n.º 3 (1 de septiembre de 2005): 277–94. http://dx.doi.org/10.1556/sscmath.42.2005.3.3.

Texto completo
Resumen
Let G=(V,E) be a simple graph of order n. We consider the problem of partitioning G into vertex-disjoint paths. We obtain the following new results: (i) For any positive integer k, if dG(x)+dG(y) = n-k-1 for every pair x, y of nonadjacent vertices in G, then G can be partitioned into k vertex-disjoint paths, unless G belongs to certain classes of extremal graphs which we characterize; (ii) For the case k=2, we strengthen our result by showing that for any two positive integers p1 and p2 satisfying n= p1+ p2,if dG(x)+dG(y) = n-3 for every pair x, y of nonadjacent vertices in G and G does not belong to classes of exceptional graphs we define, then G can be partitioned into two vertex-disjoint paths P1 and P2 of order p1 and p2, respectively. These results are generalizations of some classical results of Dirac and Ore, and also lead to new sufficient conditions for the existence of a Hamilton path in a graph.
Los estilos APA, Harvard, Vancouver, ISO, etc.
8

VERSTRAËTE, JACQUES. "A Note on Vertex-Disjoint Cycles". Combinatorics, Probability and Computing 11, n.º 1 (enero de 2002): 97–102. http://dx.doi.org/10.1017/s0963548301004904.

Texto completo
Resumen
Häggkvist and Scott asked whether one can find a quadratic function q(k) such that, if G is a graph of minimum degree at least q(k), then G contains vertex-disjoint cycles of k consecutive even lengths. In this paper, it is shown that if G is a graph of average degree at least k2+19k+10 with sufficiently many vertices, then G contains vertex-disjoint cycles of k consecutive even lengths, answering the above question in the affirmative. The coefficient of k2 cannot be decreased and, in this sense, this result is best possible.
Los estilos APA, Harvard, Vancouver, ISO, etc.
9

Egawa, Yoshimi, Ralph J. Faudree, Ervin Györi, Yoshiyasu Ishigami, Richard H. Schelp y Hong Wang. "Vertex-Disjoint Cycles Containing Specified Edges". Graphs and Combinatorics 16, n.º 1 (1 de marzo de 2000): 81–92. http://dx.doi.org/10.1007/s003730050005.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
10

Li, Ruijuan, Juanjuan Liang, Xinhong Zhang y Yubao Guo. "Vertex-disjoint cycles in local tournaments". Discrete Mathematics 343, n.º 12 (diciembre de 2020): 112127. http://dx.doi.org/10.1016/j.disc.2020.112127.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
11

Lichiardopol, Nicolas. "Vertex-disjoint cycles in regular tournaments". Discrete Mathematics 312, n.º 12-13 (julio de 2012): 1927–30. http://dx.doi.org/10.1016/j.disc.2012.03.009.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
12

Bai, Yandong, Binlong Li y Hao Li. "Vertex-disjoint cycles in bipartite tournaments". Discrete Mathematics 338, n.º 8 (agosto de 2015): 1307–9. http://dx.doi.org/10.1016/j.disc.2015.02.012.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
13

Egawa, Yoshimi, Hikoe Enomoto, Stanislav Jendrol, Katsuhiro Ota y Ingo Schiermeyer. "Independence number and vertex-disjoint cycles". Discrete Mathematics 307, n.º 11-12 (mayo de 2007): 1493–98. http://dx.doi.org/10.1016/j.disc.2005.11.086.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
14

Harant, Jochen, Dieter Rautenbach, Peter Recht, Ingo Schiermeyer y Eva-Maria Sprengel. "Packing disjoint cycles over vertex cuts". Discrete Mathematics 310, n.º 13-14 (julio de 2010): 1974–78. http://dx.doi.org/10.1016/j.disc.2010.03.009.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
15

González-Moreno, Diego, Camino Balbuena y Mika Olsen. "Vertex-disjoint cycles in bipartite tournaments". Electronic Notes in Discrete Mathematics 54 (octubre de 2016): 69–72. http://dx.doi.org/10.1016/j.endm.2016.09.013.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
16

Ishigami, Yoshiyasu y Tao Jiang. "Vertex-disjoint cycles containing prescribed vertices". Journal of Graph Theory 42, n.º 4 (20 de marzo de 2003): 276–96. http://dx.doi.org/10.1002/jgt.10090.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
17

Gu, Ran, Xue-liang Li y Yong-tang Shi. "Hypergraph Turán Numbers of Vertex Disjoint Cycles". Acta Mathematicae Applicatae Sinica, English Series 38, n.º 1 (enero de 2022): 229–34. http://dx.doi.org/10.1007/s10255-022-1056-x.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
18

Verstraëte, Jacques. "Vertex-disjoint cycles of the same length". Journal of Combinatorial Theory, Series B 88, n.º 1 (mayo de 2003): 45–52. http://dx.doi.org/10.1016/s0095-8956(02)00012-6.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
19

Qiao, Shengning y Shenggui Zhang. "Vertex-disjoint chorded cycles in a graph". Operations Research Letters 38, n.º 6 (noviembre de 2010): 564–66. http://dx.doi.org/10.1016/j.orl.2010.09.007.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
20

Kang, Minjeong, O.-joung Kwon y Myounghwan Lee. "Graphs without two vertex-disjoint S-cycles". Discrete Mathematics 343, n.º 10 (octubre de 2020): 111997. http://dx.doi.org/10.1016/j.disc.2020.111997.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
21

Balbuena, C., D. González-Moreno y M. Olsen. "Vertex disjoint 4-cycles in bipartite tournaments". Discrete Mathematics 341, n.º 4 (abril de 2018): 1103–8. http://dx.doi.org/10.1016/j.disc.2017.10.023.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
22

Wang, Hong. "Two vertex-disjoint cycles in a graph". Graphs and Combinatorics 11, n.º 4 (diciembre de 1995): 389–96. http://dx.doi.org/10.1007/bf01787818.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
23

Bermond, Jean-Claude y Min-Li Yu. "Vertex disjoint routings of cycles over tori". Networks 49, n.º 3 (2007): 217–25. http://dx.doi.org/10.1002/net.20155.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
24

Egawa, Yoshimi. "Vertex-Disjoint Cycles of the Same Length". Journal of Combinatorial Theory, Series B 66, n.º 2 (marzo de 1996): 168–200. http://dx.doi.org/10.1006/jctb.1996.0015.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
25

KOHAYAKAWA, YOSHIHARU, GUILHERME OLIVEIRA MOTA y MATHIAS SCHACHT. "Monochromatic trees in random graphs". Mathematical Proceedings of the Cambridge Philosophical Society 166, n.º 1 (16 de enero de 2018): 191–208. http://dx.doi.org/10.1017/s0305004117000846.

Texto completo
Resumen
AbstractBal and DeBiasio [Partitioning random graphs into monochromatic components, Electron. J. Combin.24(2017), Paper 1.18] put forward a conjecture concerning the threshold for the following Ramsey-type property for graphsG: everyk-colouring of the edge set ofGyieldskpairwise vertex disjoint monochromatic trees that partition the whole vertex set ofG. We determine the threshold for this property for two colours.
Los estilos APA, Harvard, Vancouver, ISO, etc.
26

Li, Luyi y Xueliang Li. "Vertex-disjoint rainbow cycles in edge-colored graphs". Discrete Mathematics 345, n.º 7 (julio de 2022): 112878. http://dx.doi.org/10.1016/j.disc.2022.112878.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
27

Zhang, Yuke, Huiqiu Lin, Qinghai Liu y Jinfeng Zheng. "Distance spectrum, 1-factor and vertex-disjoint cycles". Linear Algebra and its Applications 654 (diciembre de 2022): 10–27. http://dx.doi.org/10.1016/j.laa.2022.08.034.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
28

Henning, Michael A. y Anders Yeo. "Vertex Disjoint Cycles of Different Length in Digraphs". SIAM Journal on Discrete Mathematics 26, n.º 2 (enero de 2012): 687–94. http://dx.doi.org/10.1137/100802463.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
29

Wang, Hong. "Large Vertex-Disjoint Cycles in a Bipartite Graph". Graphs and Combinatorics 16, n.º 3 (4 de septiembre de 2000): 359–66. http://dx.doi.org/10.1007/s003730070017.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
30

Gould, Ronald J., Kazuhide Hirohata y Ariel Keller. "On vertex-disjoint cycles and degree sum conditions". Discrete Mathematics 341, n.º 1 (enero de 2018): 203–12. http://dx.doi.org/10.1016/j.disc.2017.08.030.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
31

Gao, Yunshu, Xiaoyao Lin y Hong Wang. "Vertex-disjoint double chorded cycles in bipartite graphs". Discrete Mathematics 342, n.º 9 (septiembre de 2019): 2482–92. http://dx.doi.org/10.1016/j.disc.2019.05.028.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
32

Gao, Jun y Jie Ma. "A Conjecture of Verstraëte on Vertex-Disjoint Cycles". SIAM Journal on Discrete Mathematics 34, n.º 2 (enero de 2020): 1290–301. http://dx.doi.org/10.1137/19m1267738.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
33

He, Zhihong, Xiaoying Wang y Caiming Zhang. "Complementary Cycles in Irregular Multipartite Tournaments". Mathematical Problems in Engineering 2016 (2016): 1–7. http://dx.doi.org/10.1155/2016/5384190.

Texto completo
Resumen
A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph. A digraphDis cycle complementary if there exist two vertex disjoint cyclesCandC′such thatV(D)=V(C)∪V(C′). LetDbe a locally almost regularc-partite tournament withc≥3and|γ(D)|≤3such that all partite sets have the same cardinalityr, and letC3be a3-cycle ofD. In this paper, we prove that ifD-V(C3)has no cycle factor, thenDcontains a pair of disjoint cycles of length3and|V(D)|-3, unlessDis isomorphic toT7,D4,2,D4,2⁎, orD3,2.
Los estilos APA, Harvard, Vancouver, ISO, etc.
34

Sikhwal, Omprakash y Ashish Rastogi. "Domination, Independence and Fibonacci Numbers in Graphs Containing Disjoint Cycles". International Journal of Computational and Applied Mathematics & Computer Science 2 (2 de septiembre de 2022): 65–68. http://dx.doi.org/10.37394/232028.2022.2.12.

Texto completo
Resumen
Graph theory is a delightful playground for the exploration of proof techniques in discrete mathematics and its results have applications in many areas of the computing, social, and natural sciences. The fastest growing area within graph theory is the study of domination and Independence numbers. Domination number is the cardinality of a minimum dominating set of a graph. Independence number is the maximal cardinality of an independent set of vertices of a graph. The concept of Fibonacci numbers of graphs was first introduced by Prodinger and Tichy in 1982. The Fibonacci numbers of a graph is the number of independent vertex subsets. In this paper, introduce the identities of domination, independence and Fibonacci numbers of graphs containing vertex-disjoint cycles and edge-disjoint cycles.
Los estilos APA, Harvard, Vancouver, ISO, etc.
35

Hung, Le Xuan, Do Duy Hieu y Ngo Dac Tan. "Vertex-disjoint cycles of different lengths in multipartite tournaments". Discrete Mathematics 345, n.º 6 (junio de 2022): 112819. http://dx.doi.org/10.1016/j.disc.2022.112819.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
36

Molla, Theodore, Michael Santana y Elyse Yeager. "A Refinement of Theorems on Vertex-Disjoint Chorded Cycles". Graphs and Combinatorics 33, n.º 1 (3 de diciembre de 2016): 181–201. http://dx.doi.org/10.1007/s00373-016-1749-0.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
37

Elliott, Bradley, Ronald J. Gould y Kazuhide Hirohata. "On Degree Sum Conditions and Vertex-Disjoint Chorded Cycles". Graphs and Combinatorics 36, n.º 6 (21 de septiembre de 2020): 1927–45. http://dx.doi.org/10.1007/s00373-020-02227-z.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
38

Bai, Yandong y Yannis Manoussakis. "On the Number of Vertex-Disjoint Cycles in Digraphs". SIAM Journal on Discrete Mathematics 33, n.º 4 (enero de 2019): 2444–51. http://dx.doi.org/10.1137/18m1186356.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
39

Bang-Jensen, Jørgen, Matthias Kriesell, Alessandro Maddaloni y Sven Simonsen. "Vertex-disjoint directed and undirected cycles in general digraphs". Journal of Combinatorial Theory, Series B 106 (mayo de 2014): 1–14. http://dx.doi.org/10.1016/j.jctb.2013.10.005.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
40

Chen, Rong y Irene Pivotto. "Biased graphs with no two vertex-disjoint unbalanced cycles". Journal of Combinatorial Theory, Series B 130 (mayo de 2018): 207–45. http://dx.doi.org/10.1016/j.jctb.2018.01.001.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
41

Bang-Jensen, Jørgen y Stéphane Bessy. "Cycle Transversals in Tournaments with Few Vertex Disjoint Cycles". Journal of Graph Theory 79, n.º 4 (10 de septiembre de 2014): 249–66. http://dx.doi.org/10.1002/jgt.21830.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
42

Dziechci?ska-Halamoda, Z., J. Michael y W. Szwiec. "Games without repetitions on graphs with vertex disjoint cycles". Archiv der Mathematik 69, n.º 3 (1 de septiembre de 1997): 254–58. http://dx.doi.org/10.1007/s000130050118.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
43

Hou, Jianfeng, Caihong Yang y Qinghou Zeng. "Counting triangles in graphs without vertex disjoint odd cycles". Discrete Mathematics 347, n.º 7 (julio de 2024): 114015. http://dx.doi.org/10.1016/j.disc.2024.114015.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
44

Barile, Margherita y Antonio Macchia. "The arithmetical rank of the edge ideals of graphs with pairwise disjoint cycles". Journal of Algebra and Its Applications 15, n.º 07 (22 de julio de 2016): 1650120. http://dx.doi.org/10.1142/s0219498816501206.

Texto completo
Resumen
We prove that, for the edge ideal of a graph whose cycles are pairwise vertex-disjoint, the arithmetical rank is bounded above by the sum of the number of cycles and the maximum height of its associated primes.
Los estilos APA, Harvard, Vancouver, ISO, etc.
45

FERBER, ASAF, KYLE LUH, DANIEL MONTEALEGRE y OANH NGUYEN. "Packing Loose Hamilton Cycles". Combinatorics, Probability and Computing 26, n.º 6 (1 de agosto de 2017): 839–49. http://dx.doi.org/10.1017/s0963548317000402.

Texto completo
Resumen
A subsetCof edges in ak-uniform hypergraphHis aloose Hamilton cycleifCcovers all the vertices ofHand there exists a cyclic ordering of these vertices such that the edges inCare segments of that order and such that every two consecutive edges share exactly one vertex. The binomial randomk-uniform hypergraphHkn,phas vertex set [n] and an edge setEobtained by adding eachk-tuplee∈ ($\binom{[n]}{k}$) toEwith probabilityp, independently at random.Here we consider the problem of finding edge-disjoint loose Hamilton cycles covering all buto(|E|) edges, referred to as thepacking problem. While it is known that the threshold probability of the appearance of a loose Hamilton cycle inHkn,pis$p=\Theta\biggl(\frac{\log n}{n^{k-1}}\biggr),$the best known bounds for the packing problem are aroundp= polylog(n)/n. Here we make substantial progress and prove the following asymptotically (up to a polylog(n) factor) best possible result: forp≥ logCn/nk−1, a randomk-uniform hypergraphHkn,pwith high probability contains$N:=(1-o(1))\frac{\binom{n}{k}p}{n/(k-1)}$edge-disjoint loose Hamilton cycles.Our proof utilizes and modifies the idea of ‘online sprinkling’ recently introduced by Vu and the first author.
Los estilos APA, Harvard, Vancouver, ISO, etc.
46

CHEN, XIAOXUAN, JING YANG, XIANYA GENG y LONG WANG. "SINGULARITY OF ORIENTED GRAPHS FROM SEVERAL CLASSES". Bulletin of the Australian Mathematical Society 102, n.º 1 (21 de noviembre de 2019): 7–14. http://dx.doi.org/10.1017/s0004972719001151.

Texto completo
Resumen
A digraph is called oriented if there is at most one arc between two distinct vertices. An oriented graph $D$ is nonsingular if its adjacency matrix $A(D)$ is nonsingular. We characterise all nonsingular oriented graphs from three classes: graphs in which cycles are vertex disjoint, graphs in which all cycles share exactly one common vertex and graphs formed by cycles sharing a common path. As a straightforward corollary, the singularity of oriented bicyclic graphs is determined.
Los estilos APA, Harvard, Vancouver, ISO, etc.
47

Fernández, Irene, Jaehoon Kim, Younjin Kim y Hong Liu. "Nested cycles with no geometric crossings". Proceedings of the American Mathematical Society, Series B 9, n.º 3 (7 de febrero de 2022): 22–32. http://dx.doi.org/10.1090/bproc/107.

Texto completo
Resumen
In 1975, Erdős asked the following question: what is the smallest function f ( n ) f(n) for which all graphs with n n vertices and f ( n ) f(n) edges contain two edge-disjoint cycles C 1 C_1 and C 2 C_2 , such that the vertex set of C 2 C_2 is a subset of the vertex set of C 1 C_1 and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound f ( n ) = O ( n ) f(n)=O(n) using sublinear expanders.
Los estilos APA, Harvard, Vancouver, ISO, etc.
48

KURAUSKAS, VALENTAS y COLIN McDIARMID. "Random Graphs with Few Disjoint Cycles". Combinatorics, Probability and Computing 20, n.º 5 (9 de junio de 2011): 763–75. http://dx.doi.org/10.1017/s0963548311000186.

Texto completo
Resumen
The classical Erdős–Pósa theorem states that for each positive integer k there is an f(k) such that, in each graph G which does not have k + 1 disjoint cycles, there is a blocker of size at most f(k); that is, a set B of at most f(k) vertices such that G−B has no cycles. We show that, amongst all such graphs on vertex set {1,. . .,n}, all but an exponentially small proportion have a blocker of size k. We also give further properties of a random graph sampled uniformly from this class, concerning uniqueness of the blocker, connectivity, chromatic number and clique number.A key step in the proof of the main theorem is to show that there must be a blocker as in the Erdős–Pósa theorem with the extra ‘redundancy’ property that B–v is still a blocker for all but at most k vertices v ∈ B.
Los estilos APA, Harvard, Vancouver, ISO, etc.
49

Qiao, Shengning y Shenggui Zhang. "Spanning Cyclic Subdivisions of Vertex-Disjoint Cycles and Chorded Cycles in Graphs". Graphs and Combinatorics 28, n.º 2 (27 de marzo de 2011): 277–85. http://dx.doi.org/10.1007/s00373-011-1042-1.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
50

KIERSTEAD, H. A., A. V. KOSTOCHKA y A. McCONVEY. "A Sharp Dirac–Erdős Type Bound for Large Graphs". Combinatorics, Probability and Computing 27, n.º 3 (9 de marzo de 2018): 387–97. http://dx.doi.org/10.1017/s0963548318000020.

Texto completo
Resumen
Let k ⩾ 3 be an integer, hk(G) be the number of vertices of degree at least 2k in a graph G, and ℓk(G) be the number of vertices of degree at most 2k − 2 in G. Dirac and Erdős proved in 1963 that if hk(G) − ℓk(G) ⩾ k2 + 2k − 4, then G contains k vertex-disjoint cycles. For each k ⩾ 2, they also showed an infinite sequence of graphs Gk(n) with hk(Gk(n)) − ℓk(Gk(n)) = 2k − 1 such that Gk(n) does not have k disjoint cycles. Recently, the authors proved that, for k ⩾ 2, a bound of 3k is sufficient to guarantee the existence of k disjoint cycles, and presented for every k a graph G0(k) with hk(G0(k)) − ℓk(G0(k)) = 3k − 1 and no k disjoint cycles. The goal of this paper is to refine and sharpen this result. We show that the Dirac–Erdős construction is optimal in the sense that for every k ⩾ 2, there are only finitely many graphs G with hk(G) − ℓk(G) ⩾ 2k but no k disjoint cycles. In particular, every graph G with |V(G)| ⩾ 19k and hk(G) − ℓk(G) ⩾ 2k contains k disjoint cycles.
Los estilos APA, Harvard, Vancouver, ISO, etc.
Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!

Pasar a la bibliografía