84:
74:
53:
22:
162:
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
309:; 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. —
385:
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
140:
514:
130:
193:
106:
509:
197:
454:. 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. --
97:
58:
469:
They are not the same thing. If you look more carefully, you will discover that they are not even named after the same
Johnson. —
190:
33:
272:
474:
416:
362:
324:
314:
262:
215:
168:
187:
250:
488:
459:
430:
401:
39:
257:(if n is odd) or two disjoint copies of Cn (if n is even). Maybe you mean some other kind of product? —
83:
21:
470:
412:
393:
358:
310:
258:
164:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
483:
Oops. Okay, maybe a word of explanation in the text would help, since they have the same name. --
89:
73:
52:
348:
296:
239:
484:
455:
426:
411:
Thanks for catching this. I've uploaded new versions of these images that fix the problem. —
397:
306:
389:
of G? It's at least what the other pages on the subject on
English wikipedia do suggest.
357:
Yes, that one's already in the first paragraph, where it says "bipartite double cover". —
234:. Unless someone points out that I am mistaken, I shall add this to the first paragraph.
337:
328:
285:
228:
503:
451:
183:
344:
292:
235:
276:
219:
102:
79:
323:
I've been wrong twice, so maybe I ought to give up. But I now think I mean
305:
Still not right, I think. The
Cartesian product of a cycle with K2 is a
447:"crown graphs are sometimes called Johnson’s graphs with notation Jn."
492:
478:
463:
434:
420:
405:
366:
352:
318:
300:
266:
243:
200:
172:
253:) preserves the degree of a vertex. Cn x K2 is always either C
182:
The crown graph with an octagonal boundary looks a bit like a
15:
249:
I don't think so. Tensor product with K2 (also known as the
101:, a collaborative effort to improve the coverage of
163:paper, so maybe I’m misunderstanding something.)
8:
47:
49:
19:
214:vertices can also be regarded as the
7:
95:This article is within the scope of
38:It is of interest to the following
14:
515:Low-priority mathematics articles
210:I think that the crown graph on 2
115:Knowledge:WikiProject Mathematics
118:Template:WikiProject Mathematics
82:
72:
51:
20:
392:Same identical problem on page
135:This article has been rated as
1:
493:07:25, 18 December 2012 (UTC)
479:22:50, 17 December 2012 (UTC)
464:22:37, 17 December 2012 (UTC)
367:17:00, 20 February 2011 (UTC)
353:16:14, 20 February 2011 (UTC)
319:23:56, 16 February 2011 (UTC)
301:22:23, 16 February 2011 (UTC)
267:21:59, 16 February 2011 (UTC)
244:21:34, 16 February 2011 (UTC)
201:13:01, 9 September 2009 (UTC)
158:Greedy worst case lower bound
109:and see a list of open tasks.
510:B-Class mathematics articles
173:09:41, 14 January 2009 (UTC)
450:There is an article called
531:
435:21:13, 20 April 2012 (UTC)
421:21:09, 20 April 2012 (UTC)
406:20:34, 20 April 2012 (UTC)
134:
67:
46:
141:project's priority scale
425:You're very welcome. --
98:WikiProject Mathematics
271:You are right. I mean
251:bipartite double cover
178:Polyhedral resemblance
28:This article is rated
121:mathematics articles
394:Bipartite dimension
90:Mathematics portal
34:content assessment
273:Cartesian product
155:
154:
151:
150:
147:
146:
522:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
530:
529:
525:
524:
523:
521:
520:
519:
500:
499:
445:
383:
341:
334:
289:
282:
256:
232:
225:
208:
180:
160:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
528:
526:
518:
517:
512:
502:
501:
498:
497:
496:
495:
471:David Eppstein
444:
443:Article merge?
441:
440:
439:
438:
437:
413:David Eppstein
382:
379:
378:
377:
376:
375:
374:
373:
372:
371:
370:
369:
359:David Eppstein
339:
330:
325:tensor product
311:David Eppstein
287:
278:
259:David Eppstein
254:
230:
221:
216:tensor product
207:
206:Tensor product
204:
179:
176:
165:Thore Husfeldt
159:
156:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
527:
516:
513:
511:
508:
507:
505:
494:
490:
486:
482:
481:
480:
476:
472:
468:
467:
466:
465:
461:
457:
453:
452:Johnson graph
448:
442:
436:
432:
428:
424:
423:
422:
418:
414:
410:
409:
408:
407:
403:
399:
395:
390:
388:
381:Wrong schema?
380:
368:
364:
360:
356:
355:
354:
350:
346:
342:
335:
333:
326:
322:
321:
320:
316:
312:
308:
304:
303:
302:
298:
294:
290:
283:
281:
274:
270:
269:
268:
264:
260:
252:
248:
247:
246:
245:
241:
237:
233:
226:
224:
217:
213:
205:
203:
202:
199:
195:
192:
189:
185:
184:square cupola
177:
175:
174:
170:
166:
157:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
449:
446:
391:
386:
384:
331:
279:
222:
211:
209:
181:
161:
137:Low-priority
136:
96:
62:Low‑priority
40:WikiProjects
485:MathsPoetry
456:MathsPoetry
427:MathsPoetry
398:MathsPoetry
275:, still of
112:Mathematics
103:mathematics
59:Mathematics
504:Categories
387:subgraphs
188:Professor
194:Fiendish
345:Maproom
293:Maproom
236:Maproom
139:on the
30:B-class
36:scale.
307:Prism
489:talk
475:talk
460:talk
431:talk
417:talk
402:talk
396:. --
363:talk
349:talk
336:and
315:talk
297:talk
284:and
263:talk
240:talk
227:and
198:Esq.
186:...
169:talk
327:of
218:of
131:Low
506::
491:)
477:)
462:)
433:)
419:)
404:)
365:)
351:)
343:.
317:)
299:)
291:.
265:)
255:2n
242:)
196:,
191:M.
171:)
487:(
473:(
458:(
429:(
415:(
400:(
361:(
347:(
340:2
338:K
332:n
329:K
313:(
295:(
288:2
286:K
280:n
277:C
261:(
238:(
231:2
229:K
223:n
220:C
212:n
167:(
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.