No label defined (Q3972103)

[For the entire collection see Zbl 0699.00015.] Let \(F\) be a family of isomorphism classes of graphs. A graph \(G\) is said to be an \(F\)-graph if for any vertex \(v\) the \(\text{Link}(v)\) (we sometimes use \(G[N(v)])\) belongs to \(F\). Let \(PC\) denote the family of all paths and all cycles, \(P_ k\) (resp. \(C_ k)\) the path (resp. cycle) of \(k\) vertices and \(B_ k\) the set of all connected circulant graphs that are locally \(P_ k\)-graphs. Then it is proved that the circulant graph \(G(n,S)\) on \(n\) vertices with symbol \(S\) belongs to \(B_ k\) if and only if one of the following condition holds: (a) \(n=2\), \(k=1\), \(S=\{1\}\) and \(G(n,S)=K_ 2[\text{Link}=P_ 1]\). (b) \(n=3\), \(k=2\), \(S=\{-1,1\}\) and \(G(n,S)=K_ 3[\text{Link}=P_ 2]\). (c) \(n\geq 7\), \(k=4\), \(S=a\{-1,1,-2,2\}\) for some \(a\) from \(Z*_ n\), the group of units of the ring \(Z_ n[\text{Link}=P_ 4]\). It is also shown that the only connected \(P_ k\)-graphs, \(k\leq 4\), are the ones given above. Some topological characterization of the \(PC\)-graphs is given. The Euler formula for each \(PC\)-graph \(G\) is \[ \sum(k-6)c_ k+\sum(k-4)p_ k=6(d- \chi)\quad\text{and } p\geq 4d, \] where \(p_ k\) (resp. \(c_ k)\) is the number of vertices \(v\) such that \(\text{Link}(v)=P_ k\) (resp. \(C_ k)\), \(p=\sum_{k\geq 2}p_ k\), \(d\) is the number of boundary cycles in \(\alpha G\) and \(\chi\) is the corresponding Euler characteristic of the surface \(S'\) which is obtained from the surface \(S\) determined by \(K(G)\) by ``filling in the \(d\) holes''.