degree

Degree

graphcalc.graphs.invariants.degree.annihilation_number(G: Graph) → int[source]

Returns the annihilation number of the graph.

The annihilation number of a graph \(G\) is defined as:

\[a(G) = \max\{t : \sum_{i=1}^t d_i \leq m \}\]

where

\[d_1 \leq d_2 \leq \cdots \leq d_n\]

is the degree sequence of the graph ordered in non-decreasing order, and \(m\) is the number of edges in \(G\).

Parameters:: G (NetworkX graph) – An undirected graph.
Returns:: The annihilation number of the graph.
Return type:: int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph, cycle_graph, complete_graph

>>> G = cycle_graph(6)  # A cycle graph with 6 vertices
>>> gc.annihilation_number(G)
3

>>> H = path_graph(5)  # A path graph with 5 vertices
>>> gc.annihilation_number(H)
3

>>> K = complete_graph(5)  # A complete graph with 5 vertices
>>> gc.annihilation_number(K)
2

References

P. Dankelmann, S. Mukwembi, and H.C. Swart, The annihilation number of a graph, Utilitas Mathematica, 72:91–108, (2007).

graphcalc.graphs.invariants.degree.average_degree(G: Graph) → float[source]

Returns the average degree of a graph.

The average degree of a graph is the sum of vertex degrees divided by the number of vertices.

Parameters:: G (nx.Graph) – The input graph.
Returns:: The average degree of the graph.
Return type:: float

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> gc.average_degree(G)
1.5

graphcalc.graphs.invariants.degree.count_of_maximum_degree_vertices(G)[source]

Count the vertices attaining the maximum degree in a graph \(G\).

Let \(\Delta(G) = \max\{\deg(v) : v \in V(G)\}\) be the maximum degree. This function returns

\[\bigl|\{\, v \in V(G) : \deg(v) = \Delta(G) \,\}\bigr|.\]

Parameters:: G (networkx.Graph-like) – A finite graph. Degrees are taken from G.degree() using NetworkX conventions for the graph type (undirected degree for Graph, total degree for DiGraph, multiplicity for MultiGraph).
Returns:: The number of vertices of degree \(\Delta(G)\). If \(G\) has no vertices, returns 0.
Return type:: int

Notes

For simple undirected graphs, this is the number of vertices with maximum degree.
For directed graphs, this uses total degree unless you substitute G.in_degree() or G.out_degree() by convention.

Complexity

\(O(|V(G)|)\) time to scan degrees (and \(O(|V(G)|)\) auxiliary space in this particular implementation due to materializing the degree list).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.star_graph(5)  # center degree 5, leaves degree 1
>>> gc.count_of_maximum_degree_vertices(G)
1

graphcalc.graphs.invariants.degree.count_of_minimum_degree_vertices(G)[source]

Count the vertices attaining the minimum degree in a graph \(G\).

Let \(\delta(G) = \min\{\deg(v) : v \in V(G)\}\) be the minimum degree. This function returns

\[\bigl|\{\, v \in V(G) : \deg(v) = \delta(G) \,\}\bigr|.\]

Parameters:: G (networkx.Graph-like) – A finite graph. Degrees are taken from G.degree() using NetworkX conventions for the graph type (undirected degree for Graph, total degree for DiGraph, multiplicity for MultiGraph).
Returns:: The number of vertices of degree \(\delta(G)\). If \(G\) has no vertices, returns 0.
Return type:: int

Notes

For simple undirected graphs, isolated vertices (degree 0) determine \(\delta(G)=0\) whenever they exist.
For directed graphs, this uses total degree unless you substitute G.in_degree() or G.out_degree() by convention.

Complexity

\(O(|V(G)|)\) time to scan degrees (and \(O(|V(G)|)\) auxiliary space in this particular implementation due to materializing the degree list).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(5)  # min degree is 1, achieved by 2 endpoints
>>> gc.count_of_minimum_degree_vertices(G)
2
>>> H = nx.empty_graph(4)  # all degrees 0
>>> gc.count_of_minimum_degree_vertices(H)
4

graphcalc.graphs.invariants.degree.degree(G: Graph, v: Hashable) → int[source]

Returns the degree of a vertex in a graph.

The degree of a vertex is the number of edges connected to it.

Parameters:

G (nx.Graph) – The input graph.
v (int) – The vertex whose degree is to be calculated.

Returns:

The degree of the vertex.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> gc.degree(G, 1)
2
>>> gc.degree(G, 0)
1

graphcalc.graphs.invariants.degree.degree_sequence(G: Graph, nonincreasing=True) → List[int][source]

Returns the degree sequence of a graph.

The degree sequence is the list of vertex degrees in the graph, optionally sorted in nonincreasing order.

Parameters:

G (nx.Graph) – The input graph.
nonincreasing (bool, optional (default=True)) – If True, the degree sequence is sorted in nonincreasing order.

Returns:

The degree sequence of the graph.

Return type:

list

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> gc.degree_sequence(G)
[2, 2, 1, 1]
>>> gc.degree_sequence(G, nonincreasing=False)
[1, 1, 2, 2]

graphcalc.graphs.invariants.degree.distinct_degree_count(G)[source]

Return the number of distinct vertex degrees attained in a graph \(G\).

Formally, this computes the cardinality of the set of degrees appearing among vertices:

\[\bigl|\{\, \deg(v) : v \in V(G) \,\}\bigr|.\]

Parameters:

G (networkx.Graph-like) –

A finite graph. Degrees are taken from G.degree(), following NetworkX conventions:

Graph: undirected degree.
DiGraph: total degree (in-degree + out-degree).
MultiGraph / MultiDiGraph: degree counts edge multiplicity.

Returns:

The number of distinct degree values occurring in \(G\). For the empty graph (no vertices), this returns 0.

Return type:

int

Notes

For simple undirected graphs, this is the number of distinct entries in the degree sequence.
This is sometimes used as a coarse measure of “degree heterogeneity”.
If you want distinct in-degrees or out-degrees for a digraph, use G.in_degree() or G.out_degree() instead of G.degree().

Complexity

\(O(|V(G)|)\) time and \(O(k)\) additional space, where \(k\) is the number of distinct degrees (at most \(|V(G)|\)).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(5)  # degrees: {1,2}
>>> gc.distinct_degree_count(G)
2
>>> H = nx.empty_graph(4)  # degrees: {0}
>>> gc.distinct_degree_count(H)
1
>>> gc.distinct_degree_count(nx.empty_graph(0))
0

graphcalc.graphs.invariants.degree.irregularity(G)[source]

Compute the (Albertson) irregularity of a graph \(G\).

The (Albertson) irregularity is the edge-sum of absolute degree differences:

\[\operatorname{irr}(G) \;=\; \sum_{uv \in E(G)} \bigl| \deg(u) - \deg(v) \bigr|,\]

where \(\deg(u)\) denotes the (undirected) degree of vertex \(u\).

Parameters:

G (networkx.Graph-like) –

A finite graph. For standard usage in graph invariants, \(G\) is typically a simple undirected graph. Degrees are read from G.degree() and the sum ranges over the edges returned by G.edges().

If G is a MultiGraph, parallel edges are iterated with multiplicity and degrees count multiplicity, so this computes the natural multigraph extension.
If G is directed, G.degree() is the total degree (in-degree + out-degree), so the result is the Albertson irregularity with respect to total degree unless you replace it by G.in_degree() or G.out_degree() by convention.

Returns:

The value \(\operatorname{irr}(G)\). In particular, if \(G\) has no edges, the sum is empty and the function returns 0.

Return type:

int

Notes

This invariant is commonly attributed to Albertson and is often called the Albertson irregularity.
\(\operatorname{irr}(G)=0\) if and only if \(G\) is regular on every edge, i.e., every edge joins two vertices of equal degree. (For simple graphs, this holds in particular for regular graphs.)
The quantity is additive over components in the sense that it is a sum over edges; there are no cross-component contributions.

Complexity

Let \(n=|V(G)|\) and \(m=|E(G)|\). Constructing the degree dictionary takes \(O(n+m)\) time. The subsequent edge-sum takes \(O(m)\) time. Memory usage is \(O(n)\) for the cached degrees.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # Path P4 has degrees [1,2,2,1]; edge differences are 1,0,1 so irr=2
>>> G = nx.path_graph(4)
>>> gc.irregularity(G)
2

>>> # Any regular graph has irr=0
>>> H = nx.cycle_graph(6)
>>> gc.irregularity(H)
0

graphcalc.graphs.invariants.degree.k_residue(G: Graph, k: int) → int[source]

Compute the \(k\)-residue \(R_k(G)\) from the Havel–Hakimi elimination sequence.

Let \(D\) be a graphic degree sequence and let \(E=E(D)\) be its Havel–Hakimi elimination sequence (the list of values removed at each step, including trailing zeros). For \(k \ge 1\), define

\[R_k(E) \;=\; \sum_{i=0}^{k-1} (k-i)\, f_i(E),\]

where \(f_i(E)\) is the frequency of \(i\) in \(E\). Since \(E\) is determined by the degree sequence of \(G\), we write \(R_k(G)\).

The special case \(k=1\) gives the classical residue:

\[R_1(G) \;=\; f_0(E) \;=\; R(G).\]

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.
k (int) – The parameter \(k \ge 1\).

Returns:

The \(k\)-residue \(R_k(G)\).

Return type:

int

Notes

This function constructs the elimination sequence \(E\) by running the Havel–Hakimi process and recording the removed value at each step, including trailing zeros. Including those zeros ensures \(f_0(E)\) matches the classical residue.

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph, complete_graph
>>> G = path_graph(4)
>>> gc.k_residue(G, 1) == gc.residue(G)
True

>>> H = complete_graph(4)
>>> gc.k_residue(H, 2)
3

graphcalc.graphs.invariants.degree.k_residue_from_degrees(degrees: Sequence[int], k: int) → int[source]

Compute the \(k\)-residue \(R_k\) from a degree sequence via its elimination sequence.

Let \(D\) be a (graphic) degree sequence and let \(E=E(D)\) be its Havel–Hakimi elimination sequence (including trailing zeros). For \(k \ge 1\),

\[R_k(E) \;=\; \sum_{i=0}^{k-1} (k-i)\, f_i(E),\]

where \(f_i(E)\) is the frequency of \(i\) in \(E\). This function computes \(R_k(E(D))\) from the input degree sequence.

Parameters:

degrees (sequence of int) – A sequence of nonnegative integers (assumed graphical when coming from a graph).
k (int) – The parameter \(k \ge 1\).

Returns:

The \(k\)-residue \(R_k(D)\).

Return type:

int

Raises:

ValueError – If k < 1.

Complexity

\(O(|V(G)|)\), since it scans the degree view once.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(5)  # degrees: 1,2,2,2,1
>>> gc.n1_degree_count(G)
2

graphcalc.graphs.invariants.degree.residue(G: Graph) → int[source]

Returns the residue of a graph.

The residue of a graph is defined as the number of zeros obtained at the end of the Havel-Hakimi process. This process determines whether a given degree sequence corresponds to a graphical sequence, which is a sequence of integers that can be realized as the degree sequence of a simple graph.

Havel-Hakimi Algorithm: - Sort the degree sequence in non-increasing order. - Remove the largest degree (say, \(d\)) from the sequence. - Reduce the next \(d\) degrees by 1. - Repeat until all degrees are zero (graphical) or a negative degree is encountered (non-graphical).

The residue is the count of zeros in the sequence when the algorithm terminates.

Parameters:: G (nx.Graph) – The graph whose residue is to be calculated.
Returns:: The residue of the graph.
Return type:: int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph, complete_graph, cycle_graph

>>> G = path_graph(4)  # Path graph with 4 vertices
>>> gc.residue(G)
2

>>> H = complete_graph(4)  # Complete graph with 4 vertices
>>> gc.residue(H)
1

>>> K = cycle_graph(5)  # Cycle graph with 5 vertices
>>> gc.residue(K)
2

References

Havel, Václav, and Hakimi, Seymour L. “A Method of Constructing Graphs from their Degree Sequence.” Journal of Mathematical Analysis and Applications, 1963.

Notes

The Havel-Hakimi process ensures the degree sequence remains graphical throughout the steps, making it a key concept in graph theory.

graphcalc.graphs.invariants.degree.residue_from_degrees(degrees: Sequence[int]) → int[source]

Classical residue R(D): number of zeros in the elimination sequence E(D).

Parameters:: degrees (Sequence[int]) – Degree sequence.
Returns:: R(D) = f_0(E(D)).
Return type:: int

graphcalc.graphs.invariants.degree.slater(G: Graph) → int[source]

Returns the Slater invariant for the graph.

The Slater invariant of a graph \(G\) is a lower bound for the domination number of a graph defined by:

\[sl(G) = \min\{t : t + \sum_{i=0}^t d_i \geq n\}\]

where

\[{d_1 \geq d_2 \geq \cdots \geq d_n}\]

is the degree sequence of the graph ordered in non-increasing order and n is the order of \(G\).

Amos et al. rediscovered this invariant and generalized it into what is now known as the sub-\(k\)-domination number.

Parameters:: G (NetworkX graph) – An undirected graph.
Returns:: The Slater invariant for the graph.
Return type:: int