Talk:Crown graph
Mathematics B‑class Low‑priority | ||||||||||
|
Greedy worst case lower bound
I attributed the greedy worst case lower bound to Johnson, which is what Kubale (2004) does. That’s the oldest reference I’ve been able to find for this construction. If the Füredi et al. (2008) paper was only used for that reference, I think it can be removed. (But I’m slightly confused about that paper, so maybe I’m misunderstanding something.) Thore Husfeldt (talk) 09:41, 14 January 2009 (UTC)
Polyhedral resemblance
The crown graph with an octagonal boundary looks a bit like a square cupola... Professor M. Fiendish, Esq. 13:01, 9 September 2009 (UTC)
Tensor product
I think that the crown graph on 2n vertices can also be regarded as the tensor product of Cn and K2. Unless someone points out that I am mistaken, I shall add this to the first paragraph. Maproom (talk) 21:34, 16 February 2011 (UTC)
- I don't think so. Tensor product with K2 (also known as the bipartite double cover) preserves the degree of a vertex. Cn x K2 is always either C2n (if n is odd) or two disjoint copies of Cn (if n is even). Maybe you mean some other kind of product? —David Eppstein (talk) 21:59, 16 February 2011 (UTC)
- You are right. I mean Cartesian product, still of Cn and K2. Maproom (talk) 22:23, 16 February 2011 (UTC)
- Still not right, I think. The Cartesian product of a cycle with K2 is a Prism; it has three edges per vertex, and is non-bipartite if the cycle is odd. Crown graphs have higher degree (except for the eight-vertex one, the one case for which this works) and are always bipartite. —David Eppstein (talk) 23:56, 16 February 2011 (UTC)
- I've been wrong twice, so maybe I ought to give up. But I now think I mean tensor product of Kn and K2. Maproom (talk) 16:14, 20 February 2011 (UTC)
- Yes, that one's already in the first paragraph, where it says "bipartite double cover". —David Eppstein (talk) 17:00, 20 February 2011 (UTC)
- I've been wrong twice, so maybe I ought to give up. But I now think I mean tensor product of Kn and K2. Maproom (talk) 16:14, 20 February 2011 (UTC)
- Still not right, I think. The Cartesian product of a cycle with K2 is a Prism; it has three edges per vertex, and is non-bipartite if the cycle is odd. Crown graphs have higher degree (except for the eight-vertex one, the one case for which this works) and are always bipartite. —David Eppstein (talk) 23:56, 16 February 2011 (UTC)
- You are right. I mean Cartesian product, still of Cn and K2. Maproom (talk) 22:23, 16 February 2011 (UTC)
Kneser graph
"The crown graph can be viewed (...) as a bipartite Kneser graph Hn,1 representing the 1-item and (n − 1)-item subsets of an n-item set, with an edge between two subsets whenever one is contained in the other."
I am having a problem with that sentence, for two reasons :
- The article Kneser graph uses KG as a symbol for the Kneser graph, not H
- The article Kneser graph defines that graph as "with an edge between two sets when both sets are disjoint", here you consider edges when both sets are not disjoint. This makes the crown graph a complement ? opposite ? contrary ? of a Kneser graph.
Maybe that sentence should be reformulated. --MathsPoetry (talk) 14:10, 20 April 2012 (UTC)