40:
437:
429:
of a graph is the minimum number of colors needed to color its vertices in such a way that every two color classes together form a subgraph in which all connected components are stars. The graphs of
515:
A geometric realization of the star graph, formed by identifying the edges with intervals of some fixed length, is used as a local model of curves in
673:
849:
425:
is the minimum number of forests that a graph can be partitioned into such that each tree in each forest is a star, and the
174:
365:
767:
688:
844:
519:. A tropical curve is defined to be a metric space that is locally isomorphic to a star-shaped metric graph.
771:
593:
605:, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, pp. 153â171,
733:
17:
528:
199:
253:
95:
290:
509:
345:
140:
68:
531:- a generalization of the concept of a star from a graph to an arbitrary simplicial complex.
821:
610:
575:
316:
246:
105:
8:
388:
344:
Stars may also be described as the only connected graphs in which at most one vertex has
215:
148:
144:
83:
825:
811:
654:
337:). Additionally, the star has large automorphism group, namely, the symmetric group on
566:
392:
788:
718:
684:
516:
369:
485:
The set of distances between the vertices of a claw provides an example of a finite
783:
749:
713:
704:
Hakimi, S. L.; Mitchem, J.; Schmeichel, E. E. (1996), "Star arboricity of graphs",
644:
636:
597:
589:
561:
505:
361:
327:
305:
115:
674:"PrĂŒfer numbers: A poor representation of spanning trees for evolutionary search"
624:
606:
571:
494:
418:
357:
320:
302:
152:
125:
737:
681:
GECCO-2001: Proceedings of the
Genetic and Evolutionary Computation Conference
649:
838:
549:
426:
552:; Flandrin, Evelyne; RyjĂĄÄek, ZdenÄk (1997), "Claw-free graphs â A survey",
501:
486:
375:
are themselves isomorphic, with the exception of the claw and the triangle
183:
803:
430:
806:(2002), "Finite metric spacesâcombinatorics, geometry and algorithms",
658:
422:
372:
753:
433:
1 are exactly the graphs in which each connected component is a star.
816:
640:
627:(January 1932), "Congruent Graphs and the Connectivity of Graphs",
490:
672:
Gottlieb, J.; Julstrom, B. A.; Rothlauf, F.; Raidl, G. R. (2001).
39:
774:(1991), "Graph minors. X. Obstructions to tree-decomposition",
436:
671:
808:
Proc. International
Congress of Mathematicians, Beijing
703:
27:
Tree graph with one central node and leaves of length 1
548:
364:. They are also one of the exceptional cases of the
351:
731:
588:
836:
766:
508:modeled after the star graph, is important in
391:. As with any tree, stars may be encoded by a
596:(2005), "The structure of claw-free graphs",
815:
787:
717:
648:
565:
360:, graphs that do not have any claw as an
435:
623:
356:Claws are notable in the definition of
236:). Alternatively, some authors define
14:
837:
802:
683:. Morgan Kaufmann. pp. 343â350.
480:
732:Fertin, Guillaume; Raspaud, André;
24:
222:leaves (but no internal nodes and
25:
861:
810:, vol. 3, pp. 573â586,
395:; the PrĂŒfer sequence for a star
366:Whitney graph isomorphism theorem
352:Relation to other graph families
273:A star with 3 edges is called a
38:
776:Journal of Combinatorial Theory
629:American Journal of Mathematics
421:are defined in terms of stars.
53:. (Some authors index this as
796:
760:
725:
697:
665:
617:
582:
542:
175:Table of graphs and parameters
13:
1:
850:Parametric families of graphs
599:Surveys in combinatorics 2005
567:10.1016/S0012-365X(96)00045-3
535:
414:copies of the center vertex.
789:10.1016/0095-8956(91)90061-N
719:10.1016/0012-365X(94)00313-8
387:A star is a special kind of
7:
522:
308:, and has diameter 2 (when
256:2; in which case a star of
218:with one internal node and
10:
866:
368:: in general, graphs with
738:"Star coloring of graphs"
529:Star (simplicial complex)
173:
158:
136:
124:
114:
104:
94:
82:
67:
37:
32:
489:that cannot be embedded
200:complete bipartite graph
742:Journal of Graph Theory
477:
319:â (it has no cycles),
510:distributed computing
439:
427:star chromatic number
297:is even and not when
845:Trees (graph theory)
554:Discrete Mathematics
826:2003math......4466L
650:10338.dmlcz/101067
497:of any dimension.
481:Other applications
478:
348:greater than one.
245:to be the tree of
754:10.1002/jgt.20029
590:Chudnovsky, Maria
517:tropical geometry
301:is odd. It is an
180:
179:
16:(Redirected from
857:
829:
828:
819:
800:
794:
792:
791:
772:Seymour, Paul D.
764:
758:
756:
729:
723:
722:
721:
701:
695:
694:
678:
669:
663:
661:
652:
625:Whitney, Hassler
621:
615:
613:
604:
586:
580:
578:
569:
546:
506:computer network
475:
466:
457:
448:
440:The star graphs
419:graph invariants
413:
406:
383:
362:induced subgraph
358:claw-free graphs
340:
336:
328:chromatic number
325:
314:
306:matchstick graph
300:
296:
288:
269:
262:
251:
244:
235:
228:
221:
213:
197:
169:
132:
116:Chromatic number
90:
78:
61:
52:
42:
30:
29:
21:
865:
864:
860:
859:
858:
856:
855:
854:
835:
834:
833:
832:
801:
797:
768:Robertson, Neil
765:
761:
730:
726:
702:
698:
691:
676:
670:
666:
641:10.2307/2371086
622:
618:
602:
587:
583:
560:(1â3): 87â147,
547:
543:
538:
525:
495:Euclidean space
483:
474:
468:
465:
459:
456:
450:
447:
441:
423:Star arboricity
408:
405:
396:
393:PrĂŒfer sequence
382:
376:
354:
338:
331:
323:
321:chromatic index
309:
303:edge-transitive
298:
294:
287:
281:
264:
257:
249:
243:
237:
230:
223:
219:
211:
202:
196:
190:
168:
162:
151:
147:
143:
141:Edge-transitive
130:
126:Chromatic index
88:
73:
63:
60:
54:
51:
45:
28:
23:
22:
15:
12:
11:
5:
863:
853:
852:
847:
831:
830:
804:Linial, Nathan
795:
782:(2): 153â190,
759:
748:(3): 163â182,
724:
706:Discrete Math.
696:
689:
664:
635:(1): 150â168,
616:
581:
550:Faudree, Ralph
540:
539:
537:
534:
533:
532:
524:
521:
482:
479:
472:
463:
454:
445:
400:
380:
353:
350:
285:
241:
206:
194:
178:
177:
171:
170:
166:
160:
156:
155:
138:
134:
133:
128:
122:
121:
118:
112:
111:
108:
102:
101:
98:
92:
91:
86:
80:
79:
71:
65:
64:
58:
49:
43:
35:
34:
26:
9:
6:
4:
3:
2:
862:
851:
848:
846:
843:
842:
840:
827:
823:
818:
813:
809:
805:
799:
790:
785:
781:
777:
773:
769:
763:
755:
751:
747:
743:
739:
735:
728:
720:
715:
711:
707:
700:
692:
686:
682:
675:
668:
660:
656:
651:
646:
642:
638:
634:
630:
626:
620:
612:
608:
601:
600:
595:
594:Seymour, Paul
591:
585:
577:
573:
568:
563:
559:
555:
551:
545:
541:
530:
527:
526:
520:
518:
513:
511:
507:
503:
498:
496:
492:
491:isometrically
488:
471:
462:
453:
444:
438:
434:
432:
428:
424:
420:
415:
411:
404:
399:
394:
390:
385:
379:
374:
371:
367:
363:
359:
349:
347:
342:
334:
329:
322:
318:
312:
307:
304:
292:
291:edge-graceful
284:
278:
276:
271:
267:
260:
255:
252:with maximum
248:
240:
233:
226:
217:
210:
205:
201:
193:
189:
185:
176:
172:
165:
161:
157:
154:
150:
149:Unit distance
146:
142:
139:
135:
129:
127:
123:
119:
117:
113:
109:
107:
103:
99:
97:
93:
87:
85:
81:
76:
72:
70:
66:
57:
48:
41:
36:
31:
19:
817:math/0304466
807:
798:
779:
775:
762:
745:
741:
727:
709:
705:
699:
680:
667:
632:
628:
619:
598:
584:
557:
553:
544:
514:
502:star network
499:
487:metric space
484:
469:
460:
451:
442:
416:
409:
407:consists of
402:
397:
386:
377:
355:
343:
332:
310:
282:
279:
274:
272:
265:
258:
238:
231:
229:leaves when
224:
208:
203:
191:
187:
184:graph theory
181:
163:
74:
55:
46:
734:Reed, Bruce
431:branchwidth
373:line graphs
839:Categories
690:1558607749
536:References
370:isomorphic
137:Properties
18:Star graph
712:: 93â98,
341:letters.
280:The star
153:Bipartite
44:The star
736:(2004),
523:See also
417:Several
330:2 (when
270:leaves.
254:diameter
212: :
159:Notation
96:Diameter
69:Vertices
822:Bibcode
659:2371086
611:2187738
576:1432221
493:into a
198:is the
687:
657:
609:
574:
346:degree
335:> 0
326:, and
313:> 1
261:> 2
812:arXiv
677:(PDF)
655:JSTOR
603:(PDF)
317:girth
293:when
247:order
106:Girth
84:Edges
685:ISBN
504:, a
500:The
467:and
389:tree
275:claw
263:has
216:tree
188:star
186:, a
145:Tree
33:Star
784:doi
750:doi
714:doi
710:149
645:hdl
637:doi
562:doi
558:164
512:.
412:â 1
384:.
315:),
289:is
268:â 1
234:†1
227:+ 1
182:In
77:+ 1
841::
820:,
780:52
778:,
770:;
746:47
744:,
740:,
708:,
679:.
653:,
643:,
633:54
631:,
607:MR
592:;
572:MR
570:,
556:,
458:,
449:,
401:1,
277:.
214:a
207:1,
62:.)
824::
814::
793:.
786::
757:.
752::
716::
693:.
662:.
647::
639::
614:.
579:.
564::
476:.
473:6
470:S
464:5
461:S
455:4
452:S
446:3
443:S
410:k
403:k
398:K
381:3
378:K
339:k
333:k
324:k
311:l
299:k
295:k
286:k
283:S
266:k
259:k
250:k
242:k
239:S
232:k
225:k
220:k
209:k
204:K
195:k
192:S
167:k
164:S
131:k
120:2
110:â
100:2
89:k
75:k
59:8
56:S
50:7
47:S
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
