local invariants

Local Invariants

graphcalc.graphs.invariants.local_invariants.local_annihilation_number(G)

Compute the local annihilation number of a graph \(G\) (with respect to open neighborhoods).

Let \(a(H)\) denote the annihilation number of a graph \(H\) (as implemented by graphcalc.annihilation_number()). The local annihilation number is the maximum annihilation number attained by an open-neighborhood induced subgraph:

\[a_{\mathrm{loc}}(G) \;=\; \max_{v \in V(G)} a\!\bigl(G[N(v)]\bigr),\]

where \(N(v)\) is the open neighborhood of \(v\) and \(G[N(v)]\) is the subgraph induced by \(N(v)\).

Parameters:

G (networkx.Graph-like) – A finite graph. Neighborhoods are computed via G.neighbors(v), so this is primarily intended for undirected graphs. For directed graphs, NetworkX interprets neighbors as successors, yielding an out-neighborhood variant.

Returns:

The local annihilation number \(a_{\mathrm{loc}}(G)\). If \(G\) has no vertices, returns 0.

Return type:

int

Notes

• If \(v\) is isolated, then \(N(v)=\varnothing\) and \(G[N(v)]\) is the empty graph. The value contributed by such a vertex is \(a(\varnothing)\) under the convention used by graphcalc.annihilation_number() on the empty graph. (This only matters when \(G\) has isolated vertices.)

• This function is a “local” refinement: it measures how large the annihilation number can be inside a vertex neighborhood, rather than on \(G\) itself.

• Implementation: this is a thin wrapper around local_parameter() with gc.annihilation_number, neighborhood="open", and agg="max".

Complexity

Runtime is dominated by computing graphcalc.annihilation_number() on each neighborhood-induced subgraph.

Examples

Complete graphs: \(N(v)\) induces \(K_{n-1}\).

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> K6 = nx.complete_graph(6)
>>> gc.local_annihilation_number(K6) == gc.annihilation_number(nx.complete_graph(5))
True

Bipartite graphs: each open neighborhood induces an independent set (no edges), so each neighborhood subgraph is edgeless.

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> P6 = nx.path_graph(6)
>>> gc.local_annihilation_number(P6) == gc.annihilation_number(nx.empty_graph(2))
True

graphcalc.graphs.invariants.local_invariants.local_chromatic_number(G)

Compute the local chromatic number of a graph \(G\) (with respect to open neighborhoods).

This parameter is defined by taking, over all vertices \(v\), the chromatic number of the subgraph induced by the open neighborhood \(N(v)\) and then maximizing:

\[\chi_{\mathrm{loc}}(G) \;=\; \max_{v \in V(G)} \chi\!\bigl(G[N(v)]\bigr),\]

where \(N(v)\) is the open neighborhood of \(v\), \(G[N(v)]\) denotes the induced subgraph on \(N(v)\), and \(\chi(H)\) is the chromatic number of \(H\) (the minimum number of colors in a proper vertex coloring of \(H\)).

Parameters:

G (networkx.Graph-like) – A finite graph. Neighborhoods are computed via G.neighbors(v), so this is primarily intended for undirected graphs under the standard adjacency notion. For directed graphs, NetworkX interprets neighbors as successors, which yields an out-neighborhood variant.

Returns:

The value \(\chi_{\mathrm{loc}}(G)\). If \(G\) has no vertices, returns 0.

Return type:

int

Notes

• Empty/isolated-neighborhood convention: if \(v\) is isolated, then \(N(v)=\varnothing\) and \(G[N(v)]\) is the empty graph. Many conventions set \(\chi(\varnothing)=0\), while some implementations return 1. This function uses whatever convention is implemented by gc.chromatic_number when applied to the empty graph. This only affects the value when \(G\) has isolated vertices.

• This is a local refinement of coloring complexity: it measures the strongest coloring requirement among neighborhood-induced subgraphs, rather than coloring \(G\) itself. In general, \(\chi_{\mathrm{loc}}(G)\) need not equal \(\chi(G)\).

Complexity

This function delegates to local_parameter() with gc.chromatic_number. The runtime is therefore dominated by the cost of computing the chromatic number on each neighborhood-induced subgraph. Exact chromatic number routines are typically exponential in neighborhood size.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # Complete graph: each neighborhood is complete, so chi_loc(K_n) = n-1.
>>> K6 = nx.complete_graph(6)
>>> gc.local_chromatic_number(K6)
5

>>> # Bipartite graphs have neighborhoods inducing independent sets, so chi_loc is at most 1
>>> # (or 0 on isolated neighborhoods depending on the empty-graph convention).
>>> P6 = nx.path_graph(6)
>>> gc.local_chromatic_number(P6)
1

graphcalc.graphs.invariants.local_invariants.local_clique_number(G)

Compute the local clique number of a graph \(G\) (with respect to open neighborhoods).

The local clique number is defined as the maximum clique number attained by an induced open neighborhood:

\[\omega_{\mathrm{loc}}(G) \;=\; \max_{v \in V(G)} \omega\!\bigl(G[N(v)]\bigr),\]

where \(N(v)\) is the open neighborhood of \(v\) (the set of neighbors of \(v\)), \(G[N(v)]\) is the subgraph induced by \(N(v)\), and \(\omega(H)\) denotes the clique number of \(H\) (the size of a largest complete subgraph of \(H\)).

Parameters:

G (networkx.Graph-like) – A finite graph. Neighborhoods are computed via G.neighbors(v), so this is primarily intended for undirected graphs under the standard adjacency notion. For directed graphs, NetworkX interprets neighbors as successors, which yields an out-neighborhood variant.

Returns:

The value \(\omega_{\mathrm{loc}}(G)\). If \(G\) has no vertices, returns 0.

Return type:

int

Notes

• If \(v\) is isolated, then \(N(v)=\varnothing\) and \(G[N(v)]\) is empty, so \(\omega(G[N(v)]) = 0\). Thus isolated vertices do not increase the maximum.

• \(\omega(G[N(v)])\) measures how “clique-like” the neighborhood of \(v\) is. In particular, it equals the maximum number of neighbors of \(v\) that are pairwise adjacent.

• For a complete graph \(K_n\) (n ≥ 2), every open neighborhood induces \(K_{n-1}\), so \(\omega_{\mathrm{loc}}(K_n)=n-1\).

• For a bipartite graph, every open neighborhood induces an independent set, so \(\omega_{\mathrm{loc}}(G) \le 1\) (and equals 1 whenever there is an edge).

Complexity

This function delegates to local_parameter() with gc.clique_number. The runtime is therefore dominated by the cost of computing the clique number on each neighborhood-induced subgraph. Exact clique number routines are typically exponential in neighborhood size.

Examples

>>> import networkx as nx
>>> # In a star, each leaf has neighborhood {center} (clique number 1),
>>> # and the center has neighborhood consisting of independent leaves (clique number 1).
>>> G = nx.star_graph(5)
>>> gc.local_clique_number(G)
1

>>> # In a complete graph, neighborhoods are complete.
>>> H = nx.complete_graph(6)
>>> gc.local_clique_number(H)
5

>>> # In a triangle, each vertex's neighborhood is an edge (clique number 2).
>>> T = nx.complete_graph(3)
>>> gc.local_clique_number(T)
2

graphcalc.graphs.invariants.local_invariants.local_domination_number(G)

Compute the local domination number of a graph \(G\) (with respect to open neighborhoods).

The local domination number is defined as the maximum domination number attained by an induced open neighborhood:

\[\gamma_{\mathrm{loc}}(G) \;=\; \max_{v \in V(G)} \gamma\!\bigl(G[N(v)]\bigr),\]

where \(N(v)\) is the open neighborhood of \(v\) (the set of neighbors of \(v\)), \(G[N(v)]\) is the subgraph induced by \(N(v)\), and \(\gamma(H)\) denotes the domination number of a graph \(H\).

Recall that the domination number \(\gamma(H)\) is

\[\gamma(H) \;=\; \min\{\, |D| : D \subseteq V(H)\ \text{and}\ N_H[D] = V(H) \,\},\]

i.e., the minimum size of a vertex set \(D\) such that every vertex of \(H\) lies in \(D\) or has a neighbor in \(D\) (here \(N_H[D]\) denotes the closed neighborhood of \(D\) in \(H\)).

Parameters:

G (networkx.Graph-like) – A finite graph. Neighborhoods are computed via G.neighbors(v), so this is primarily intended for undirected graphs under the standard adjacency notion. For directed graphs, NetworkX interprets neighbors as successors, which yields an out-neighborhood variant.

Returns:

The value \(\gamma_{\mathrm{loc}}(G)\). If \(G\) has no vertices, returns 0.

Return type:

int

Notes

• If \(v\) is isolated, then \(N(v)=\varnothing\) and \(G[N(v)]\) is the empty graph. Under the standard convention used by most domination-number implementations, the empty graph has domination number 0, so isolated vertices do not increase the maximum.

• This is a local parameter: it measures how “difficult” it is to dominate each open-neighborhood subgraph, rather than dominating \(G\) itself. In general, \(\gamma_{\mathrm{loc}}(G)\) is not equal to \(\gamma(G)\).

Complexity

This function delegates to local_parameter() with gc.domination_number. The runtime is therefore dominated by the cost of computing the domination number on each neighborhood-induced subgraph. Exact domination number routines are typically exponential in neighborhood size.

Examples

>>> import networkx as nx
>>> # In a star, the center's neighborhood is an independent set of size n-1,
>>> # whose domination number equals n-1 (each isolated vertex must be chosen).
>>> G = nx.star_graph(5)
>>> gc.local_domination_number(G)
5

>>> # In a complete graph, each neighborhood is complete, so domination number is 1.
>>> H = nx.complete_graph(6)
>>> gc.local_domination_number(H)
1

graphcalc.graphs.invariants.local_invariants.local_harmonic_index(G)

Compute the local harmonic index of a graph \(G\) (with respect to open neighborhoods).

This parameter is defined by applying the harmonic index to each induced open neighborhood subgraph and taking the maximum:

\[H_{\mathrm{loc}}(G) \;=\; \max_{v \in V(G)} H\!\bigl(G[N(v)]\bigr),\]

where \(N(v)\) is the open neighborhood of \(v\), \(G[N(v)]\) is the subgraph induced by \(N(v)\), and \(H(\cdot)\) denotes the harmonic index as implemented by graphcalc.harmonic_index() (here referenced as gc.harmonic_index).

Parameters:

G (networkx.Graph-like) – A finite graph. Neighborhoods are computed via G.neighbors(v), so this is primarily intended for undirected graphs under the standard adjacency notion. For directed graphs, NetworkX interprets neighbors as successors, which yields an out-neighborhood variant.

Returns:

The value \(H_{\mathrm{loc}}(G)\). If \(G\) has no vertices, returns 0.

Return type:

number

Notes

• A widely used definition of the (edge-based) harmonic index of a simple undirected graph \(H\) is

  \[H(H) \;=\; \sum_{xy \in E(H)} \frac{2}{\deg_H(x) + \deg_H(y)}.\]

  This function uses the exact convention implemented by gc.harmonic_index; the above formula is included for orientation.

• If \(v\) is isolated, then \(N(v)=\varnothing\) and \(G[N(v)]\) is the empty graph. Under the standard edge-sum convention, the harmonic index of an edgeless graph is 0 (empty sum), so isolated vertices do not increase the maximum.

• This is a local refinement: it measures harmonic index on neighborhood-induced subgraphs rather than on \(G\) itself.

Complexity

This function delegates to local_parameter() with gc.harmonic_index. The runtime is dominated by the cost of evaluating gc.harmonic_index on each neighborhood-induced subgraph.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(6)
>>> local_harmonic_index(G)
...  # depends on gc.harmonic_index implementation details

graphcalc.graphs.invariants.local_invariants.local_independence_number(G)

Compute the local independence number of a graph \(G\) (with respect to open neighborhoods).

The local independence number is defined as the maximum independence number attained by the induced subgraph on an open neighborhood:

\[\alpha_{\mathrm{loc}}(G) \;=\; \max_{v \in V(G)} \alpha\!\bigl(G[N(v)]\bigr),\]

where \(N(v)\) is the open neighborhood of \(v\) (the set of neighbors of \(v\)), \(G[N(v)]\) is the induced subgraph on \(N(v)\), and \(\alpha(H)\) denotes the independence number of a graph \(H\).

Parameters:

G (networkx.Graph-like) – A finite graph. Neighborhoods are taken using G.neighbors(v), so this is primarily intended for undirected graphs with the standard adjacency notion. For directed graphs, NetworkX interprets neighbors as successors, which yields an out-neighborhood variant.

Returns:

The value \(\alpha_{\mathrm{loc}}(G)\). If \(G\) has no vertices, returns 0.

Return type:

int

Notes

• If \(v\) is isolated, then \(N(v)=\varnothing\) and \(G[N(v)]\) is the empty graph, so \(\alpha(G[N(v)]) = 0\). Thus isolated vertices do not increase the maximum.

• This is a neighborhood-based refinement of the global independence number. In general, \(\alpha_{\mathrm{loc}}(G)\) need not equal \(\alpha(G)\) and may be smaller or larger (e.g., in graphs with a high-degree vertex whose neighborhood is sparse).

• For a complete graph \(K_n\) (n ≥ 2), every open neighborhood induces \(K_{n-1}\), so \(\alpha_{\mathrm{loc}}(K_n)=1\).

Complexity

This function delegates to local_parameter() with gc.independence_number. The runtime is therefore dominated by the cost of computing the independence number on each neighborhood-induced subgraph. For exact independence number routines, this may be exponential in the neighborhood sizes.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # In a star, the center's neighborhood is an independent set of size n-1.
>>> G = nx.star_graph(5)  # 6 vertices total: center + 5 leaves
>>> gc.local_independence_number(G)
5

>>> # In a complete graph, every neighborhood is a clique.
>>> H = nx.complete_graph(6)
>>> gc.local_independence_number(H)
1

graphcalc.graphs.invariants.local_invariants.local_parameter(G, f, *, neighborhood='open', agg='max')

Apply a graph parameter locally to neighborhood-induced subgraphs and aggregate the results.

For each vertex \(v \in V(G)\), this operator forms the induced subgraph on either the open neighborhood \(N(v)\) or the closed neighborhood \(N[v]=N(v)\cup\{v\}\), evaluates a graph parameter \(f\) on that induced subgraph, and then aggregates the local values over all vertices.

Formally, define

\[\begin{split}S_v \;=\; \begin{cases} N(v), & \text{if neighborhood = 'open'},\\ N[v], & \text{if neighborhood = 'closed'}. \end{cases}\end{split}\]

This function computes

\[\operatorname{Agg}_{v\in V(G)}\; f\!\left(G[S_v]\right),\]

where \(G[S_v]\) is the induced subgraph on \(S_v\) and \(\operatorname{Agg}\) is one of max, min, sum, or the arithmetic mean avg.

Parameters:

• G (networkx.Graph-like) – A finite graph. Neighborhoods are defined using G.neighbors(v), so this is primarily intended for undirected graphs. For directed graphs, NetworkX treats neighbors as successors, yielding an out-neighborhood variant.

• f (callable) –

  A function that accepts a graph H and returns a numeric value.

  Typical examples include invariant/parameter functions such as order, size, independence_number, clique_number, domination_number, and zero_forcing_number.

  This implementation calls f on a copy of each induced subgraph to guard against accidental mutation inside f.

• neighborhood ({'open', 'closed'}, default='open') –

  Which neighborhood to use.

  'open' means \(S_v = N(v)\) (neighbors only).

  'closed' means \(S_v = N[v]\) (neighbors plus the vertex itself).

• agg ({'max', 'min', 'sum', 'avg'}, default='max') – Aggregation operator applied to the multiset \(\{ f(G[S_v]) : v \in V(G)\}\).

Returns:

The aggregated value. If \(|V(G)|=0\), returns 0.

Return type:

number

Notes

• If \(v\) is isolated, then \(N(v)=\varnothing\). In that case, with neighborhood='open' the induced graph is empty, and with neighborhood='closed' the induced graph is a single vertex. Ensure your parameter function f is defined on these graphs.

• The induced subgraphs are formed independently for each vertex; overlapping neighborhoods are allowed.

• If f is guaranteed to be read-only, you may remove the .copy() calls for speed.

Raises:

ValueError – If neighborhood is not in {'open','closed'} or agg is not in {'max','min','sum','avg'}.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(5)
>>> gc.local_parameter(G, gc.maximum_degree, neighborhood="open", agg="max")
0
>>> gc.local_parameter(G, gc.order, neighborhood="closed", agg="max")
3

graphcalc.graphs.invariants.local_invariants.local_parameter_radius(G, f, *, r=1, closed=True, agg='max')

Apply a graph parameter locally to radius-:math:`r` distance balls and aggregate.

For each vertex \(v \in V(G)\), form the vertex set of the (closed) distance ball

\[B_r(v) \;=\; \{\, u \in V(G) : d_G(u,v) \le r \,\},\]

where \(d_G\) is the unweighted shortest-path distance in \(G\). The function then evaluates a graph parameter \(f\) on the induced subgraph \(G[B_r(v)]\) (or on the induced open ball if closed=False), and aggregates the resulting values over all vertices.

If closed=False, the center vertex \(v\) is removed from the ball before inducing: \(B_r(v) \setminus \{v\}\).

Common special cases

• r=1, closed=False gives induced open neighborhoods \(G[N(v)]\).

• r=1, closed=True gives induced closed neighborhoods \(G[N[v]]\).

• r=2, closed=True gives induced closed distance-2 balls.

• r=2, closed=False gives induced open distance-2 balls (distance ≤ 2, excluding the center).

param G:

A finite graph. Distances are computed with unweighted BFS via networkx.single_source_shortest_path_length(). This is primarily intended for undirected graphs; for directed graphs, distances respect edge directions.

type G:

networkx.Graph-like

param f:

A function accepting a graph H and returning a numeric value. This implementation calls f on a copy of each induced ball subgraph.

type f:

callable

param r:

Radius \(r \ge 0\). If r=0, each ball is {v} (or empty if closed=False).

type r:

int, optional

param closed:

If True, include the center vertex \(v\) in the ball; if False, exclude it.

type closed:

bool, optional

param agg:

Aggregation operator applied to the multiset of local values \(\{ f(G[B_r(v)]) : v\in V(G)\}\) (or open balls when closed=False).

type agg:

{‘max’, ‘min’, ‘sum’, ‘avg’}, optional

returns:

The aggregated value. If \(|V(G)| = 0\), returns 0.

rtype:

number

raises ValueError:

If r < 0 or if agg is not in {'max','min','sum','avg'}.

Notes

• The ball is computed with BFS distances in the original graph G and then induced. This is different from, e.g., taking the radius-\(r\) neighborhood inside some already induced subgraph.

• Ensure your parameter f is defined on the empty graph, since open balls can be empty when r=0 or when a vertex is isolated and you exclude the center.

Complexity

For each vertex, a BFS to depth r is performed. In the worst case (when r is large relative to the diameter), this is essentially one BFS per vertex, so the time is \(O(|V||E|)\) for sparse graphs (more precisely \(O(\sum_v (|V|+|E|))\) in the worst case). The dominant cost is usually the BFS calls plus evaluation of f on each induced ball.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(6)
>>> # Max size of closed radius-2 balls in a path on 6 vertices:
>>> gc.local_parameter_radius(G, gc.order, r=2, closed=True, agg="max")
5
>>> # Average size of open radius-1 balls is the average degree:
>>> gc.local_parameter_radius(G, gc.order, r=1, closed=False, agg="avg")
1.6666666666666667

graphcalc.graphs.invariants.local_invariants.local_residue(G)

Compute the local Havel–Hakimi residue of a graph \(G\) (with respect to open neighborhoods).

This parameter is defined by applying the Havel–Hakimi residue (as implemented by graphcalc.residue()) to each induced open neighborhood subgraph and taking the maximum:

\[\operatorname{res}_{\mathrm{loc}}(G) \;=\; \max_{v \in V(G)} \operatorname{res}\!\bigl(G[N(v)]\bigr),\]

where \(N(v)\) is the open neighborhood of \(v\), \(G[N(v)]\) is the subgraph induced by \(N(v)\), and \(\operatorname{res}(H)\) denotes the Havel–Hakimi residue of \(H\).

Havel–Hakimi residue (brief description)

The Havel–Hakimi process operates on a (nonnegative) integer degree sequence \(d=(d_1,\dots,d_n)\):

1. Sort the sequence in nonincreasing order.

2. Remove the first term \(d_1\).

3. Subtract 1 from each of the next \(d_1\) terms.

4. Repeat until no positive terms remain (or the process fails for non-graphical sequences).

When applied to the degree sequence of a graph \(H\), this iterative reduction produces a terminal sequence with some number of zeros. The residue \(\operatorname{res}(H)\) (in the Havel–Hakimi sense) is the number of zeros in this terminal sequence. Equivalently, it is the number of vertices left with degree 0 at termination of the Havel–Hakimi reduction started from the degree sequence of \(H\).

(This matches the convention used by graphcalc.residue().)

param G:

A finite graph. Neighborhoods are computed via G.neighbors(v), so this is primarily intended for undirected graphs under the standard adjacency notion. For directed graphs, NetworkX interprets neighbors as successors; if you want an undirected notion, convert via G.to_undirected() first.

type G:

networkx.Graph-like

returns:

The value \(\operatorname{res}_{\mathrm{loc}}(G)\). If \(G\) has no vertices, returns 0.

rtype:

int

Notes

• If \(v\) is isolated, then \(N(v)=\varnothing\) and \(G[N(v)]\) is the empty graph. The Havel–Hakimi residue of the empty graph is 0 under the usual convention, so isolated vertices do not increase the maximum.

• This is a local construction: it measures the Havel–Hakimi residue on neighborhood-induced subgraphs rather than on \(G\) itself.

• The Havel–Hakimi residue is defined via degree sequences and depends only on the degree sequence of the input graph, not on its particular labeling.

Complexity

This function delegates to local_parameter() with gc.residue. The runtime is dominated by the cost of evaluating gc.residue on each neighborhood-induced subgraph.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # For a complete graph K_n, each open neighborhood is K_{n-1} (regular),
>>> # so the local residue is the HH-residue of K_{n-1}.
>>> G = nx.complete_graph(6)
>>> gc.local_residue(G)
1

graphcalc.graphs.invariants.local_invariants.local_zero_forcing_number(G)

Compute the local zero forcing number of a graph \(G\) (with respect to open neighborhoods).

The local zero forcing number is defined as the maximum zero forcing number attained by an induced open neighborhood:

\[Z_{\mathrm{loc}}(G) \;=\; \max_{v \in V(G)} Z\!\bigl(G[N(v)]\bigr),\]

where \(N(v)\) is the open neighborhood of \(v\), \(G[N(v)]\) is the subgraph induced by \(N(v)\), and \(Z(H)\) denotes the zero forcing number of a graph \(H\).

Zero forcing number (brief definition)

Given a graph \(H\) and an initial set \(S \subseteq V(H)\) of colored vertices, apply the standard zero forcing rule repeatedly:

• If a colored vertex has exactly one uncolored neighbor, it forces that neighbor to become colored.

The set \(S\) is a zero forcing set if this process eventually colors all vertices of \(H\). The zero forcing number is the minimum size of such a set:

\[Z(H) \;=\; \min\{\, |S| : S \subseteq V(H)\ \text{is a zero forcing set for } H \,\}.\]

param G:

A finite graph. Neighborhoods are computed via G.neighbors(v), so this is primarily intended for undirected graphs under the standard adjacency notion. For directed graphs, NetworkX interprets neighbors as successors, which yields an out-neighborhood variant.

type G:

networkx.Graph-like

returns:

The value \(Z_{\mathrm{loc}}(G)\). If \(G\) has no vertices, returns 0.

rtype:

int

Notes

• If \(v\) is isolated, then \(N(v)=\varnothing\) and \(G[N(v)]\) is the empty graph. Under the standard convention used by most zero-forcing implementations, the empty graph has zero forcing number 0, so isolated vertices do not increase the maximum.

• This is a local refinement: it measures how large a forcing set is needed to control each neighborhood-induced subgraph, rather than \(G\) itself. In general, \(Z_{\mathrm{loc}}(G)\) is not equal to \(Z(G)\).

Complexity

This function delegates to local_parameter() with gc.zero_forcing_number. The runtime is therefore dominated by the cost of computing the zero forcing number on each neighborhood-induced subgraph. Exact zero forcing number routines are typically exponential in neighborhood size.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # In a complete graph, each neighborhood is complete, and Z(K_m)=m-1.
>>> K6 = nx.complete_graph(6)
>>> gc.local_zero_forcing_number(K6)  # neighborhoods are K5
4

>>> # In a star, the center's neighborhood is an independent set of size n-1, whose Z equals n-1.
>>> S = nx.star_graph(5)  # 6 vertices total: center + 5 leaves
>>> gc.local_zero_forcing_number(S)
5