Search ETDs:
Some Topics concerning Graphs, Signed Graphs and Matroids
Sivaraman, Vaidyanathan

2012, Doctor of Philosophy, Ohio State University, Mathematics.
We discuss well-quasi-ordering in graphs and signed graphs, giving two short proofs of the bounded case of S. B. Rao's conjecture. We give a characterization of graphs whose bicircular matroids are signed-graphic, thus generalizing a theorem of Matthews from the 1970s. We prove a recent conjecture of Zaslavsky on the equality of frustration number and frustration index in a certain class of signed graphs. We prove that there are exactly seven signed Heawood graphs, up to switching isomorphism. We present a computational approach to an interesting conjecture of D. J. A. Welsh on the number of bases of matroids. We then move on to study the frame matroids of signed graphs, giving explicit signed-graphic representations of certain families of matroids. We also discuss the cycle, bicircular and even-cycle matroid of a graph and characterize matroids arising as two different such structures. We study graphs in which any two vertices have the same number of common neighbors, giving a quick proof of Shrikhande's theorem. We provide a solution to a problem of E. W. Dijkstra. Also, we discuss the flexibility of graphs on the projective plane. We conclude by mentioning partial progress towards characterizing signed graphs whose frame matroids are transversal, and some miscellaneous results.
Neil Robertson (Advisor)
Akos Seress (Committee Member)
Matthew Kahle (Committee Member)
120 p.

Recommended Citations

Hide/Show APA Citation

Sivaraman, V. (2012). Some Topics concerning Graphs, Signed Graphs and Matroids. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Sivaraman, Vaidyanathan. "Some Topics concerning Graphs, Signed Graphs and Matroids." Electronic Thesis or Dissertation. Ohio State University, 2012. OhioLINK Electronic Theses and Dissertations Center. 25 Sep 2017.

Hide/Show Chicago Citation

Sivaraman, Vaidyanathan "Some Topics concerning Graphs, Signed Graphs and Matroids." Electronic Thesis or Dissertation. Ohio State University, 2012. https://etd.ohiolink.edu/

Files

osu1354645035.pdf (650.49 KB) View|Download