284:
33:
181:. The same neighbourhood notation may also be used to refer to sets of adjacent vertices rather than the corresponding induced subgraphs. The neighbourhood described above does not include
260:
of its neighbourhoods. In addition, many important classes of graphs may be defined by properties of their neighbourhoods, or by symmetries that relate neighbourhoods to each other.
487:
611:
144:
237:
177:
874:
Finite
Geometries, Buildings, and Related Topics: Papers from the Conference on Buildings and Related Geometries held in Pingree Park, Colorado, July 17–23, 1988
36:
In this graph, the vertices adjacent to 5 are 1, 2 and 4. The neighbourhood of 5 is the graph consisting of the vertices 1, 2, 4 and the edge connecting 1 and 2.
571:, embeddings of graphs on surfaces in such a way that the faces of the embedding are the cliques of the graph. Locally cyclic graphs can have as many as
17:
692:
is the union of the neighbourhoods of the vertices, and so it is the set of all vertices adjacent to at least one member of
1042:
1054:
1004:
975:
431:
1122:
719:; modular decomposition algorithms have applications in other graph algorithms including the recognition of
63:
747:
41:
275:
that connects a vertex to itself; if such an edge exists, the vertex belongs to its own neighbourhood.
639:
is at most two; for instance, the graph of the regular icosahedron is claw-free because it is locally
758:
456:
742:
568:
574:
253:
966:
113:
712:
268:
56:
910:
881:
657:
206:
153:
8:
872:, in Kantor, William M.; Liebler, Robert A.; Payne, Stanley E.; Shult, Ernest E. (eds.),
720:
632:
620:
513:
427:
272:
71:
627:
of the neighbourhood of the vertex does not contain a triangle. A graph that is locally
1101:
1082:
940:
737:
989:
970:
1038:
1017:
517:
420:
304:
1105:
944:
1091:
1063:
1030:
1029:, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 242–247,
1013:
984:
932:
898:
661:
624:
442:
378:. The only graphs that are locally complete are disjoint unions of complete graphs.
249:
90:
866:
906:
877:
672:
616:
264:
241:. When stated without any qualification, a neighbourhood is assumed to be open.
918:
732:
496:
is closed under the operation of taking induced subgraphs, then every graph in
358:
245:
244:
Neighbourhoods may be used to represent graphs in computer algorithms, via the
1080:(1983), "Improving the performance guarantee for approximate graph coloring",
902:
382:
1116:
1077:
923:
752:
668:
509:
505:
271:
of a vertex is equal to the number of adjacent vertices. A special case is a
1052:
Seress, Ákos; Szabó, Tibor (1995), "Dense graphs with cycle neighborhoods",
1068:
416:
48:
999:
716:
550:
539:
524:
340:
292:
257:
876:, Oxford Science Publications, Oxford University Press, pp. 85–94,
1034:
952:
936:
528:
339:, shown in the figure, each vertex has a neighbourhood isomorphic to a
336:
288:
1096:
283:
711:. Any graph has a uniquely recursive decomposition into modules, its
959:, Colloques internationaux C.N.R.S., vol. 260, pp. 219–223
703:
of vertices in a graph is said to be a module if every vertex in
1002:(1992), "Generating locally cyclic triangulations of surfaces",
971:"Whitney triangulations, local girth and iterated clique graphs"
867:"Local recognition of graphs, buildings, and related geometries"
761:, a generalization of the neighborhood to simplicial complexes
1025:
Sedláček, J. (1983), "On local properties of finite graphs",
27:
Subgraph made of all nodes linked to a given node of a graph
32:
964:
809:
423:. However, not every locally outerplanar graph is planar.
193:; it is also possible to define a neighbourhood in which
40:
For other meanings of neighbourhoods in mathematics, see
97:, i.e., the graph composed of the vertices adjacent to
818:
671:
are locally grid, meaning that each neighborhood is a
523:
A graph is locally cyclic if every neighbourhood is a
577:
459:
412:-1). More generally any Turán graph is locally Turán.
323:
have neighbourhoods that belong to some graph family
252:
representations. Neighbourhoods are also used in the
209:
156:
116:
787:
343:
of four vertices, so the octahedron is locally
889:Fronček, Dalibor (1989), "Locally linear graphs",
830:
660:are the graphs in which every neighbourhood is an
605:
481:
231:
171:
138:
1114:
842:
916:
805:
957:Problèmes combinatoires et théorie des graphes
256:of a graph, which is a measure of the average
101:and all edges connecting vertices adjacent to
955:(1978), "Graphs with given neighborhoods I",
715:, which can be constructed from the graph in
278:
1051:
997:
824:
813:
707:has the same set of neighbours outside of
1095:
1076:
1067:
1055:Journal of Combinatorial Theory, Series B
1005:Journal of Combinatorial Theory, Series B
988:
793:
679:
291:, the neighbourhood of any vertex is a 4-
1024:
782:
282:
31:
888:
836:
810:Larrión, Neumann-Lara & Pizaña 2002
14:
1115:
453:-chromatic graph has chromatic number
864:
848:
567:are exactly the underlying graphs of
185:itself, and is more specifically the
951:
778:
619:are the graphs that are locally co-
560:. Locally cyclic graphs other than
520:is locally (k)-(ultra)-homogeneous.
148:or (when the graph is unambiguous)
108:The neighbourhood is often denoted
24:
688:of vertices, the neighbourhood of
25:
1134:
623:; that is, for all vertices, the
66:is a vertex that is connected to
921:(1991), "Clean triangulations",
755:, a related concept in polyhedra
631:is claw-free if and only if the
542:is the unique connected locally
531:is the unique connected locally
482:{\displaystyle O({\sqrt {kn}})}
197:itself is included, called the
799:
772:
598:
592:
476:
463:
267:has no adjacent vertices. The
226:
220:
166:
160:
133:
127:
13:
1:
990:10.1016/S0012-365X(02)00266-2
885:; see in particular pp. 89–90
858:
518:(k)-(ultra)-homogeneous graph
516:is locally comparable; every
449:-1)-chromatic. Every locally
430:if and only if it is locally
303:have neighbourhoods that are
1018:10.1016/0095-8956(92)90015-P
653:has independence number two.
93:by all vertices adjacent to
7:
806:Hartsfeld & Ringel 1991
748:Second neighborhood problem
726:
42:Neighbourhood (mathematics)
18:Neighborhood (graph theory)
10:
1139:
606:{\displaystyle n^{2-o(1)}}
512:is locally perfect; every
508:is locally chordal; every
279:Local properties in graphs
39:
759:Link (simplicial complex)
743:Von Neumann neighbourhood
319:, and if all vertices in
969:; Pizaña, M. A. (2002),
865:Cohen, Arjeh M. (1990),
765:
139:{\displaystyle N_{G}(v)}
825:Seress & Szabó 1995
814:Malnič & Mohar 1992
553:of order 13 is locally
335:. For instance, in the
1069:10.1006/jctb.1995.1020
680:Neighbourhood of a set
607:
569:Whitney triangulations
504:. For instance, every
483:
296:
254:clustering coefficient
233:
173:
140:
37:
713:modular decomposition
658:locally linear graphs
608:
484:
286:
234:
232:{\displaystyle N_{G}}
174:
141:
35:
1123:Graph theory objects
998:Malnič, Aleksander;
976:Discrete Mathematics
721:comparability graphs
575:
527:. For instance, the
457:
207:
199:closed neighbourhood
172:{\displaystyle N(v)}
154:
114:
1027:Graph Theory, Lagów
891:Mathematica Slovaca
738:Moore neighbourhood
633:independence number
514:comparability graph
299:If all vertices in
86:is the subgraph of
1083:Journal of the ACM
1035:10.1007/BFb0071634
937:10.1007/BF01206358
903:10338.dmlcz/136481
603:
492:If a graph family
479:
445:graph is locally (
307:to the same graph
297:
229:
187:open neighbourhood
169:
136:
38:
1097:10.1145/2157.2158
1044:978-3-540-12687-4
917:Hartsfeld, Nora;
474:
16:(Redirected from
1130:
1108:
1099:
1072:
1071:
1047:
1020:
993:
992:
983:(1–3): 123–135,
967:Neumann-Lara, V.
960:
947:
913:
884:
871:
852:
846:
840:
834:
828:
822:
816:
803:
797:
791:
785:
776:
662:induced matching
625:complement graph
617:Claw-free graphs
612:
610:
609:
604:
602:
601:
500:is also locally
488:
486:
485:
480:
475:
467:
337:octahedron graph
289:octahedron graph
250:adjacency matrix
240:
238:
236:
235:
230:
219:
218:
196:
192:
184:
180:
178:
176:
175:
170:
147:
145:
143:
142:
137:
126:
125:
104:
100:
96:
89:
85:
81:
69:
61:
21:
1138:
1137:
1133:
1132:
1131:
1129:
1128:
1127:
1113:
1112:
1045:
919:Ringel, Gerhard
869:
861:
856:
855:
847:
843:
835:
831:
823:
819:
804:
800:
792:
788:
777:
773:
768:
729:
682:
652:
645:
582:
578:
576:
573:
572:
566:
559:
549:graph, and the
548:
537:
466:
458:
455:
454:
377:
368:
349:
281:
265:isolated vertex
214:
210:
208:
205:
204:
202:
201:and denoted by
194:
190:
182:
155:
152:
151:
149:
121:
117:
115:
112:
111:
109:
102:
98:
94:
87:
83:
79:
67:
59:
53:adjacent vertex
45:
28:
23:
22:
15:
12:
11:
5:
1136:
1126:
1125:
1111:
1110:
1090:(4): 729–735,
1078:Wigderson, Avi
1074:
1062:(2): 281–293,
1049:
1043:
1022:
1012:(2): 147–164,
995:
962:
949:
931:(2): 145–155,
914:
886:
860:
857:
854:
853:
841:
829:
817:
798:
794:Wigderson 1983
786:
770:
769:
767:
764:
763:
762:
756:
750:
745:
740:
735:
733:Markov blanket
728:
725:
681:
678:
677:
676:
669:Johnson graphs
665:
654:
650:
643:
614:
600:
597:
594:
591:
588:
585:
581:
564:
557:
546:
535:
521:
490:
478:
473:
470:
465:
462:
435:
424:
413:
379:
373:
364:
359:complete graph
347:
331:is said to be
315:is said to be
280:
277:
246:adjacency list
228:
225:
222:
217:
213:
168:
165:
162:
159:
135:
132:
129:
124:
120:
26:
9:
6:
4:
3:
2:
1135:
1124:
1121:
1120:
1118:
1107:
1103:
1098:
1093:
1089:
1085:
1084:
1079:
1075:
1070:
1065:
1061:
1057:
1056:
1050:
1046:
1040:
1036:
1032:
1028:
1023:
1019:
1015:
1011:
1007:
1006:
1001:
996:
991:
986:
982:
978:
977:
972:
968:
965:Larrión, F.;
963:
958:
954:
950:
946:
942:
938:
934:
930:
926:
925:
924:Combinatorica
920:
915:
912:
908:
904:
900:
896:
892:
887:
883:
879:
875:
868:
863:
862:
850:
845:
838:
833:
826:
821:
815:
811:
807:
802:
795:
790:
784:
783:Sedláček 1983
780:
775:
771:
760:
757:
754:
753:Vertex figure
751:
749:
746:
744:
741:
739:
736:
734:
731:
730:
724:
722:
718:
714:
710:
706:
702:
697:
695:
691:
687:
674:
670:
666:
663:
659:
655:
649:
642:
638:
634:
630:
626:
622:
621:triangle-free
618:
615:
595:
589:
586:
583:
579:
570:
563:
556:
552:
545:
541:
534:
530:
526:
522:
519:
515:
511:
510:perfect graph
507:
506:chordal graph
503:
499:
495:
491:
471:
468:
460:
452:
448:
444:
440:
436:
433:
429:
428:triangle-free
425:
422:
418:
414:
411:
407:
403:
399:
396:) is locally
395:
391:
387:
384:
380:
376:
372:
367:
363:
360:
356:
355:
354:
353:For example:
351:
346:
342:
338:
334:
330:
326:
322:
318:
314:
310:
306:
302:
294:
290:
285:
276:
274:
270:
266:
261:
259:
255:
251:
247:
242:
223:
215:
211:
200:
188:
163:
157:
130:
122:
118:
106:
92:
77:
76:neighbourhood
73:
65:
58:
54:
50:
43:
34:
30:
19:
1087:
1081:
1059:
1053:
1026:
1009:
1003:
1000:Mohar, Bojan
980:
974:
956:
928:
922:
894:
890:
873:
844:
837:Fronček 1989
832:
820:
801:
789:
774:
708:
704:
700:
698:
693:
689:
685:
683:
673:rook's graph
647:
640:
636:
628:
561:
554:
543:
532:
501:
497:
493:
450:
446:
438:
417:planar graph
409:
405:
401:
397:
393:
389:
385:
374:
370:
365:
361:
352:
344:
332:
328:
324:
320:
316:
312:
308:
300:
298:
262:
243:
198:
186:
107:
78:of a vertex
75:
52:
49:graph theory
46:
29:
953:Hell, Pavol
717:linear time
551:Paley graph
540:icosahedron
538:graph, the
432:independent
426:A graph is
421:outerplanar
419:is locally
383:Turán graph
369:is locally
82:in a graph
897:(1): 3–6,
859:References
849:Cohen 1990
684:For a set
529:octahedron
305:isomorphic
779:Hell 1978
587:−
443:chromatic
333:locally F
317:locally H
1117:Category
1106:32214512
945:28144260
727:See also
911:1016323
882:1072157
287:In the
258:density
239:
203:
179:
150:
146:
110:
91:induced
1104:
1041:
943:
909:
880:
699:A set
613:edges.
437:Every
415:Every
269:degree
74:. The
70:by an
57:vertex
1102:S2CID
941:S2CID
870:(PDF)
766:Notes
525:cycle
341:cycle
293:cycle
64:graph
62:in a
55:of a
51:, an
1039:ISBN
667:The
656:The
646:and
357:Any
273:loop
248:and
72:edge
1092:doi
1064:doi
1031:doi
1014:doi
985:doi
981:258
933:doi
899:hdl
635:of
404:-1)
375:n-1
263:An
189:of
47:In
1119::
1100:,
1088:30
1086:,
1060:63
1058:,
1037:,
1010:56
1008:,
979:,
973:,
939:,
929:11
927:,
907:MR
905:,
895:39
893:,
878:MR
812:;
808:;
781:,
723:.
696:.
400:((
390:rs
381:A
350:.
327:,
311:,
105:.
1109:.
1094::
1073:.
1066::
1048:.
1033::
1021:.
1016::
994:.
987::
961:.
948:.
935::
901::
851:.
839:.
827:.
796:.
709:A
705:A
701:A
694:A
690:A
686:A
675:.
664:.
651:5
648:C
644:5
641:C
637:H
629:H
599:)
596:1
593:(
590:o
584:2
580:n
565:4
562:K
558:6
555:C
547:5
544:C
536:4
533:C
502:F
498:F
494:F
489:.
477:)
472:n
469:k
464:(
461:O
451:k
447:k
441:-
439:k
434:.
410:r
408:,
406:s
402:r
398:T
394:r
392:,
388:(
386:T
371:K
366:n
362:K
348:4
345:C
329:G
325:F
321:G
313:G
309:H
301:G
295:.
227:]
224:v
221:[
216:G
212:N
195:v
191:v
183:v
167:)
164:v
161:(
158:N
134:)
131:v
128:(
123:G
119:N
103:v
99:v
95:v
88:G
84:G
80:v
68:v
60:v
44:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
