Talk:Crown graph: Difference between revisions
→Article merge?: different Johnson |
m Maintain {{WPBS}}: 1 WikiProject template. Remove 1 deprecated parameter: field. Tag: |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{WikiProject banner shell|class=B| |
|||
{{maths rating|class=B|importance=low|field=discrete}} |
|||
{{WikiProject Mathematics|importance=low}} |
|||
}} |
|||
==Greedy worst case lower bound== |
==Greedy worst case lower bound== |
||
| Line 31: | Line 33: | ||
There is an article called [[Johnson graph]]. If that is really the same thing as a crown graph, both articles could be merged. If not, the sentence above needs to be reviewed. --[[User:MathsPoetry|MathsPoetry]] ([[User talk:MathsPoetry|talk]]) 22:37, 17 December 2012 (UTC) |
There is an article called [[Johnson graph]]. If that is really the same thing as a crown graph, both articles could be merged. If not, the sentence above needs to be reviewed. --[[User:MathsPoetry|MathsPoetry]] ([[User talk:MathsPoetry|talk]]) 22:37, 17 December 2012 (UTC) |
||
:They are not the same thing. If you look more carefully, you will discover that they are not even named after the same Johnson. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 22:50, 17 December 2012 (UTC) |
:They are not the same thing. If you look more carefully, you will discover that they are not even named after the same Johnson. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 22:50, 17 December 2012 (UTC) |
||
:: Oops. Okay, maybe a word of explanation in the text would help, since they have the same name. --[[User:MathsPoetry|MathsPoetry]] ([[User talk:MathsPoetry|talk]]) 07:25, 18 December 2012 (UTC) |
|||
Latest revision as of 00:08, 9 March 2024
 | This article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Greedy worst case lower bound
[edit]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
[edit]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
[edit]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)
Wrong schema?
[edit]The schema captioned "A biclique cover of the ten-vertex crown graph" seems wrong to me: it has an edge between u3 and v3 (horizontal in red). Aren't the bicliques covering the graph G supposed to be subgraphs of G? It's at least what the other pages on the subject on English wikipedia do suggest.
Same identical problem on page Bipartite dimension. --MathsPoetry (talk) 20:34, 20 April 2012 (UTC)
- Thanks for catching this. I've uploaded new versions of these images that fix the problem. —David Eppstein (talk) 21:09, 20 April 2012 (UTC)
- You're very welcome. --MathsPoetry (talk) 21:13, 20 April 2012 (UTC)
Article merge?
[edit]"crown graphs are sometimes called Johnson’s graphs with notation Jn."
There is an article called Johnson graph. If that is really the same thing as a crown graph, both articles could be merged. If not, the sentence above needs to be reviewed. --MathsPoetry (talk) 22:37, 17 December 2012 (UTC)
- They are not the same thing. If you look more carefully, you will discover that they are not even named after the same Johnson. —David Eppstein (talk) 22:50, 17 December 2012 (UTC)
- Oops. Okay, maybe a word of explanation in the text would help, since they have the same name. --MathsPoetry (talk) 07:25, 18 December 2012 (UTC)