Disjoint cycles covering specified vertices in bipartite graphs with partial degrees

DOI10.1016/J.AMC.2022.127626MaRDI QIDQ6041509zbMATH OpenOpenAlexFDO

Authors Su-yun Jiang, Jin Yan

Publication date 31 May 2023

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.10791

zbMATH Keywords

bipartite graphscoveringdisjoint cyclespartial degree

Mathematics Subject Classification ID

Graph theory (05Cxx)

Abstract: Let $k$ be a positive integer. Let $G$ be a balanced bipartite graph of order $2n$ with bipartition $(X,Y)$, and $S$ a subset of $X$. Suppose that every pair of nonadjacent vertices $(x,y)$ with $xinS,yinY$ satisfies $d(x)+d(y)geqn+1$. We show that if $|S|geq2k+2$, then $G$ contains $k$ disjoint cycles covering $S$ such that each of the $k$ cycles contains at least two vertices of $S$. Here, both the degree condition and the lower bound of $|S|$ are best possible. And we also show that if $|S|=2k+1$, then $G$ contains $k$ disjoint cycles such that each of the $k$ cycles contains at least two vertices of $S$.

Recommendations

• Partial degree conditions and cycle coverings in bipartite graphs
• Partial degrees on matchings for cycles in bipartite graphs
• Vertex-disjoint cycles containing specified vertices in a bipartite graph
• Maximal total length of k disjoint cycles in bitpartite graphs
• Vertex disjoint cycles containing specified paths of order 3 in a bipartite graph

Cites work

• 2-factors of bipartite graphs with asymmetric minimum degrees
• 2‐neighborhoods and hamiltonian conditions
• A degree condition of 2-factors in bipartite graphs
• A look at cycles containing specified elements of a graph
• A method in graph theory
• A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
• Cyclability and pancyclability in bipartite graphs
• Cycles through specified vertices
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• Graph theory
• On 2-factors of a bipartite graph
• On Hamiltonian bipartite graphs
• On the maximum number of independent cycles in a bipartite graph
• Partial Degree Conditions and Cycle Coverings
• Partial degree conditions and cycle coverings in bipartite graphs
• Some Theorems on Abstract Graphs

Cited in

(8)

• Covering vertices of a graph by \(k\) disjoint cycles
• Large vertex-disjoint cycles in a bipartite graph
• scientific article; zbMATH DE number 5080500 (Why is no real title available?)
• The double Hall property and cycle covers in bipartite graphs
• Partial degrees on matchings for cycles in bipartite graphs
• Packing directed cycles of specified odd length into digraphs and alternating cycles into bipartite graphs
• On partitioning a bipartite graph into cycles and degenerated cycles
• On partitioning a bipartite graph into a specified number of cycles and degree sum conditions for two vertices of distance three

This page was built for publication: Disjoint cycles covering specified vertices in bipartite graphs with partial degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041509)