733:
Czerwiński, Wojciech; Daviaud, Laure; Fijalkow, Nathanaël; Jurdziński, Marcin; Lazić, Ranko; Parys, Paweł (2018-07-27). "Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games".
199:
may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label.
195:-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in
83:
so a hypercube can be said to be a universal graph for trees. However it is not the smallest such graph: it is known that there is a universal graph for
640:
Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2021), "Adjacency
Labelling for Planar Graphs (And Beyond)",
761:
616:
698:
555:
516:
Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday
25:
788:
303:
146:
513:(1982). "On graphs which contain all sparse graphs". In Rosa, Alexander; Sabidussi, Gert; Turgeon, Jean (eds.).
809:
104:
37:
804:
457:
142:
598:
462:
550:
546:
767:
739:
649:
389:
363:
312:
494:
75:
of graphs can also refer to a member of a sequence of finite graphs that contains all graphs in
608:
602:
203:
In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a
757:
612:
442:
749:
707:
659:
564:
467:
416:
373:
322:
243:
177:
719:
626:
576:
527:
479:
385:
354:; Shi, Niandong (1999). "Universal graphs with forbidden subgraphs and algebraic closure".
336:
283:
257:
715:
622:
572:
523:
475:
381:
332:
279:
253:
80:
594:
351:
210:
The notion of universal graph has been adapted and used for solving mean payoff games.
204:
181:
48:
or random graph. More recent work has focused on universal graphs for a graph family
675:
798:
693:
506:
502:
438:
420:
135:
edges. It is also possible to construct universal graphs for planar graphs that have
771:
393:
510:
271:
227:
112:
61:
41:
753:
17:
471:
45:
736:
Proceedings of the
Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
689:
590:
542:
498:
434:
33:
377:
248:
231:
150:
368:
317:
123:
edges, and that bounded-degree planar graphs have universal graphs with
79:; for instance, every finite tree is a subgraph of a sufficiently large
607:. Algorithms and Combinatorics. Vol. 9. Springer-Verlag. pp.
553:(1989). "Universal graphs for bounded-degree trees and planar graphs".
514:
327:
298:
172:
of graphs has a universal graph of polynomial size, containing every
711:
663:
568:
744:
654:
522:. Annals of Discrete Mathematics. Vol. 12. pp. 21–26.
407:
Wu, A. Y. (1985). "Embedding of tree networks into hypercubes".
103:
edges, and that this is optimal. A construction based on the
791:, "Theorem of the Day" concerning universal graphs for trees
40:. A universal graph of this type was first constructed by
593:(1990). "Separator theorems and their applications". In
278:. Holt, Rinehart, and Winston. pp. 83–85.
696:(1992), "Implicit representation of graphs",
409:Journal of Parallel and Distributed Computing
8:
297:Goldstern, Martin; Kojman, Menachem (1996).
601:; Prömel, Hans Jürgen; et al. (eds.).
450:Journal of the London Mathematical Society
232:"Universal graphs and universal functions"
153:, in the sense that every tournament with
52:: that is, an infinite graph belonging to
743:
653:
461:
367:
326:
316:
247:
678:, Douglas B. West, retrieved 2010-09-17.
676:Sumner's Universal Tournament Conjecture
443:"On universal graphs for spanning trees"
219:
161:vertices contains every polytree with
7:
699:SIAM Journal on Discrete Mathematics
556:SIAM Journal on Discrete Mathematics
184:in which vertices may be labeled by
64:are universal in this sense for the
56:that contains all finite graphs in
14:
356:Advances in Applied Mathematics
71:A universal graph for a family
1:
604:Paths, Flows, and VLSI-Layout
299:"Universal arrow-free graphs"
421:10.1016/0743-7315(85)90026-7
274:(1967). "Universal graphs".
754:10.1137/1.9781611975482.142
180:, if and only if it has an
115:have universal graphs with
826:
304:Acta Mathematica Hungarica
182:adjacency labelling scheme
276:A Seminar in Graph Theory
107:can be used to show that
87:-vertex trees, with only
472:10.1112/jlms/s2-27.2.203
165:vertices as a subgraph.
105:planar separator theorem
789:The panarborial formula
36:) graph as an induced
738:. pp. 2333–2349.
378:10.1006/aama.1998.0641
249:10.4064/aa-9-4-331-340
44:and is now called the
68:-clique-free graphs.
551:Rosenberg, Arnold L.
176:-vertex graph as an
159: − 2
60:. For instance, the
541:Bhatt, Sandeep N.;
143:Sumner's conjecture
91: vertices and
32:finite (or at-most-
642:Journal of the ACM
328:10.1007/BF00052907
149:are universal for
763:978-1-61197-548-2
688:Kannan, Sampath;
618:978-0-387-52685-0
817:
776:
775:
747:
730:
724:
722:
685:
679:
673:
667:
666:
657:
637:
631:
630:
591:Chung, Fan R. K.
587:
581:
580:
543:Chung, Fan R. K.
538:
532:
531:
521:
491:
485:
483:
465:
447:
431:
425:
424:
404:
398:
397:
371:
347:
341:
340:
330:
320:
294:
288:
287:
268:
262:
261:
251:
236:Acta Arithmetica
224:
198:
194:
178:induced subgraph
175:
171:
164:
160:
140:
134:
122:
110:
102:
90:
86:
78:
74:
67:
59:
51:
825:
824:
820:
819:
818:
816:
815:
814:
810:Infinite graphs
795:
794:
785:
780:
779:
764:
732:
731:
727:
712:10.1137/0405049
687:
686:
682:
674:
670:
664:10.1145/3477542
639:
638:
634:
619:
595:Korte, Bernhard
589:
588:
584:
569:10.1137/0402014
547:Leighton, F. T.
540:
539:
535:
519:
499:Chung, F. R. K.
493:
492:
488:
463:10.1.1.108.3415
445:
435:Chung, F. R. K.
433:
432:
428:
406:
405:
401:
369:math.LO/9809202
352:Shelah, Saharon
350:Cherlin, Greg;
349:
348:
344:
318:math.LO/9409206
296:
295:
291:
270:
269:
265:
226:
225:
221:
216:
196:
185:
173:
169:
162:
154:
136:
129: log
124:
116:
108:
97: log
92:
88:
84:
81:hypercube graph
76:
72:
65:
57:
49:
24:is an infinite
22:universal graph
12:
11:
5:
823:
821:
813:
812:
807:
805:Graph families
797:
796:
793:
792:
784:
783:External links
781:
778:
777:
762:
725:
706:(4): 596–603,
694:Rudich, Steven
680:
668:
632:
617:
599:Lovász, László
582:
563:(2): 145–155.
533:
511:Spencer, J. H.
486:
456:(2): 203–211.
426:
415:(3): 238–249.
399:
362:(4): 454–491.
342:
311:(4): 319–326.
289:
263:
242:(4): 331–340.
218:
217:
215:
212:
205:complete graph
28:that contains
13:
10:
9:
6:
4:
3:
2:
822:
811:
808:
806:
803:
802:
800:
790:
787:
786:
782:
773:
769:
765:
759:
755:
751:
746:
741:
737:
729:
726:
721:
717:
713:
709:
705:
701:
700:
695:
691:
684:
681:
677:
672:
669:
665:
661:
656:
651:
647:
643:
636:
633:
628:
624:
620:
614:
610:
606:
605:
600:
596:
592:
586:
583:
578:
574:
570:
566:
562:
558:
557:
552:
548:
544:
537:
534:
529:
525:
518:
517:
512:
508:
507:Graham, R. L.
504:
500:
496:
490:
487:
481:
477:
473:
469:
464:
459:
455:
451:
444:
440:
439:Graham, R. L.
436:
430:
427:
422:
418:
414:
410:
403:
400:
395:
391:
387:
383:
379:
375:
370:
365:
361:
357:
353:
346:
343:
338:
334:
329:
324:
319:
314:
310:
306:
305:
300:
293:
290:
285:
281:
277:
273:
267:
264:
259:
255:
250:
245:
241:
237:
233:
229:
223:
220:
213:
211:
208:
206:
201:
192:
188:
183:
179:
166:
158:
152:
148:
144:
139:
132:
128:
120:
114:
113:planar graphs
106:
100:
96:
82:
69:
63:
62:Henson graphs
55:
47:
43:
39:
35:
31:
27:
23:
19:
735:
728:
703:
697:
683:
671:
645:
641:
635:
603:
585:
560:
554:
536:
515:
489:
453:
449:
429:
412:
408:
402:
359:
355:
345:
308:
302:
292:
275:
266:
239:
235:
222:
209:
202:
190:
186:
167:
156:
145:states that
137:
130:
126:
118:
98:
94:
70:
53:
42:Richard Rado
29:
21:
15:
648:(6): 1–33,
147:tournaments
141:vertices.
18:mathematics
799:Categories
745:1807.10546
690:Naor, Moni
655:2003.04280
214:References
189:(log
46:Rado graph
503:Erdős, P.
495:Babai, L.
458:CiteSeerX
168:A family
151:polytrees
34:countable
772:51865783
441:(1983).
394:17529604
272:Rado, R.
230:(1964).
228:Rado, R.
111:-vertex
38:subgraph
720:1186827
627:1083375
577:0990447
528:0806964
480:0692525
386:1683298
337:1428038
284:0214507
258:0172268
770:
760:
718:
625:
615:
575:
526:
478:
460:
392:
384:
335:
282:
256:
768:S2CID
740:arXiv
650:arXiv
609:17–34
520:(PDF)
446:(PDF)
390:S2CID
364:arXiv
313:arXiv
30:every
26:graph
758:ISBN
613:ISBN
309:1973
20:, a
750:doi
708:doi
660:doi
565:doi
468:doi
417:doi
374:doi
323:doi
244:doi
16:In
801::
766:.
756:.
748:.
716:MR
714:,
702:,
692:;
658:,
646:68
644:,
623:MR
621:.
611:.
597:;
573:MR
571:.
559:.
549:;
545:;
524:MR
509:;
505:;
501:;
497:;
476:MR
474:.
466:.
454:27
452:.
448:.
437:;
411:.
388:.
382:MR
380:.
372:.
360:22
358:.
333:MR
331:.
321:.
307:.
301:.
280:MR
254:MR
252:.
238:.
234:.
207:.
125:O(
117:O(
93:O(
774:.
752::
742::
723:.
710::
704:5
662::
652::
629:.
579:.
567::
561:2
530:.
484:.
482:.
470::
423:.
419::
413:2
396:.
376::
366::
339:.
325::
315::
286:.
260:.
246::
240:9
197:F
193:)
191:n
187:O
174:n
170:F
163:n
157:n
155:2
138:n
133:)
131:n
127:n
121:)
119:n
109:n
101:)
99:n
95:n
89:n
85:n
77:F
73:F
66:i
58:F
54:F
50:F
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.