On local properties of graphs again. (English) Zbl 0697.05024

Sedláček, Jiří

Čas. Pěstování Mat. 114, No. 4, 381-390 (1989).

Summary: In our earlier papers we considered two types of vertex neighborhood but in this paper we deal mostly with the first one. Let v be a vertex of a graph G. By \(N_ 1(v)\), the neighborhood of the first type, we mean the subgraph of G induced on the set of all vertices adjacent to v.
Let \({\mathcal C}_ 1\) be the class of all graphs G of order at least two with the property that for any two vertices of G, say u and v, we have \(N_ 1(u)\not\simeq N_ 1(v)\). First we show that for a given positive integer m there exists a positive integer \(\rho\) (m) such that for every graph \(G^{(m)}\) of order m there is a graph G of order \(\rho\) (m) with \(G\in {\mathcal C}_ 1\) and a vertex w of G with \(N_ 1(w)\cong G^{(m)}.\)
Further one can easily verify that for every integer \(n\geq 7\) there exists a locally connected graph of order n belonging to \({\mathcal C}_ 1\). It is known that the number of planar graphs belonging to \({\mathcal C}_ 1\) is finite. In the present paper we prove that there are exactly four outerplanar graphs in the class \({\mathcal C}_ 1\) (see Fig. 3). In [Čas. Pěstování Mat. 113, No.2, 213-218 (1988; Zbl 0649.05028)], we defined a generalized outerplanar graph as a planar graph which can be embedded in the plane in such a way that at least one endvertex of each edge lies on the boundary of the same face. Next result of this paper states that if G is an outerplanar graph of order at least seven then \(\bar G\) is not a generalized outerplanar graph. This statement strengthens Theorem 11.12 in [F. Harary, Graph Theory (1969; Zbl 0182.577)]. The generalized outerplanarity also allows us to interpose the following statement between Theorem 11.11 and Theorem 11.12 in Harary’s book: Every generalized outerplanar graph with at least eight vertices has a nonplanar complement, and eight is the smallest such number. The final section of this paper shows how to use the so-called Ford circles to construct an infinite graph with the property that all vertex neighborhoods are isomorphic with a two-way infinite path.

MSC:

05C10

Planar graphs; geometric and topological aspects of graph theory

Keywords:

planarity; outerplanarity; Ford circles; vertex neighborhood; generalized outerplanar graph

Citations:

Zbl 0649.05028; Zbl 0182.577