Premium
Disjoint cycles covering matchings in graphs with partial degrees
Author(s) -
Wang Hong
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22495
Subject(s) - combinatorics , mathematics , disjoint sets , conjecture , matching (statistics) , integer (computer science) , graph , order (exchange) , discrete mathematics , set (abstract data type) , computer science , statistics , finance , economics , programming language
Let G be a graph of order n . Let k be a positive integer and M a matching of G with ∣ M ∣ ≥ 2 k such that d ( x ) ≥ 3 n ∕ 4 for each x ∈ V ( M ) , where V ( M ) is the set of vertices that are endvertices of edges of M . We prove that for any k integersn i ≥ 2 ( 1 ≤ i ≤ k )with n 1 + n 2 + ⋯ + n k ≤ ∣ M ∣ , G contains k disjoint cycles C 1 , C 2 , … ,C k such that C i contains n i edges of M for all i ∈ { 1 , … , k } . We conjecture that the same conclusion holds if the degree condition is changed to that d ( x ) ≥ 2 n ∕ 3 for all x ∈ V ( M ) .