TOPICS
Search

Local Graph


A graph G is said to be locally X, where X is a graph (or class of graphs), when for every vertex v, the graph induced on G by the set of adjacent vertices of v (i.e. the vertex-induced subgraph; sometimes called the ego graph in more recent literature) is isomorphic to (or to a member of) X. Note that the term "neighbors" is sometimes used instead of "adjacent vertices" here (e.g., Brouwer et al. 1989), so care is needed since the definition of local graphs excludes the vertex v on which a subgraph is induced, while the definitions of graph neighborhood and neighborhood graph include v itself.

LocallyPentagonalGraph

For example, the only locally pentagonal (cycle graph C_5) graph is the icosahedral graph (Brouwer et al. 1989, p. 5).

The following table summarizes some named graphs that have named local graphs.

graphlocal graph
24-cell graphcubical graph
cocktail party graph K_(5×2)16-cell graph
cocktail party graph K_(n×2)cocktail party graph K_((n-1)×2)
complete graph K_ncomplete graph K_(n-1)
complete k-partite graph K_(n,...,n_()_(k))complete (k-1)-partite graph K_(n,...,n_()_(k-1))
Conway-Smith graphPetersen graph
19-cyclotomic graphcycle graph C_6
31-cyclotomic graphprism graph Y_5
37-cyclotomic graph2C_6
43-cyclotomic graph7-Möbius ladder graph
64-cyclotomic graph(3,7)-rook graph
generalized hexagon GH(n,1)circulant graph Ci_(2n)(2,4)
generalized octagon GO(3,1)2C_3
Gosset graphSchläfli graph
Hall graphPetersen graph
Hall-Janko graphU_3(3) graph
n-halved cube graphn-triangular graph
(3,n)-Hamming graphcirculant graph Ci_(3(n-1))(3,6)
line graph of the Hoffman-Singleton graphcirculant graph Ci_(12)(2,4,6)
icosahedral graphcycle graph C_5
(8,4)-Johnson graph(4,4)-rook graph
(9,4)-Johnson graph(4,5)-rook graph
Klein graphcycle graph C_7
(7,2)-Kneser graphPetersen graph
(8,2)-Kneser graphgeneralized quadrangle GQ(2,2)
(n,2)-Kneser graph(n-2,2)-Kneser graph
(10,3)-Kneser graphodd graph O_4
(n,n)-rook graphcirculant graph Ci_(2n-2)(2,4,...,n-1)
(4,4)-rook graph complementgeneralized quadrangle GQ(2,1)
octahedral graphsquare graph
13-Paley graphcycle graph C_6
17-Paley graph4-Möbius ladder
25-Paley graphcirculant graph Ci_(12)(2,3,6)
29-Paley graphcirculant graph Ci_(14)(1,2,6)
pentatope graphtetrahedral graph
Schläfli graph5-halved cube graph
Shrikhande graphcycle graph C_6
600-cell graphicosahedral graph
16-cell graphoctahedral graph
6-tetrahedral Johnson graphgeneralized quadrangle GQ(2,1)
7-tetrahedral Johnson graphcirculant graph Ci_(12)(3,4,6)
8-tetrahedral Johnson graphcirculant graph Ci_(15)(3,5,6)
9-tetrahedral Johnson graph(3,6)-rook graph
10-tetrahedral Johnson graph(3,7)-rook graph
tetrahedral graphtriangle graph
5-triangular graphprism graph Y_3
n-triangular graph(2,n-2)-rook graph
U_3(3) graphquartic vertex-transitive graph Qt31

The following table gives a list of some local graphs and graphs in which they are contained.


See also

Distance k-Graph, Graph Neighborhood, Local McLaughlin Graph, Locally Petersen Graph, M22 Graph, Suzuki Tower, Vertex-Induced Subgraph

Explore with Wolfram|Alpha

References

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, pp. 4-5, 256, and 434, 1989.

Referenced on Wolfram|Alpha

Local Graph

Cite this as:

Weisstein, Eric W. "Local Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LocalGraph.html

Subject classifications