Talk:Crown graph: Difference between revisions

Content deleted Content added

Inline

Revision as of 20:34, 20 April 2012

Mathematics B‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
B	This article has been rated as B-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

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)[reply]

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)[reply]

Tensor product

I think that the crown graph on 2n vertices can also be regarded as the tensor product of C_n and K₂. Unless someone points out that I am mistaken, I shall add this to the first paragraph. Maproom (talk) 21:34, 16 February 2011 (UTC)[reply]

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 C_2n (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)[reply]

You are right. I mean Cartesian product, still of C_n and K₂. Maproom (talk) 22:23, 16 February 2011 (UTC)[reply]

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)[reply]

I've been wrong twice, so maybe I ought to give up. But I now think I mean tensor product of K_n and K₂. Maproom (talk) 16:14, 20 February 2011 (UTC)[reply]

Yes, that one's already in the first paragraph, where it says "bipartite double cover". —David Eppstein (talk) 17:00, 20 February 2011 (UTC)[reply]

Wrong schema?

The schema showing a covering of the crown graph with several complete bipartite subgraphs seems wrong to me: it has an edge between u3 and v3 (in red). Aren't the bicliques supposed to be subgraphs of G? It's at least what the other pages on the subject on English wikipedia do suggest. --MathsPoetry (talk) 20:34, 20 April 2012 (UTC)[reply]

@@ Line 17: / Line 17: @@
 ::::I've been wrong twice, so maybe I ought to give up.  But I now think I mean [[Tensor product of graphs|tensor product]] of [[Complete graph|K<sub>''n''</sub>]] and [[Complete graph|K<sub>2</sub>]]. [[User:Maproom|Maproom]] ([[User talk:Maproom|talk]]) 16:14, 20 February 2011 (UTC)
 :::::Yes, that one's already in the first paragraph, where it says "bipartite double cover". —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:00, 20 February 2011 (UTC)
+== Wrong schema? ==
+The schema showing a covering of the crown graph with several complete bipartite subgraphs seems wrong to me: it has an edge between u3 and v3 (in red). Aren't the bicliques supposed to be ''subgraphs'' of G? It's at least what the other pages on the subject on English wikipedia do suggest. --[[User:MathsPoetry|MathsPoetry]] ([[User talk:MathsPoetry|talk]]) 20:34, 20 April 2012 (UTC)