Two Hamiltonian cycles
If the line graph of a graph decomposes into Hamiltonian cycles, what is ? We answer this question for decomposition into two cycles.
Source author record
Vaidy Sivaraman
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
8works
2topics
3close collaborators
Published work
8 publications
preprint2019arXiv
Cop number of graphs without long holes
A hole in a graph is an induced cycle of length at least 4. We give a simple winning strategy for t-3 cops to capture a robber in the game of cops and robbers played in a graph that does not contain a hole of length at least t. This strengthens a theorem of Joret-Kaminski-Theis, who proved that t-2 cops have a winning strategy in such graphs. As a consequence of our bound, we also give an inequality relating the cop number and the Dilworth number of a graph.
Open access
preprint2017arXiv
Sum-perfect graphs
Inspired by a famous characterization of perfect graphs due to Lovász, we define a graph G to be sum-perfect if for every induced subgraph H of G, α(H)+ω(H)≥∣V(H)∣. (Here α and ω denote the stability number and clique number, respectively.) We give a set of 27 graphs and we prove that a graph G is sum-perfect if and only if G does not contain any of the graphs in the set as an induced subgraph.
Open access
preprint2014arXiv
A unified proof of Brooks' theorem and Catlin's theorem
We give a new proof of Brooks' theorem that immediately implies a strengthening of Brooks' theorem, known as Catlin's theorem.
Open access
preprint2014arXiv
Frustration in signed graphs
Zaslavsky conjectured the following: The minimum number of vertices to be deleted to restore balance in a subcubic signed graph is the same as the minimum number of edges to be deleted to restore balance. We prove this conjecture. Also, we obtain a bound for these invariants in a special class of signed graphs.
Open access
preprint2013arXiv
Bicircular signed-graphic matroids
Several matroids can be defined on the edge set of a graph. Although historically the cycle matroid has been the most studied, in recent times, the bicircular matroid has cropped up in several places. A theorem of Matthews from late 1970s gives a characterization of graphs whose bicircular matroids are graphic. We give a characterization of graphs whose bicircular matroids are signed-graphic.
Open access
preprint2013arXiv
Labelled version of the almost bounded case of S. B. Rao's degree sequence conjecture
S. B. Rao conjectured that graphic sequences are well-quasi-ordered under an inclusion based on induced subgraphs. This conjecture has now been proved by Chudnovsky and Seymour. We give an independent short proof of the labelled version of the almost bounded case of S. B. Rao's conjecture, the case where we have a bound on the degree, but allow a bounded number of vertices to have unbounded degree.
Open access
preprint2011arXiv
Two short proofs of the bounded case of S.B. Rao's degree sequence conjecture
S. B. Rao conjectured that graphic sequences are well-quasi-ordered under an inclusion based on induced subgraphs. This conjecture has now been settled completely by M. Chudnovsky and P. Seymour. One part of the proof proves the result for the bounded case, a result proved independently by C. J. Altomare. We give two short proofs of the bounded case of S. B. Rao's conjecture. Both the proofs use the fact that if the number of entries in an integer sequence (with even sum) is much larger than its highest term, then it is necessarily graphic.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.