On the maximum number of independent cycles in a bipartite graph
type: Item
instance of: scholarly article
title: On the maximum number of independent cycles in a bipartite graph
zbMATH Open document ID: 0859.05054
author: Hong Wang
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-04-07T00:00:00Z
review text: In [\textit{K. Corrádi} and \textit{A. Hajnal}, On the maximum number of independent circuits in a graph, Acta Math. Acad. Sci. Hung. 14, 423-439 (1963; Zbl 0118.19001)] it was shown that if \(G\) is a graph of order at least \(3k\) with minimum degree at least \(2k\), then \(G\) contains \(k\) independent cycles. A collection of cycles in a graph is called independent if they are vertex disjoint. Here the author considers the analogous bipartite problem. Theorem 1. Let \(G\) be a bipartite graph with partite sets \(V_1\) and \(V_2\). If \(|V_1|=|V_2|=n>2k\) and \(G\) has minimum degree at least \(k+1\), then \(G\) contains \(k\) independent cycles.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 934808
zbMATH Keywords: independent cycles
zbMATH Keywords: bipartite graph
reviewed by: Linda Lesniak
MaRDI profile type: Publication
full work available at URL: jctb.1996.0037
OpenAlex ID: W2041660565
DOI: 10.1006/JCTB.1996.0037
description: scientific article; zbMATH DE number 934808