IsSplitGraph - Maple Help

GraphTheory

 IsSplitGraph
 test if graph is a split graph

 Calling Sequence IsSplitGraph(G,opts)

Parameters

 G - graph opts - (optional) equation of the form decomposition=true or decomposition=false

Options

 • decomposition : keyword option of the form decomposition=true or decomposition=false.
 Specifies whether the decomposition into a maximum clique and an independent set should be returned when the graph is a split graph. If true, the result is an expression sequence whose second element is a two-element list containing a maximum clique and an independent set when G is a split graph. The default is false.

Description

 • IsSplitGraph(G) returns true if G is a split graph and false otherwise.

Definition

 • An undirected graph G is a split graph if its vertices can be partitioned into a clique and an independent set. The partition is not guaranteed to be unique.
 • Split graphs are closed under graph complement.
 • Every split graph is a chordal graph.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $K≔\mathrm{Graph}\left(5,\left\{\left\{1,2\right\},\left\{1,3\right\},\left\{2,3\right\},\left\{2,4\right\},\left\{3,4\right\},\left\{4,5\right\}\right\}\right)$
 ${K}{≔}{\mathrm{Graph 1: an undirected graph with 5 vertices and 6 edge\left(s\right)}}$ (1)
 > $\mathrm{IsSplitGraph}\left(K\right)$
 ${\mathrm{true}}$ (2)
 > $\mathrm{IsSplitGraph}\left(K,\mathrm{decomposition}\right)$
 ${\mathrm{true}}{,}\left[\left[{2}{,}{3}{,}{4}\right]{,}\left[{1}{,}{5}\right]\right]$ (3)
 > $P≔\mathrm{PathGraph}\left(4\right)$
 ${P}{≔}{\mathrm{Graph 2: an undirected graph with 4 vertices and 3 edge\left(s\right)}}$ (4)
 > $\mathrm{IsSplitGraph}\left(P\right)$
 ${\mathrm{true}}$ (5)
 > $\mathrm{IsSplitGraph}\left(P,\mathrm{decomposition}\right)$
 ${\mathrm{true}}{,}\left[\left[{2}{,}{3}\right]{,}\left[{1}{,}{4}\right]\right]$ (6)
 > $G≔\mathrm{SpecialGraphs}:-\mathrm{PetersenGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 3: an undirected graph with 10 vertices and 15 edge\left(s\right)}}$ (7)
 > $\mathrm{IsSplitGraph}\left(G\right)$
 ${\mathrm{false}}$ (8)

Compatibility

 • The GraphTheory[IsSplitGraph] command was introduced in Maple 2020.