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!

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ What does G2(n) mean? $\endgroup$
    – Gerry Myerson
    Commented Oct 16, 2014 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
    Commented Oct 16, 2014 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
    Commented Oct 17, 2014 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
    Commented Oct 17, 2014 at 12:44

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .