TOPICS
Search

Local Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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.

local graph Ggraphs containing G
2C_637-cyclotomic graph
2C_3generalized hexagon GH(3,1), generalized octagon GO(3,1), (4,4)-rook graph
3C_3(3,4)-Hamming graph
4C_3(4,4)-Hamming graph
cycle graph C_5icosahedral graph
cycle graph C_6Shrikhande graph, circulant graph Ci_(12)(1,2,5), Ci_(14)(1,2,6), Ci_(14)(1,3,4), Ci_(15)(1,3,4), 19-cyclotomic graph, 13-Paley graph
cycle graph C_7Klein graph
cubical graph24-cell graph, circulant graph Ci_(15)(1,2,4,7)
generalized quadrangle GQ(2,1)(4,4)-rook graph complement, 6-tetrahedral Johnson graph
generalized quadrangle GQ(2,2)(8,2)-Kneser graph
5-halved cube graphSchläfli graph
icosahedral graph600-cell graph
4-Möbius ladder17-Paley graph
7-Möbius ladder43-cyclotomic graph
octahedral graph16-cell graph
Petersen graphConway-Smith graph, Hall graph, (7,2)-Kneser graph
prism graph Y_35-triangular graph
prism graph Y_531-cyclotomic graph
quartic vertex-transitive graph Qt31U_3(3) graph
Schläfli graphGosset graph
square graph C_4octahedral graph
tetrahedral graphpentatope graph
triangle graph C_3tetrahedral graph
n-triangular graphn-halved cube graph
U_3(3) graphHall-Janko graph
utility graphcomplete tripartite graph K_(3,3,3)

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