2
$\begingroup$

There are two relevant questions:

(1) We know an edge set $C$ is a rigid cycle in $\mathcal{G}_2(n)$ if and only if $|E(C)|=2|V(C)|−2$ and $|F|≤2|V(F)|−3$ for every proper subset $F$ of $E(C)$. Thus, I want to know: Is a rigid cycle a chordal graph? (It can be found in Wiki that chordal graphs are also called as "rigid circuit graphs". But i can't find the connection between it and rigid cycle. Are they the same thing?)

(2) A graph $G=(V,E)$ is defined as pseudocycle iff $|E|=2|V|−2$ and $F\leq 2|V(F)|−2$, $ \forall \ \emptyset\subset F\subset E$. Thus, I also would like to know: Is a pseudocycle a chordal graph?

Thanks very much!

$\endgroup$
  • 5
    $\begingroup$ What does G2(n) mean? $\endgroup$ – Gerry Myerson Oct 16 '14 at 22:06
  • 1
    $\begingroup$ No to the second question, as exhibited by a graph on five vertices and eight edges with minimum degree 3. $\endgroup$ – Andrew D. King Oct 16 '14 at 23:32
  • $\begingroup$ 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! $\endgroup$ – Mark Oct 17 '14 at 12:17
  • $\begingroup$ @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. $\endgroup$ – Mark Oct 17 '14 at 12:44
2
$\begingroup$

I know this question is old but in case it's still useful here's an answer to 1 (the second question was answered in a comment):

Wikipedia uses "rigid circuit graphs" as an alternative name for chordal graphs referencing a paper of Dirac.

The graphs that you call rigid cycles are more commonly known in rigidity theory as circuits (they are the graphs induced by circuits in the 2-dimensional generic rigidity matroid).

It is easy to show that circuits have minimum degree 3, but as Dirac states, trees are chordal graphs so there's one class of examples showing the two notions are not the same.

A good paper on circuits is Berg and Jordan, A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid in JCT:B. A number of the figures in that paper illustrate that circuits need not have chords on every cycle.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.