Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
osu1354645035.pdf (650.49 KB)
ETD Abstract Container
Abstract Header
Some Topics concerning Graphs, Signed Graphs and Matroids
Author Info
Sivaraman, Vaidyanathan
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=osu1354645035
Abstract Details
Year and Degree
2012, Doctor of Philosophy, Ohio State University, Mathematics.
Abstract
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.
Committee
Neil Robertson (Advisor)
Akos Seress (Committee Member)
Matthew Kahle (Committee Member)
Pages
120 p.
Subject Headings
Mathematics
Keywords
Graphs
;
Signed Graphs
;
Matroids
;
Heawood Graph
;
Projective-planar Graphs
;
Frustration
;
Zaslavsky's Conjecture
;
S. B. Rao's Conjecture
;
Welsh's Conjecture
;
WQO
;
Strongly Regular Graphs
;
Shrikhande's Theorem
;
Frame Matroid
;
Bicircular Matroid.
Recommended Citations
Refworks
EndNote
RIS
Mendeley
Citations
Sivaraman, V. (2012).
Some Topics concerning Graphs, Signed Graphs and Matroids
[Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1354645035
APA Style (7th edition)
Sivaraman, Vaidyanathan.
Some Topics concerning Graphs, Signed Graphs and Matroids.
2012. Ohio State University, Doctoral dissertation.
OhioLINK Electronic Theses and Dissertations Center
, http://rave.ohiolink.edu/etdc/view?acc_num=osu1354645035.
MLA Style (8th edition)
Sivaraman, Vaidyanathan. "Some Topics concerning Graphs, Signed Graphs and Matroids." Doctoral dissertation, Ohio State University, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=osu1354645035
Chicago Manual of Style (17th edition)
Abstract Footer
Document number:
osu1354645035
Download Count:
1,490
Copyright Info
© 2012, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.