Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

New Results on Packing Degree Sequences and the 2-Color Discrete Tomography Problem

Published

Author(s)

James Shook, Michael Ferrara, Jennifer Diemunsch, Sogol Jahanbekam

Abstract

A sequence $\pi=(d_1,\ldots,d_n)$ is graphic if there is a simple graph $G$ with vertex set $\{v_1,\ldots,v_n\}$ such that the degree of $v_i$ is the $i$th entry of $\pi$. We say that graphic sequences $\pi_1=(d_1^{(1)},\ldots,d_n^{(1)})$ and $\pi_2=(d_1^{(2)},\ldots,d_n^{(2)})$, \emph{pack} if there exist edge-disjoint $n$-vertex graphs $G_1$ and $G_2$ such that for $j=1,2$, $d_{G_j}(v_i)=d_i^{(j)}$ for all $i=1,\ldots,n$. Here we give conditions on $\pi_1$ and $\pi_2$ to guarantee that these sequences pack. In particular, let $\Δ_j$ be the maximum degree of $\pi_j$, then if $\Δ_1\Δ_2<\frac{n}{2}$ then $\pi_1$ and $\pi_2$ pack. This result is a degree sequence analogue to a well-known result of Sauer and Spencer. Packing bigraphic sequences $\pi_1$ and $\pi_2$ applies to discrete tomography. In discrete tomography, the goal is to reconstruct discrete objects from low-dimensional projections. Specifically, we consider an $m\times n$ matrix, with the goal of coloring the entries with $k$ colors so that each row and column receive a prescribed numbers of entries of each colors. This problem is the same as packing degree sequences of $k$ bipartite graphs with parts of sizes $m$ and $n$. Here we show that two bigraphic sequences pack if $\Δ_1\Δ_2<\frac{n+m}{4}$.
Citation
Siam Journal on Discrete Mathematics
Volume
29
Issue
4

Keywords

Degree sequence, Packing, Discrete Tomography

Citation

Shook, J. , Ferrara, M. , Diemunsch, J. and Jahanbekam, S. (2015), New Results on Packing Degree Sequences and the 2-Color Discrete Tomography Problem, Siam Journal on Discrete Mathematics, [online], https://doi.org/10.1137/140987912 (Accessed April 14, 2024)
Created October 27, 2015, Updated May 15, 2020