On packing bipartite graphs

descriptionPublicationkeyboard_double_arrow_right Article 01 Sep 1992 English Publisher:Springer Science and Business Media LLCJournal:Combinatorica, volume 12, pages 295-301 (issn: 0209-9683, eissn: 1439-6912,

Copyright policy )

Authors: Péter Hajnal; Mario Szegedy;

doi: 10.1007/bf01285818

On packing bipartite graphs

- Summary
- Subjects
- Metrics

Abstract

Two simple graphs \(G\) and \(H\) can be packed if \(G\) is isomorphic to a subgraph of the complement \(\overline H\) of \(H\). A sufficient condition is known for the existence of packing in terms of the product of the maximal degrees of \(G\) and \(H\). The paper improves this result for bipartite graphs by presenting a condition involving products of a maximum degree with an average degree, which guarantees a packing of the two bipartite graphs.

Related Organizations

AT&T
United States
University of Szeged
Hungary

Keywords

bipartite graphs, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), packing, Combinatorial aspects of packing and covering, degree

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	7
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average