Gotowe bibliografie tematyczne / Partitioning into vertex-disjoint cycles / Artykuły w czasopismach

Artykuły w czasopismach na temat „Partitioning into vertex-disjoint cycles”

Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: Partitioning into vertex-disjoint cycles.
Autor: Grafiati
Data publikacji: 4 maja 2024

Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych

Wybierz rodzaj źródła:

Sprawdź 50 najlepszych artykułów w czasopismach naukowych na temat „Partitioning into vertex-disjoint cycles”.

Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.

Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.

Przeglądaj artykuły w czasopismach z różnych dziedzin i twórz odpowiednie bibliografie.

1

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
2

Lin, Mugang, Jianxin Wang, Qilong Feng i Bin Fu. "Randomized Parameterized Algorithms for the Kidney Exchange Problem". Algorithms 12, nr 2 (25.02.2019): 50. http://dx.doi.org/10.3390/a12020050.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
3

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
4

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
5

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
6

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
7

Li, Jianping, i George Steiner. "Partitioning a graph into vertex-disjoint paths". Studia Scientiarum Mathematicarum Hungarica 42, nr 3 (1.09.2005): 277–94. http://dx.doi.org/10.1556/sscmath.42.2005.3.3.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
8

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
9

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
10

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
11

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
12

Bai, Yandong, Binlong Li i Hao Li. "Vertex-disjoint cycles in bipartite tournaments". Discrete Mathematics 338, nr 8 (sierpień 2015): 1307–9. http://dx.doi.org/10.1016/j.disc.2015.02.012.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
13

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
14

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
15

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
16

Ishigami, Yoshiyasu, i Tao Jiang. "Vertex-disjoint cycles containing prescribed vertices". Journal of Graph Theory 42, nr 4 (20.03.2003): 276–96. http://dx.doi.org/10.1002/jgt.10090.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
17

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
18

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
19

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
20

Kang, Minjeong, O.-joung Kwon i Myounghwan Lee. "Graphs without two vertex-disjoint S-cycles". Discrete Mathematics 343, nr 10 (październik 2020): 111997. http://dx.doi.org/10.1016/j.disc.2020.111997.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
21

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
22

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
23

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
24

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
25

KOHAYAKAWA, YOSHIHARU, GUILHERME OLIVEIRA MOTA i MATHIAS SCHACHT. "Monochromatic trees in random graphs". Mathematical Proceedings of the Cambridge Philosophical Society 166, nr 1 (16.01.2018): 191–208. http://dx.doi.org/10.1017/s0305004117000846.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
26

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
27

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
28

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
29

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
30

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
31

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
32

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
33

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
34

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
35

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
36

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
37

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
38

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
39

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
40

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
41

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
42

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
43

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
44

Barile, Margherita, i Antonio Macchia. "The arithmetical rank of the edge ideals of graphs with pairwise disjoint cycles". Journal of Algebra and Its Applications 15, nr 07 (22.07.2016): 1650120. http://dx.doi.org/10.1142/s0219498816501206.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
45

FERBER, ASAF, KYLE LUH, DANIEL MONTEALEGRE i OANH NGUYEN. "Packing Loose Hamilton Cycles". Combinatorics, Probability and Computing 26, nr 6 (1.08.2017): 839–49. http://dx.doi.org/10.1017/s0963548317000402.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
46

CHEN, XIAOXUAN, JING YANG, XIANYA GENG i LONG WANG. "SINGULARITY OF ORIENTED GRAPHS FROM SEVERAL CLASSES". Bulletin of the Australian Mathematical Society 102, nr 1 (21.11.2019): 7–14. http://dx.doi.org/10.1017/s0004972719001151.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
47

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
48

KURAUSKAS, VALENTAS, i COLIN McDIARMID. "Random Graphs with Few Disjoint Cycles". Combinatorics, Probability and Computing 20, nr 5 (9.06.2011): 763–75. http://dx.doi.org/10.1017/s0963548311000186.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
49

Qiao, Shengning, i Shenggui Zhang. "Spanning Cyclic Subdivisions of Vertex-Disjoint Cycles and Chorded Cycles in Graphs". Graphs and Combinatorics 28, nr 2 (27.03.2011): 277–85. http://dx.doi.org/10.1007/s00373-011-1042-1.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
50

KIERSTEAD, H. A., A. V. KOSTOCHKA i A. McCONVEY. "A Sharp Dirac–Erdős Type Bound for Large Graphs". Combinatorics, Probability and Computing 27, nr 3 (9.03.2018): 387–97. http://dx.doi.org/10.1017/s0963548318000020.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
Oferujemy zniżki na wszystkie plany premium dla autorów, których prace zostały uwzględnione w tematycznych zestawieniach literatury. Skontaktuj się z nami, aby uzyskać unikalny kod promocyjny!

Do bibliografii