On the Existence of Simultaneous Edge Disjoint Realizations of Degree Sequences with 'Few' Edges

Abstract

This paper contains the following results. For a sequence A, let (M sub A) be the number of non-zero entries in it; suppose A, B and C = (A+B) are sequences that are the degrees of simple graphs; then if summation of (c sub i) or < or = 2(M sub A) + (M sub B) - 2, there exists a realization of C having disjoint factors with degree sequences A and B. At least one of these can be a forest. If A and B are forest realizable, the conditions under which A, B and C can be simultaneously realized with A- and B-factors that are forests are characterized.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1975
Accession Number
ADA016608

Entities

People

  • D. J. Kleitman
  • M. Koren
  • S.-y. Li

Organizations

  • Cornell University

Tags

DTIC Thesaurus Topics

  • Construction
  • Contracts
  • Engineering
  • Graph Theory
  • Guarantees
  • Inequalities
  • Massachusetts
  • Mathematics
  • Military Research
  • New York
  • Operations Research
  • Sequences
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.