networkx icon indicating copy to clipboard operation
networkx copied to clipboard

ENH: Add is_split_graph and is_complete_split_graph functions with tests

Open sourabh-sudesh-paradeshi opened this issue 6 months ago • 2 comments

Summary

This PR introduces two functions to recognize split graphs in networkx.algorithms:

  • is_split_graph(G) — returns True if the graph is both chordal and its complement is chordal.
  • is_complete_split_graph(G) — returns True if the graph can be partitioned into a clique and an independent set, with all vertices in the independent set adjacent to every vertex in the clique.

Motivation

Split graphs form a well-studied class of graphs that intersect properties of chordal graphs and co-chordal graphs. The recognition functions are useful for research, teaching, and applications involving graph decompositions and forbidden subgraph characterizations.

References

  • https://en.wikipedia.org/wiki/Split_graph

Gentle ping @sourabh-sudesh-paradeshi

rossbar avatar Jul 23 '25 08:07 rossbar

Gentle ping @sourabh-sudesh-paradeshi

Refined the logic and tests, all checks pass now — ready for your review. Thanks!