Skip to main content
Mark's user avatar
Mark's user avatar
Mark's user avatar
Mark
Unregistered
  • Member for 10 years, 2 months
  • Last seen more than 10 years ago
comment
Is a rigid cycle a chordal graph?
@Andrew, thanks a lot! Actually, my previous intuition is the same as yours. But what I am most interested in the elimination order (not necessarily perfect) of certain graph (so-called pseudocycle) formed by the union of two spanning trees. The elimination order I mean is the order of vertices according to which I delete each vertex and add edges between the remaining vertices incident to the deleted vertex (if there is no edge between those incident vertices). The elimination order I want to find in the pseudocycle is the order that allowes me to add at most $O(n)$ extra edges totally.
comment
Is a rigid cycle a chordal graph?
These definitions comes from the book Combinatorial Rigidity by Jack Graver, Brigitte Servatius and Herman Servatius. In their book, $\mathcal{G}_2(n)$ is the unique maximal 2-dimensional abstract rigidity matroid on n vertices. It would be OK if just thinking the graph C satisfies the condition. And I just want to know whether such a C is chordal or not. Thanks!
awarded
revised
Is a rigid cycle a chordal graph?
added 66 characters in body
Loading…
awarded
asked
Loading…