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

Published

October 27, 2015

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

Pub Type

Journals

Download Paper

https://doi.org/10.1137/140987912

Local Download

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 25, 2024)