Abstract

Heather Jordon (ISU, joint with Dean Hoffman), Signed Graph Factors and Degree Sequences


Abstract: For a signed graph G and function f: V(G) --> Z, the integers, a signed f-factor of G is a spanning subgraph F such that sdeg_F(v) = f(v) for every vertex v of G, where sdeg(v) is the number of positive edges incident with v less the number of negative edges incident with v, with loops counting twice in either case. For a given vertex-function f, we provide necessary and sufficient conditions for a signed graph G to have a signed f-factor. As a consequence of this result, an Erdos-Gallai type result is given for a sequence of integers to be the degree sequence of a signed r-graph, the graph with at most r positive and r negative edges between a given pair of distinct vertices. Finally, we discuss how the theory can be altered when mixed edges (i.e. edges with one positive and one negative end) are allowed.


Papa Amar Sissokho
Last modified: Monday, Jan 30, 2006