DISJOINT CYCLES WITH PRESCRIBED LENGTHS AND INDEPENDENT EDGES IN GRAPHS
3
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
We conjecture that if k ≥ 2 is an integer and G is a graph of order n with minimum degree at least (n + 2k)/2, then for any k independent edges e1 ,...,ek in G and for any integer partition n = n1 + ··· + nk with ni ≥ 4 (1 ≤ i ≤ k), G has k disjoint cycles C1 ,...,Ck of orders n1 ,...,n k , respectively, such that C i passes through e i for all 1 ≤ i ≤ k. We show that this conjecture is true for the case k = 2. The minimum degree condition is sharp in general.
Abstract
We conjecture that if k ≥ 2 is an integer and G is a graph of order n with minimum degree at least (n + 2k)/2, then for any k independent edges e1 ,...,ek in G and for any integer partition n = n1 + ··· + nk with ni ≥ 4 (1 ≤ i ≤ k), G has k disjoint cycles C1 ,...,Ck of orders n1 ,...,n k , respectively, such that C i passes through e i for all 1 ≤ i ≤ k. We show that this conjecture is true for the case k = 2. The minimum degree condition is sharp in general.
참고문헌 (9)
- S. Abbasi, "Spanning cycles in dense graphs", Ph.D, pp.1999
- B. Bollobas, "Extremal Graph Theory" (1978), Academic Press
- J. Bondy, "A method in graph theory", Discrete Math, 15(2), pp.111~135 (1976)
- Y. Egawa, "Vertex-disjoint cycles containing specified edges", Graphs Combin, 16(1), pp.81~92 (2000)
- M. H. El-Zahar, "On circuits in graphs", Discrete Math, 50(2-3), pp.227~230 (1984)
- P. Erdos, "On maximal paths and circuits of graphs", Acta Math. Acad. Sci. Hungar, 10, pp.337~356 (1959)
- C. Magnant, "Partitioning graphs into paths and cycles", J. Comb, 3(2), pp.135~161 (2012)
- H. Wang, "Covering a graph with cycles passing through given edges", J. Graph Theory, 26(2), pp.105~109 (1997)
- J. E.Williamson, "Panconnected graph II", Period. Math. Hungar, 8, pp.105~116 (1977)