Structural Properties¶

The following functions allow the user to check for certain structural graph properties.

jgrapht.properties.has_multipleedges(graph)[source]

Check if a graph has multiple-edges.

Parameters

graph – the graph

Returns

True if it has multiple-edges, False otherwise

jgrapht.properties.has_ore(graph)[source]

Check whether an undirected graph meets Ore’s condition to be Hamiltonian.

Parameters

graph – The input graph

Returns

True if the graph meets Ore’s condition, False otherwise

jgrapht.properties.has_selfloops(graph)[source]

Check if a graph has self-loops.

Parameters

graph – the graph

Returns

True if it has self-loops, False otherwise

jgrapht.properties.is_bipartite(graph)[source]

Check if a graph is bipartite.

Parameters

graph – the graph

Returns

True if the graph is bipartite, False otherwise

jgrapht.properties.is_chordal(graph)[source]

Check where the graph is chordal.

Parameters

graph – the graph

Returns

True if the graph is chordal, False otherwise

jgrapht.properties.is_complete(graph)[source]

Check if the graph is complete.

For undirected graphs, each pair of vertices must be connected by a single edge. For directed graphs, each pair of vertices must be connected by one pair of edges, one in each direction.

Parameters

graph – the graph

Returns

True if the graph is complete, False otherwise

jgrapht.properties.is_cubic(graph)[source]

Check whether a graph is cubic.

A graph is cubic if all vertices have degree equal to three.

Parameters

graph – the graph

Returns

True if the graph is cubic, False otherwise

jgrapht.properties.is_empty_graph(graph)[source]

Check whether the graph is empty. An empty graph with n nodes contains n isolates nodes but no edges.

Parameters

graph – the graph

Returns

True if the graph is empty, False otherwise.

jgrapht.properties.is_eulerian(graph)[source]

Check whether a graph is Eulerian.

An Eulerian graph is a graph containing an Eulerian cycle.

Parameters

graph – the graph

Returns

True if the graph is Eulerian, False otherwise

jgrapht.properties.is_forest(graph)[source]

Check if an undirected graph is a forest.

Parameters

graph – the graph

Returns

True if the graph is a forest, False otherwise

jgrapht.properties.is_k33_subdivision(graph)[source]

Check whether a graph is a $$K_{3,3}$$ subdivision.

Parameters

graph – the graph

Returns

True if the graph is a $$K_{3,3}$$ subdivision, False otherwise

jgrapht.properties.is_k5_subdivision(graph)[source]

Check whether a graph is a $$K_{5}$$ subdivision.

Parameters

graph – the graph

Returns

True if the graph is a $$K_{5}$$ subdivision, False otherwise

jgrapht.properties.is_kuratowski_subdivision(graph)[source]

Check whether a graph is a $$K_{3,3}$$ or a $$K_5$$ subdivision.

Parameters

graph – the graph

Returns

True if the graph is a $$K_{3,3}$$ or a $$K_5$$ subdivision, False otherwise

jgrapht.properties.is_overfull(graph)[source]

Check if the graph is overfull.

A graph is overfull if $$m > \Delta(G) \lfloor n/2 \rfloor$$ where $$\Delta(G)$$ is the maximum degree in the graph.

Parameters

graph – the graph

Returns

True if the graph is ovefull, False otherwise

jgrapht.properties.is_perfect(graph)[source]

Check whether a graph is perfect.

Parameters

graph – the graph

Returns

True if the graph is perfect, False otherwise

jgrapht.properties.is_planar(graph)[source]

Check whether a graph is planar.

Parameters

graph – the graph

Returns

True if the graph is planar, False otherwise

jgrapht.properties.is_simple(graph)[source]

Check if a graph is simple. A graph is simple if it has no self-loops and multiple edges.

Parameters

graph – the graph

Returns

True if simple, False otherwise

jgrapht.properties.is_split(graph)[source]

Test whether an undirected graph is a split graph.

Parameters

graph – the graph

Returns

True if the graph is a split graph, False otherwise

jgrapht.properties.is_strongly_connected(graph)[source]

Test whether a graph is strongly connected.

Parameters

graph – the graph

Returns

True if strongly-connected, False otherwise

jgrapht.properties.is_tree(graph)[source]

Check if an undirected graph is a tree.

Parameters

graph – the graph

Returns

True if the graph is a tree, False otherwise

jgrapht.properties.is_trianglefree(graph)[source]

Check whether an undirected graph is triangle free.

Parameters

graph – the graph

Returns

True if the graph is triangle free, False otherwise

jgrapht.properties.is_weakly_chordal(graph)[source]

Check where the graph is weakly chordal.

Parameters

graph – the graph

Returns

True if the graph is weakly chordal, False otherwise

jgrapht.properties.is_weakly_connected(graph)[source]

Test whether a directed graph is weakly connected.

Parameters

graph – the graph. Needs to be directed

Returns

True if weakly connected, False otherwise