Bibliographies thématiques / Partitioning into vertex-disjoint cycles / Articles de revues

Articles de revues sur le sujet « Partitioning into vertex-disjoint cycles »

Pour voir les autres types de publications sur ce sujet consultez le lien suivant : Partitioning into vertex-disjoint cycles.
Auteur : Grafiati
Publié le 4 mai 2024

Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres

Choisissez une source :

Consultez les 50 meilleurs articles de revues pour votre recherche sur le sujet « Partitioning into vertex-disjoint cycles ».

À côté de chaque source dans la liste de références il y a un bouton « Ajouter à la bibliographie ». Cliquez sur ce bouton, et nous générerons automatiquement la référence bibliographique pour la source choisie selon votre style de citation préféré : APA, MLA, Harvard, Vancouver, Chicago, etc.

Vous pouvez aussi télécharger le texte intégral de la publication scolaire au format pdf et consulter son résumé en ligne lorsque ces informations sont inclues dans les métadonnées.

Parcourez les articles de revues sur diverses disciplines et organisez correctement votre bibliographie.

1

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
2

Lin, Mugang, Jianxin Wang, Qilong Feng et Bin Fu. « Randomized Parameterized Algorithms for the Kidney Exchange Problem ». Algorithms 12, no 2 (25 février 2019) : 50. http://dx.doi.org/10.3390/a12020050.

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
3

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
4

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
5

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
6

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
7

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
8

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
9

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
10

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
11

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
12

Bai, Yandong, Binlong Li et Hao Li. « Vertex-disjoint cycles in bipartite tournaments ». Discrete Mathematics 338, no 8 (août 2015) : 1307–9. http://dx.doi.org/10.1016/j.disc.2015.02.012.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
13

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
14

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
15

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
16

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
17

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
18

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
19

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
20

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
21

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
22

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
23

Bermond, Jean-Claude, et 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.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
24

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
25

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
26

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
27

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
28

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
29

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
30

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
31

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
32

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
33

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
34

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
35

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
36

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
37

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
38

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
39

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
40

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
41

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
42

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
43

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
44

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
45

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
46

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
47

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
48

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
49

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

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
50

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

Texte intégral
Résumé :
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.
Styles APA, Harvard, Vancouver, ISO, etc.
Nous offrons des réductions sur tous les plans premium pour les auteurs dont les œuvres sont incluses dans des sélections littéraires thématiques. Contactez-nous pour obtenir un code promo unique!

Vers la bibliographie