Увійти

Готові списки джерел за темами / Partitioning into vertex-disjoint cycles / Статті в журналах

Статті в журналах з теми "Partitioning into vertex-disjoint cycles"

Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Partitioning into vertex-disjoint cycles.

Автор: Grafiati

Опубліковано: 4 травня 2024

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся з топ-50 статей у журналах для дослідження на тему "Partitioning into vertex-disjoint cycles".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.

1

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

2

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

3

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

4

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

5

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

6

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

7

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

8

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

9

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

10

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

11

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

12

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

13

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

14

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

15

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

16

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

17

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

18

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

19

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

20

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

21

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

22

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

23

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

24

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

25

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

26

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

27

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

28

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

29

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

30

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

31

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

32

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

33

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

34

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

35

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

36

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

37

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

38

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

39

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

40

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

41

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

42

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

43

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

44

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

45

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

46

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

47

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

48

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

49

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

50

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

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!