EXTREMAL THEOREMS FOR DEGREE SEQUENCE PACKING AND THE TWO-COLOR DISCRETE TOMOGRAPHY PROBLEM

作者：Diemunsch Jennifer^*; Ferrara Michael; Jahanbekam Sogol; Shook James M

来源：SIAM Journal on Discrete Mathematics, 2015, 29(4): 2088-2099.

DOI：10.1137/140987912

• degree sequence
• discrete tomography
• packing

A sequence pi = (d(1),..., d(n)) is graphic if there is a simple graph G with vertex set {v(1),..., v(n)} such that the degree of v(i) is d(i). We say that graphic sequences pi(1) = (d(1)((1)),..., d(n)((1))) and pi(2) = (d(1)((2)),..., d(n)((2))) pack if there exist edge-disjoint n-vertex graphs G(1) and G(2) such that for j is an element of {1, 2}, d(Gj) (v(i)) = d(i)((j))i for all i is an element of {1,..., n}. Here, we prove several extremal degree sequence packing theorems that parallel central results and open problems from the graph packing literature. Specifically, the main result of this paper implies degree sequence packing analogues to the Bollobas Eldridge- Catlin graph packing conjecture and the classical graph packing theorem of Sauer and Spencer. In discrete tomography, a branch of discrete imaging science, the goal is to reconstruct discrete objects using data acquired from low-dimensional projections. Specifically, in the k-color discrete tomography problem the goal is to color the entries of an m x n matrix using k colors so that each row and column receives a prescribed number of entries of each color. This problem is equivalent to packing the degree sequences of k bipartite graphs with parts of sizes m and n. Here we also prove several Sauer-Spencer-type theorems with applications to the two-color discrete tomography problem.

• 出版日期2015