The neighborhood characteristic parameter for graphs
Summary: Define the neighborhood characteristic of a graph to be \(s_1 - s_2+ s_3 - \cdots\), where \(s_i\) counts subsets of \(i\) vertices that are all adjacent to some vertex outside the subset. This amounts to replacing cliques by neighborhoods in the traditional `Euler characteristic' (the number of vertices, minus the number of edges, plus the number of triangles, etc.). The neighborhood characteristic can also be calculated by knowing, for all \(i,j \geq 2\), how many \(K_{i,j}\) subgraphs there are or, through an Euler-Poincare-type theorem, by knowing how those subgraphs are arranged. Chordal bipartite graphs are precisely the graphs for which every nontrivial connected induced subgraph has neighborhood characteristic \(2\).
- Some parameters on neighborhood number of A graph
- Graph parameters measuring neighbourhoods in graphs-bounds and applications
- scientific article; zbMATH DE number 4093511
- Publication:4351073
- The neighbourhood number of a graph
- The \(\gamma\)-neighborhood graph
- scientific article; zbMATH DE number 4103126
- scientific article; zbMATH DE number 409491
- The neighbourhood polynomial of a graph
- On the neighbourhood polynomial of graphs
- Clique neighborhoods and nearly chordal graphs
- Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
- Maxclique and unit disk characterizations of strongly chordal graphs
- Some parameters on neighborhood number of A graph
- scientific article; zbMATH DE number 1052833 (Why is no real title available?)
This page was built for publication: The neighborhood characteristic parameter for graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1408522)
