31:
104:
of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph. Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. For example,
116:
of the class, a function from graphs to
Boolean values that is true for graphs in the class and false otherwise; again, any two isomorphic graphs must have the same function value as each other. A graph invariant or graph parameter may similarly be formalized as a function from graphs to a broader
423:, or rather non-isomorphism, since for any invariant at all, two graphs with different values cannot (by definition) be isomorphic. Two graphs with the same invariants may or may not be isomorphic, however.
204:
is monotone. Every monotone property is hereditary, but not necessarily vice versa; for instance, subgraphs of chordal graphs are not necessarily chordal, so being a chordal graph is not monotone.
233:
These definitions may be extended from properties to numerical invariants of graphs: a graph invariant is hereditary, monotone, or minor-closed if the function formalizing the invariant forms a
229:
is minor-closed. Every minor-closed property is monotone, but not necessarily vice versa; for instance, minors of triangle-free graphs are not necessarily themselves triangle-free.
771:
751:
105:
the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant".
909:
869:
96:
While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a
652:
699:
551:
112:
graphs either both belong to the class, or both do not belong to it. Equivalently, a graph property may be formalized using the
689:
77:
679:
578:
389:
51:
39:
350:
In addition, graph properties can be classified according to the type of graph they describe: whether the graph is
939:
721:
467:
889:
185:
885:
562:
43:
684:
674:
669:
944:
807:
730:
572:
538:
471:
47:
788:
615:
566:
544:
511:
475:
209:
201:
180:
151:
463:
234:
113:
240:
Additionally, graph invariants have been studied with respect to their behavior with regard to
905:
865:
803:
584:
526:
420:
109:
101:
857:
819:
80:
that depends only on the abstract structure, not on graph representations such as particular
897:
775:
725:
590:
407:
351:
343:
156:
919:
915:
797:
793:
711:
596:
501:
496:
396:
197:
55:
864:, Colloquium Publications, vol. 60, American Mathematical Society, pp. 41–42,
756:
736:
716:
637:
521:
355:
241:
81:
933:
694:
621:
610:
516:
172:
168:
134:
85:
108:
More formally, a graph property is a class of graphs with the property that any two
647:
642:
602:
556:
506:
308:
226:
65:
35:
632:
385:
214:
118:
17:
901:
627:
479:
403:
359:
122:
378:
A truth-value, true or false, for the indicator function of a graph property.
419:
Easily computable graph invariants are instrumental for fast recognition of
381:
An integer, such as the number of vertices or chromatic number of a graph.
657:
371:
138:
896:, Algorithms and Combinatorics, vol. 28, Springer, pp. 54–56,
559:, a linear combination of the numbers of edges, vertices, and components
599:, the smallest number of colors for the edges in a proper edge coloring
133:
Many graph properties are well-behaved with respect to certain natural
593:, the smallest number of colors for the vertices in a proper coloring
581:, the smallest number of vertices whose removal disconnects the graph
778:, a bivariate function that encodes much of the graph's connectivity
482:
on 4 vertices both have the same chromatic polynomial, for example.
462:. Finding an efficiently-computable such invariant (the problem of
237:
from the corresponding partial order on graphs to the real numbers.
30:
587:, the smallest number of edges whose removal disconnects the graph
125:, that again has the same value for any two isomorphic graphs.
374:
of a function that defines a graph invariant may be one of:
470:. However, even polynomial-valued invariants such as the
27:
Property of graphs that depends only on abstract structure
100:
is defined to be a property preserved under all possible
326:, the value of the invariant on the disjoint union of
291:, the value of the invariant on the disjoint union of
260:, the value of the invariant on the disjoint union of
759:
739:
618:, the largest size of an independent set of vertices
276:. For instance, the number of vertices is additive.
765:
745:
466:) would imply an easy solution to the challenging
34:An example graph, with the properties of being
8:
894:Sparsity: Graphs, Structures, and Algorithms
858:"4.1 Graph parameters and graph properties"
624:, the largest order of a complete subgraph
758:
738:
454:) implies the isomorphism of the graphs
311:(number of matchings) is multiplicative.
29:
831:
415:Graph invariants and graph isomorphism
609:), the least number k such that G is
7:
395:A sequence of integers, such as the
851:
849:
847:
845:
843:
841:
839:
837:
835:
753:-colorings viewed as a function of
117:class of values, such as integers,
575:, the length of the shortest cycle
438:if the identity of the invariants
358:, whether the property applies to
25:
892:(2012), "3.10 Graph Parameters",
653:Colin de Verdière graph invariant
569:lengths between pairs of vertices
800:used to specify graph properties
334:is the maximum of the values on
299:is the product of the values on
862:Large Networks and Graph Limits
806:, a closely related concept in
474:are not usually complete. The
565:, the longest of the shortest
1:
268:is the sum of the values on
42:, and with order 6, size 7,
680:Fractional chromatic number
390:fractional chromatic number
121:, sequences of numbers, or
961:
820:List of integer invariants
175:are hereditary properties.
902:10.1007/978-3-642-27875-4
890:Ossona de Mendez, Patrice
722:Characteristic polynomial
706:Sequences and polynomials
468:graph isomorphism problem
217:of a graph with property
188:of a graph with property
159:of a graph with property
541:, the number of vertices
225:. For instance, being a
196:. For instance, being a
167:. For instance, being a
129:Properties of properties
59:<3, 3, 3, 2, 2, 1>
856:Lovász, László (2012),
318:if, for all two graphs
283:if, for all two graphs
252:if, for all two graphs
767:
747:
685:Algebraic connectivity
675:Betweenness centrality
670:Clustering coefficient
664:Real number invariants
61:
808:chemical graph theory
768:
748:
607:list chromatic number
547:, the number of edges
314:A graph invariant is
279:A graph invariant is
248:A graph invariant is
33:
757:
737:
731:Chromatic polynomial
690:Isoperimetric number
552:connected components
512:Triangle-free graphs
472:chromatic polynomial
366:Values of invariants
342:. For instance, the
307:. For instance, the
207:A graph property is
178:A graph property is
789:Hereditary property
616:Independence number
579:Vertex connectivity
202:triangle-free graph
141:defined on graphs:
52:vertex connectivity
886:Nešetřil, Jaroslav
763:
743:
533:Integer invariants
527:Hamiltonian graphs
464:graph canonization
426:A graph invariant
235:monotonic function
221:also has property
192:also has property
163:also has property
114:indicator function
62:
911:978-3-642-27874-7
871:978-1-4704-1583-9
804:Topological index
796:, one of several
766:{\displaystyle k}
746:{\displaystyle k}
585:Edge connectivity
421:graph isomorphism
145:A graph property
76:is a property of
16:(Redirected from
952:
940:Graph invariants
924:
922:
882:
876:
874:
853:
798:formal languages
776:Tutte polynomial
772:
770:
769:
764:
752:
750:
749:
744:
733:, the number of
726:adjacency matrix
591:Chromatic number
502:Bipartite graphs
497:Connected graphs
408:Tutte polynomial
344:chromatic number
157:induced subgraph
60:
21:
960:
959:
955:
954:
953:
951:
950:
949:
930:
929:
928:
927:
912:
884:
883:
879:
872:
855:
854:
833:
828:
816:
794:Logic of graphs
785:
755:
754:
735:
734:
712:Degree sequence
708:
666:
597:Chromatic index
535:
522:Eulerian graphs
493:
488:
417:
397:degree sequence
368:
242:disjoint unions
198:bipartite graph
131:
94:
74:graph invariant
58:
56:degree sequence
28:
23:
22:
18:Graph invariant
15:
12:
11:
5:
958:
956:
948:
947:
942:
932:
931:
926:
925:
910:
877:
870:
830:
829:
827:
824:
823:
822:
815:
814:External links
812:
811:
810:
801:
791:
784:
781:
780:
779:
773:
762:
742:
728:
719:
717:Graph spectrum
714:
707:
704:
703:
702:
697:
692:
687:
682:
677:
672:
665:
662:
661:
660:
655:
650:
645:
640:
635:
630:
625:
619:
613:
600:
594:
588:
582:
576:
570:
560:
554:
548:
542:
534:
531:
530:
529:
524:
519:
517:Perfect graphs
514:
509:
504:
499:
492:
489:
487:
484:
416:
413:
412:
411:
406:, such as the
400:
393:
388:, such as the
382:
379:
367:
364:
348:
347:
312:
281:multiplicative
277:
231:
230:
205:
176:
135:partial orders
130:
127:
98:graph property
93:
90:
88:of the graph.
70:graph property
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
957:
946:
943:
941:
938:
937:
935:
921:
917:
913:
907:
903:
899:
895:
891:
887:
881:
878:
873:
867:
863:
859:
852:
850:
848:
846:
844:
842:
840:
838:
836:
832:
825:
821:
818:
817:
813:
809:
805:
802:
799:
795:
792:
790:
787:
786:
782:
777:
774:
760:
740:
732:
729:
727:
723:
720:
718:
715:
713:
710:
709:
705:
701:
698:
696:
695:Estrada index
693:
691:
688:
686:
683:
681:
678:
676:
673:
671:
668:
667:
663:
659:
656:
654:
651:
649:
646:
644:
641:
639:
636:
634:
631:
629:
626:
623:
622:Clique number
620:
617:
614:
612:
608:
604:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
564:
561:
558:
555:
553:
549:
546:
543:
540:
537:
536:
532:
528:
525:
523:
520:
518:
515:
513:
510:
508:
507:Planar graphs
505:
503:
500:
498:
495:
494:
490:
485:
483:
481:
477:
473:
469:
465:
461:
457:
453:
449:
445:
441:
437:
433:
429:
424:
422:
414:
409:
405:
401:
398:
394:
391:
387:
383:
380:
377:
376:
375:
373:
365:
363:
361:
357:
353:
345:
341:
337:
333:
329:
325:
321:
317:
313:
310:
306:
302:
298:
294:
290:
286:
282:
278:
275:
271:
267:
263:
259:
255:
251:
247:
246:
245:
243:
238:
236:
228:
224:
220:
216:
212:
211:
206:
203:
199:
195:
191:
187:
183:
182:
177:
174:
173:chordal graph
170:
169:perfect graph
166:
162:
158:
154:
153:
148:
144:
143:
142:
140:
136:
128:
126:
124:
120:
115:
111:
106:
103:
99:
91:
89:
87:
83:
79:
75:
71:
67:
57:
53:
49:
45:
41:
37:
32:
19:
945:Graph theory
893:
880:
861:
648:Wiener index
643:Hosoya index
606:
603:Choosability
557:Circuit rank
459:
455:
451:
447:
443:
439:
435:
434:) is called
431:
427:
425:
418:
369:
349:
339:
335:
331:
327:
323:
319:
315:
309:Hosoya index
304:
300:
296:
292:
288:
284:
280:
273:
269:
265:
261:
257:
253:
249:
239:
232:
227:planar graph
222:
218:
210:minor-closed
208:
193:
189:
179:
164:
160:
150:
146:
132:
119:real numbers
107:
102:isomorphisms
97:
95:
73:
69:
66:graph theory
63:
633:Graph genus
611:k-choosable
410:of a graph.
399:of a graph.
392:of a graph.
386:real number
360:multigraphs
244:of graphs:
215:graph minor
200:or being a
171:or being a
123:polynomials
92:Definitions
934:Categories
826:References
638:Pagenumber
628:Arboricity
550:Number of
491:Properties
480:path graph
476:claw graph
404:polynomial
372:target set
352:undirected
346:is maxing.
152:hereditary
110:isomorphic
82:labellings
38:and being
213:if every
184:if every
155:if every
139:preorders
40:connected
783:See also
700:Strength
658:Boxicity
563:diameter
486:Examples
478:and the
436:complete
356:directed
250:additive
186:subgraph
181:monotone
86:drawings
44:diameter
920:2920058
724:of the
362:, etc.
338:and on
303:and on
272:and on
54:1, and
918:
908:
868:
446:) and
316:maxing
78:graphs
36:planar
573:girth
539:Order
48:girth
906:ISBN
866:ISBN
605:(or
567:path
545:Size
458:and
370:The
330:and
322:and
295:and
287:and
264:and
256:and
68:, a
898:doi
354:or
149:is
137:or
84:or
72:or
64:In
50:3,
46:3,
936::
916:MR
914:,
904:,
888:;
860:,
834:^
402:A
384:A
923:.
900::
875:.
761:k
741:k
460:H
456:G
452:H
450:(
448:I
444:G
442:(
440:I
432:G
430:(
428:I
340:H
336:G
332:H
328:G
324:H
320:G
305:H
301:G
297:H
293:G
289:H
285:G
274:H
270:G
266:H
262:G
258:H
254:G
223:P
219:P
194:P
190:P
165:P
161:P
147:P
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
