Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I recently tried to prove the following characterization of chordal graphs, attributed to Fulkerson & Gross:

"A graph $G$ is chordal if and only if it has an ordering such that for all $v \in G$, all the neighbors of $v$ that precede it in the ordering form a clique."

I believe the wikipedia page calls this (or its reverse) a "perfect elimination ordering." In any case, my proof was harder than I expected and I ended up with the following strengthening:

"$G$ is chordal if and only if for any $v \in G$, we can find such an ordering of $G$ that starts with $v$."

I would like to know if this strengthening is:

1) known / obvious from the weaker theorem / obvious from folklore, or 2) wrong. =)

I can of course give a proof to anyone who is interested - it is just too long to fit here.

Best, -Yan

share|improve this question
    
hmm, so what do I do in this case? I've refrained from accepting my own answer in case that's bad form. –  yanzhang Apr 1 '10 at 6:19
2  
I would say: accept your own answer if you feel it is the best one. MO is in principle a resource for people over time, as well as in the present tense; a fixation on your "score" is worse than accepting your own answer. –  Niel de Beaudrap Apr 1 '10 at 7:16
    
sounds legitimate. I should give the average MO user credit for not being the average XBOX Live achievement-chaser, which ceases my need to avoid bad precedent. =) –  yanzhang Apr 1 '10 at 15:42
add comment

2 Answers

up vote 2 down vote accepted

It's known/obvious from the next few lines of the Wikipedia article stating that a LexBFS ordering (or its reverse, depending on your conventions) gives a perfect elimination ordering, since LexBFS can be made to start at any vertex.

share|improve this answer
    
Thanks. I was looking for something like this (i.e. I wasn't sure in their particular search they could have chosen \emph{any} $v$ from the list of "unchosen" vertices). I prefer things like this to my answer. –  yanzhang Apr 1 '10 at 15:40
add comment

Wow. Scary how I've failed to do this until I ask the question on MO, and then immediately get the idea.

Here's a proof, assuming the weaker version of the theorem is true:

Call such an ordering "good." Consider a minimal counterexample $M$ of size $n$ to our stronger claim: it must be chordal, has a good ordering, but does not have a good ordering starting at every vertex. However, every chordal graph of size less than $n$ has a good ordering starting at every vertex.

Since $M$ has some good ordering $T$, it has some vertex $v$ (the last one in $T$) such that all its neighbors form a clique. Remove this vertex to get $M'$. $M'$ is chordal (since chordality respects vertex deletion), so we can make a good ordering starting with any element in $M'$. Attach $v$ to the end. This ordering is obviously still good. Thus, we can make a good ordering starting with any vertex that is not $v$. So it suffices to make a good ordering starting with $v$.

To do this, consider the last vertex $w$ in $T \setminus v$ with the property that $w$ is not connected to the vertex $w'$ immediately following it in $T$. If $w$ doesn't exist, this just means $M$ is a clique, so any ordering is good and we have a good ordering starting with $v$. If $w$ exists, then notice that $w$ cannot be connected with any of the vertices after it in $T$; if it is, then pick the earliest such one $u \neq w'$, which is both connected to the vertex directly preceding it (not connected to $w$ by choice of $u$) and $w$, a contradiction on the ordering being good. Thus, $w$ is only connected with vertices preceding it. This means all of $w$'s neighbors form a clique. Hence, we can delete $w$, make a good ordering starting with $v$ of the rest, and append $w$ to the end. A winner is us.

-Yan

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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