Extensions of Signed Graphs

Signed graphs;Extensions;Odd-K_5;Combinatorics and Optimization

Naismith, Katherine

University of Waterloo

关键词: Signed graphs;    Extensions;    Odd-K_5;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/8387/1/Naismith_Katherine.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Given a signed graph (G, Σ) with an embedding on a surface S, we are interested in ;;extending;; (G, Σ) by adding edges and splitting vertices, such that the resulting graph has no embedding on S. We show (assuming 3-connectivity for (G, Σ)) that there are a small number of minimal extensions of (G, Σ) with no such embedding, and describe them explicitly. We also give conditions, for several surfaces S, for an embedding of a signed graph on S to extend uniquely. These results find application in characterizing the signed graphs with no odd-K_5 minor.