Log in

Relevant bibliographies by topics / Partitioning into vertex-disjoint cycles / Journal articles

Journal articles on the topic 'Partitioning into vertex-disjoint cycles'

To see the other types of publications on this topic, follow the link: Partitioning into vertex-disjoint cycles.

Author: Grafiati

Published: 4 May 2024

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

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Partitioning into vertex-disjoint cycles.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Ł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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!