Local Graph

A graph  is said to be locally , where  is a graph (or class of graphs), when for every vertex , the graph induced on  by the set of adjacent vertices of  (sometimes called the ego graph in more recent literature) is isomorphic to (or to a member of) . 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  on which a subgraph is induced, while the definitions of graph neighborhood and neighborhood graph include  itself.

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

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

graph	local graph
24-cell graph	cubical graph
cocktail party graph	16-cell graph
cocktail party graph	cocktail party graph
complete graph	complete graph
complete -partite graph	complete -partite graph
Conway-Smith graph	Petersen graph
19-cyclotomic graph	cycle graph
31-cyclotomic graph	prism graph
37-cyclotomic graph
43-cyclotomic graph	7-Möbius ladder graph
64-cyclotomic graph	(3,7)-rook graph
generalized hexagon	circulant graph
generalized octagon
Gosset graph	Schläfli graph
Hall graph	Petersen graph
Hall-Janko graph	graph
-halved cube graph	-triangular graph
-Hamming graph	circulant graph
line graph of the Hoffman-Singleton graph	circulant graph
icosahedral graph	cycle graph
(8,4)-Johnson graph	(4,4)-rook graph
(9,4)-Johnson graph	(4,5)-rook graph
Klein graph	cycle graph
(7,2)-Kneser graph	Petersen graph
(8,2)-Kneser graph	generalized quadrangle GQ(2,2)
-Kneser graph	-Kneser graph
(10,3)-Kneser graph	odd graph
-rook graph	circulant graph
(4,4)-rook graph complement	generalized quadrangle GQ(2,1)
octahedral graph	square graph
13-Paley graph	cycle graph
17-Paley graph	4-Möbius ladder
25-Paley graph	circulant graph
29-Paley graph	circulant graph
pentatope graph	tetrahedral graph
Schläfli graph	5-halved cube graph
Shrikhande graph	cycle graph
600-cell graph	icosahedral graph
16-cell graph	octahedral graph
6-tetrahedral graph	generalized quadrangle GQ(2,1)
7-tetrahedral graph	circulant graph
8-tetrahedral graph	circulant graph
9-tetrahedral graph	(3,6)-rook graph
10-tetrahedral graph	(3,7)-rook graph
tetrahedral graph	triangle graph
5-triangular graph	prism graph
-triangular graph	-rook graph
graph	quartic vertex-transitive graph Qt31

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

local graph	graphs containing
	37-cyclotomic graph
	generalized hexagon GH(3,1), generalized octagon GO(3,1), (4,4)-rook graph
	(3,4)-Hamming graph
	(4,4)-Hamming graph
cycle graph	icosahedral graph
cycle graph	Shrikhande graph, circulant graph , , , , 19-cyclotomic graph, 13-Paley graph
cycle graph	Klein graph
cubical graph	24-cell graph, circulant graph
generalized quadrangle GQ(2,1)	(4,4)-rook graph complement, 6-tetrahedral graph
generalized quadrangle GQ(2,2)	(8,2)-Kneser graph
5-halved cube graph	Schläfli graph
icosahedral graph	600-cell graph
4-Möbius ladder	17-Paley graph
7-Möbius ladder	43-cyclotomic graph
octahedral graph	16-cell graph
Petersen graph	Conway-Smith graph, Hall graph, (7,2)-Kneser graph
prism graph	5-triangular graph
prism graph	31-cyclotomic graph
quartic vertex-transitive graph Qt31	graph
Schläfli graph	Gosset graph
square graph	octahedral graph
tetrahedral graph	pentatope graph
triangle graph	tetrahedral graph
-triangular graph	-halved cube graph
graph	Hall-Janko graph
utility graph	complete tripartite graph

REFERENCES

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