179:
131:
147:
163:
477:
is the number of edges. A practical optimization is to limit the depth of the BFS to a depth that depends on the length of the smallest cycle discovered so far. Better algorithms are known in the case where the girth is even and when the graph is planar. In terms of lower bounds, computing the girth
608:
743:
435:
475:
455:
686:
112:
is the unique 8-cage. There may exist multiple cages for a given girth. For instance there are three nonisomorphic 10-cages, each with 70 vertices: the
178:
54:. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is
757:
362:
Thought of as the least length of a non-trivial cycle, the girth admits natural generalisations as the 1-systole or higher systoles in
626:
393:, the matroid girth equals the girth of the underlying graph, while for a co-graphic matroid it equals the edge connectivity.
275:
130:
146:
230:
construction used to form the Grötzsch graph produces triangle-free graphs of arbitrarily large chromatic number.
839:
693:
162:
479:
185:
121:
370:
47:
295:. Therefore, removing one vertex from each short cycle leaves a smaller graph with girth greater than
402:
235:
43:
85:
67:
55:
613:, London Mathematical Society Student Texts, vol. 55, Cambridge University Press, Cambridge,
306:
Explicit, though large, graphs with high girth and chromatic number can be constructed as certain
816:
790:
582:
781:
Chang, Hsien-Chih; Lu, Hsueh-I. (2013). "Computing the Girth of a Planar Graph in Linear Time".
808:
737:
622:
600:
512:
363:
299:, in which each color class of a coloring must be small and which therefore requires at least
223:
800:
658:
614:
572:
320:
215:
109:
39:
17:
719:
672:
636:
408:
668:
632:
536:
390:
344:
of a graph are the lengths of a shortest odd cycle and shortest even cycle respectively.
113:
246:
vertices, formed by choosing independently whether to include each edge with probability
649:
Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid",
460:
440:
382:
325:
137:
97:
833:
586:
560:
386:
231:
153:
117:
101:
820:
604:
374:
315:
311:
307:
239:
46:
contained in the graph. If the graph does not contain any cycles (that is, it is a
31:
227:
169:
105:
73:
663:
378:
812:
618:
758:"ds.algorithms - Optimal algorithm for finding the girth of a sparse graph?"
521:
577:
516:
540:
51:
804:
100:
is the unique 5-cage (it is the smallest cubic graph of girth 5), the
795:
389:, the size of the smallest dependent set in the matroid. For a
226:
is triangle-free and has chromatic number 4, and repeating the
401:
The girth of an undirected graph can be computed by running a
718:
Völkel, Christoph Dürr, Louis
Abraham and Finn (2016-11-06).
610:
Elementary number theory, group theory, and
Ramanujan graphs
550:(Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
463:
443:
411:
234:
was the first to prove the general result, using the
469:
449:
429:
27:Length of a shortest cycle contained in the graph
381:, and vice versa. These concepts are unified in
478:of a graph is at least as hard as solving the
8:
742:: CS1 maint: multiple names: authors list (
687:"Question 3: Computing the girth of a graph"
762:Theoretical Computer Science Stack Exchange
457:is the number of vertices of the graph and
210:, there exists a graph with girth at least
80:that is as small as possible is known as a
501:, p.8. 3rd Edition, Springer-Verlag, 2005
359:(simple) cycle, rather than the shortest.
76:(all vertices have degree three) of girth
794:
662:
576:
462:
442:
410:
563:(1959), "Graph theory and probability",
252:, has, with probability tending to 1 as
490:
126:
735:
7:
546:. Electronic supplement to the book
373:, in the sense that the girth of a
238:. More precisely, he showed that a
25:
405:from each node, with complexity
377:is the edge connectivity of its
355:of a graph is the length of the
177:
161:
145:
129:
565:Canadian Journal of Mathematics
424:
415:
50:), its girth is defined to be
1:
369:Girth is the dual concept to
108:is the unique 7-cage and the
651:Discrete Applied Mathematics
42:is the length of a shortest
18:Circumference (graph theory)
856:
256:goes to infinity, at most
202:For any positive integers
104:is the unique 6-cage, the
65:
783:SIAM Journal on Computing
664:10.1016/j.dam.2007.06.015
607:; Valette, Alain (2003),
619:10.1017/CBO9780511615825
480:triangle finding problem
303:colors in any coloring.
198:Girth and graph coloring
548:Distance-Regular Graphs
578:10.4153/CJM-1959-003-9
471:
451:
431:
472:
452:
432:
430:{\displaystyle O(nm)}
326:expansion coefficient
461:
441:
409:
403:breadth-first search
274:or less, but has no
236:probabilistic method
222:; for instance, the
537:Brouwer, Andries E.
318:. These remarkable
186:Tutte–Coxeter graph
68:Cage (graph theory)
699:on August 29, 2017
601:Davidoff, Giuliana
513:Weisstein, Eric W.
467:
447:
427:
387:girth of a matroid
192:) has a girth of 8
122:Harries–Wong graph
805:10.1137/110832033
657:(18): 2456–2470,
470:{\displaystyle m}
450:{\displaystyle n}
371:edge connectivity
364:systolic geometry
270:cycles of length
16:(Redirected from
847:
840:Graph invariants
825:
824:
798:
789:(3): 1077–1094.
778:
772:
771:
769:
768:
754:
748:
747:
741:
733:
731:
730:
720:"Shortest cycle"
715:
709:
708:
706:
704:
698:
692:. Archived from
691:
683:
677:
675:
666:
646:
640:
639:
597:
591:
589:
580:
557:
551:
545:
533:
527:
526:
525:
508:
502:
495:
476:
474:
473:
468:
456:
454:
453:
448:
436:
434:
433:
428:
353:
352:
332:Related concepts
324:also have large
321:Ramanujan graphs
302:
298:
294:
293:
292:
285:
273:
269:
268:
267:
263:
255:
251:
245:
221:
216:chromatic number
213:
209:
205:
190:Tutte eight cage
181:
172:has a girth of 7
165:
156:has a girth of 6
149:
140:has a girth of 5
133:
110:Tutte eight cage
95:
83:
79:
40:undirected graph
21:
855:
854:
850:
849:
848:
846:
845:
844:
830:
829:
828:
780:
779:
775:
766:
764:
756:
755:
751:
734:
728:
726:
717:
716:
712:
702:
700:
696:
689:
685:
684:
680:
648:
647:
643:
629:
599:
598:
594:
559:
558:
554:
535:
534:
530:
511:
510:
509:
505:
496:
492:
488:
459:
458:
439:
438:
407:
406:
399:
391:graphic matroid
350:
349:
334:
300:
296:
287:
281:
280:
279:
276:independent set
271:
265:
259:
258:
257:
253:
247:
243:
219:
211:
207:
203:
200:
193:
182:
173:
166:
157:
150:
141:
134:
114:Balaban 10-cage
89:
81:
77:
70:
64:
28:
23:
22:
15:
12:
11:
5:
853:
851:
843:
842:
832:
831:
827:
826:
773:
749:
710:
678:
641:
627:
592:
552:
528:
503:
489:
487:
484:
482:on the graph.
466:
446:
426:
423:
420:
417:
414:
398:
395:
383:matroid theory
333:
330:
224:Grötzsch graph
199:
196:
195:
194:
183:
176:
174:
167:
160:
158:
151:
144:
142:
138:Petersen graph
135:
128:
98:Petersen graph
66:Main article:
63:
60:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
852:
841:
838:
837:
835:
822:
818:
814:
810:
806:
802:
797:
792:
788:
784:
777:
774:
763:
759:
753:
750:
745:
739:
725:
721:
714:
711:
695:
688:
682:
679:
674:
670:
665:
660:
656:
652:
645:
642:
638:
634:
630:
628:0-521-82426-5
624:
620:
616:
612:
611:
606:
605:Sarnak, Peter
602:
596:
593:
588:
584:
579:
574:
570:
566:
562:
556:
553:
549:
544:
543:
538:
532:
529:
524:
523:
518:
514:
507:
504:
500:
494:
491:
485:
483:
481:
464:
444:
421:
418:
412:
404:
396:
394:
392:
388:
384:
380:
376:
372:
367:
365:
360:
358:
354:
351:circumference
345:
343:
339:
331:
329:
327:
323:
322:
317:
316:finite fields
313:
312:linear groups
309:
308:Cayley graphs
304:
291:
284:
277:
262:
250:
241:
237:
233:
229:
225:
217:
197:
191:
187:
180:
175:
171:
164:
159:
155:
154:Heawood graph
148:
143:
139:
132:
127:
125:
123:
119:
118:Harries graph
115:
111:
107:
103:
102:Heawood graph
99:
96:-cage). The
93:
87:
75:
69:
61:
59:
57:
56:triangle-free
53:
49:
45:
41:
37:
33:
19:
786:
782:
776:
765:. Retrieved
761:
752:
727:. Retrieved
723:
713:
703:February 22,
701:. Retrieved
694:the original
681:
654:
650:
644:
609:
595:
568:
564:
555:
547:
541:
531:
520:
506:
499:Graph Theory
498:
497:R. Diestel,
493:
400:
375:planar graph
368:
361:
356:
348:
346:
341:
337:
335:
319:
305:
289:
282:
260:
248:
240:random graph
201:
189:
91:
71:
35:
32:graph theory
29:
561:Erdős, Paul
397:Computation
228:Mycielskian
170:McGee graph
106:McGee graph
74:cubic graph
767:2023-02-22
729:2023-02-22
486:References
379:dual graph
342:even girth
232:Paul Erdős
813:0097-5397
796:1104.4892
587:122784453
571:: 34–38,
522:MathWorld
338:odd girth
218:at least
88:(or as a
834:Category
738:cite web
278:of size
120:and the
52:infinity
821:2493979
724:TryAlgo
673:2365057
637:1989434
517:"Girth"
385:by the
357:longest
286:⁄
264:⁄
819:
811:
671:
635:
625:
585:
437:where
116:, the
48:forest
38:of an
34:, the
817:S2CID
791:arXiv
697:(PDF)
690:(PDF)
583:S2CID
542:Cages
314:over
62:Cages
44:cycle
36:girth
809:ISSN
744:link
705:2023
623:ISBN
347:The
340:and
336:The
214:and
206:and
184:The
168:The
152:The
136:The
86:cage
801:doi
659:doi
655:155
615:doi
573:doi
310:of
242:on
90:(3,
30:In
836::
815:.
807:.
799:.
787:42
785:.
760:.
740:}}
736:{{
722:.
669:MR
667:,
653:,
633:MR
631:,
621:,
603:;
581:,
569:11
567:,
539:,
519:,
515:,
366:.
328:.
124:.
72:A
58:.
823:.
803::
793::
770:.
746:)
732:.
707:.
676:.
661::
617::
590:.
575::
465:m
445:n
425:)
422:m
419:n
416:(
413:O
301:k
297:g
290:k
288:2
283:n
272:g
266:2
261:n
254:n
249:n
244:n
220:χ
212:g
208:χ
204:g
188:(
94:)
92:g
84:-
82:g
78:g
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
