# Graph Theory Package For Giac/Xcas Graphtheory User Manual

User Manual:

Open the PDF directly: View PDF .

Page Count: 87

- 1. Introduction
- 2. Constructing graphs
- 3. Modifying graphs
- 4. Import and export
- 5. Graph properties
- 6. Traversing graphs
- 7. Visualizing graphs
- Bibliography
- Command Index

Graph theory

package for

Giac/Xcas

Reference manual

June 2018

draft

Table of contents

1. Introduction .............................................. 7

1.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2. Notations used in this manual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2. Constructing graphs ....................................... 9

2.1. General graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.1. Creating undirected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.2. Creating directed graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.3. Creating vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.4. Creating edges and arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.5. Creating paths and trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.6. Specifying adjacency or weight matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2. Promoting to directed and undirected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2.1. Converting edges to pairs of arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2.2. Assigning weight matrix to an unweighted graph . . . . . . . . . . . . . . . . . . . . . 12

2.3. Cycle and path graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3.1. Cycle graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3.2. Path graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.3. Trails of edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4. Complete graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4.1. Complete graphs with multiple vertex partitions . . . . . . . . . . . . . . . . . . . . . 13

2.4.2. Complete trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.5. Sequence graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5.1. Creating graphs from degree sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5.2. Validating graphic sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.6. Intersection graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.6.1. Interval graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.6.2. Kneser graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.7. Special graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.7.1. Hypercube graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.7.2. Star graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.7.3. Wheel graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.7.4. Web graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.7.5. Prism graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.7.6. Antiprism graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.7.7. Grid graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.7.8. Sierpi«ski graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.7.9. Generalized Petersen graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.7.10. LCF graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.8. Isomorphic copies of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.8.1. Creating an isomorphic copy of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.8.2. Permuting graph vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.8.3. Relabeling graph vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.9. Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.9.1. Extracting subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.9.2. Induced subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.9.3. Underlying graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.10. Operations on graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.10.1. Graph complement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3

2.10.2. Seidel switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.10.3. Transposing graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.10.4. Union of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.10.5. Disjoint union of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.10.6. Joining two graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.10.7. Power graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.10.8. Graph products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.10.9. Transitive closure graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.10.10. Line graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.10.11. Plane dual graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.11. Random graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.11.1. Random general graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.11.2. Random bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.11.3. Random trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.11.4. Random planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.11.5. Random regular graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.11.6. Random tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.11.7. Random ﬂow networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.11.8. Randomizing edge weights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3. Modifying graphs ......................................... 37

3.1. Modifying vertices of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.1.1. Adding and removing single vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2. Modifying edges of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2.1. Adding and removing single edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2.2. Accessing and modifying edge weights . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2.3. Contracting edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2.4. Subdividing edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.3. Using attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3.1. Graph attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3.2. Vertex attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3.3. Edge attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4. Import and export ........................................ 43

4.1. Importing graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.1.1. Loading graphs from dot ﬁles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.1.2. The dot ﬁle format overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.2. Exporting graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2.1. Saving graphs in dot format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2.2. Saving graph drawings in L

ATE

X format . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5. Graph properties ......................................... 47

5.1. Basic properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.1.1. Listing vertices and edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.1.2. Vertex degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.1.3. Vertex adjacency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.1.4. Edge incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.2. Algebraic properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.2.1. Adjacency matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.2.2. Weight matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.2.3. Incidence matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.2.4. Characteristic polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.2.5. Graph spectrum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.2.6. Seidel spectrum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.2.7. Integer graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4Table of contents

5.3. Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.3.1. Vertex connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.3.2. Connected and biconnected components . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.3.3. Graph rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.3.4. Articulation points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.3.5. Strongly connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.3.6. Edge connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.4. Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.4.1. Tree graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.4.2. Forest graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.4.3. Height of a tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.4.4. Lowest common ancestor of a pair of nodes . . . . . . . . . . . . . . . . . . . . . . . . 58

5.5. Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.5.1. Vertex distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.5.2. All-pairs vertex distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.5.3. Diameter of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.5.4. Girth of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.6. Acyclic graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.6.1. Checking if a graph is acyclic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.6.2. Topological sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.6.3. st ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.7. Vertex matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.7.1. Maximum matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.7.2. Maximum matching in bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.8. Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.8.1. Clique graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.8.2. Triangle-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.8.3. Maximal cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.8.4. Maximum clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.8.5. Minimum clique cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.9. Vertex coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.9.1. Greedy coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.9.2. Minimal coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.9.3. Chromatic number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.9.4. k-coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.10. Edge coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

6. Traversing graphs ........................................ 71

6.1. Walks and tours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.1.1. Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.1.2. Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.2. Optimal routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.2.1. Shortest paths in unweighted graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.2.2. Cheapest paths in weighted graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.2.3. Traveling salesman problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.3. Spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.3.1. Constructing a spanning tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.3.2. Minimal spanning tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.3.3. Counting all spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

7. Visualizing graphs ........................................ 75

7.1. Drawing graphs by using various methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

7.1.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

7.1.2. Drawing disconnected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

7.1.3. Spring method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

7.1.4. Drawing trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

Table of contents 5

7.1.5. Drawing planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

7.1.6. Circular graph drawings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

7.2. Custom vertex positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

7.2.1. Setting vertex positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

7.2.2. Generating vertex positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

7.3. Highlighting parts of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

7.3.1. Highlighting vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

7.3.2. Highlighting edges and trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

7.3.3. Highlighting subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

Bibliography ................................................ 85

Command Index .............................................. 87

6Table of contents

Chapter 1

Introduction

1.1. Overview

This document contains an overview of the graph theory commands built in the Giac/Xcas soft-

ware, including the syntax, the detailed description and practical examples for each command.

1.2. Notations used in this manual

7

Chapter 2

Constructing graphs

2.1. General graphs

The commands graph and digraph are used for constructing general graphs.

2.1.1. Creating undirected graphs

The command graph accepts between one and three mandatory arguments, each of them being

one of the following structural elements of the resulting graph:

¡the number or list of vertices (a vertex may be any atomic object, such as an integer, a

symbol or a string); it must be the ﬁrst argument if used,

¡the set of edges (each edge is a list containing two vertices), a permutation, a trail of edges

or a sequence of trails; it can be either the ﬁrst or the second argument if used,

¡the adjacency or weight matrix.

Additionally, some of the following options may be appended to the sequence of arguments:

•directed = true or false,

•weighted = true or false,

•color = an integer or a list of integers representing color(s) of the vertices,

•coordinates = a list of vertex 2D or 3D coordinates.

The graph command may also be called by passing a string, representing the name of a special

graph, as its only argument. In that case the corresponding graph will be constructed and returned.

The supported graphs and their names are listed below.

1. Clebsch graph: clebsch

2. Coxeter graph: coxeter

3. Desargues graph: desargues

4. Dodecahedral graph: dodecahedron

5. Dürer graph: durer

6. Dyck graph: dyck

7. Grinberg graph: grinberg

8. Grotzsch graph: grotzsch

9. Harries graph: harries

10. Harries–Wong graph: harries-wong

11. Heawood graph: heawood

9

12. Herschel graph: herschel

13. Icosahedral graph: icosahedron

14. Levi graph: levi

15. Ljubljana graph: ljubljana

16. McGee graph: mcgee

17. Möbius–Kantor graph: mobius-kantor

18. Nauru graph: nauru

19. Octahedral graph: octahedron

20. Pappus graph: pappus

21. Petersen graph: petersen

22. Robertson graph: robertson

23. Truncated icosahedral graph: soccerball

24. Shrikhande graph: shrikhande

25. Tetrahedral graph: tehtrahedron

2.1.2. Creating directed graphs

The digraph command is used for creating directed graphs, although it is also possible with the

graph command by specifying the option directed=true. Actually, calling digraph is the same as

calling graph with that option appended to the sequence of arguments. However, creating special

graphs is not supported by digraph since they are all undirected. Edges in directed graphs are

called arcs. Edges and arcs are diﬀerent structures: an edge is represented by a two-element set

containing its endpoints, while an arc is represented by the ordered pairs of its endpoints.

The following series of examples demonstrates the various possibilities when using graph and

digraph commands.

2.1.3. Creating vertices

A graph consisting only of vertices and no edges can be created simply by providing the number

of vertices or the list of vertex labels.

>graph(5)

an undirected unweighted graph with 5 vertices and 0 edges

>graph([a,b,c])

an undirected unweighted graph with 3 vertices and 0 edges

2.1.4. Creating edges and arcs

Edges/arcs must be speciﬁed inside a set so that it can be distinguished from a (adjacency or

weight) matrix. If only a set of edges/arcs is speciﬁed, the vertices needed to establish these will

be created automatically. Note that, when constructing a directed graph, the order of the vertices

in an arc matters; in undirected graphs it is not meaningful.

10 Constructing graphs

>graph(%{[a,b],[b,c],[a,c]%})

an undirected unweighted graph with 3 vertices and 3 edges

Edge weights may also be speciﬁed.

>graph(%{[[a,b],2],[[b,c],2.3],[[c,a],3/2]%})

an undirected weighted graph with 3 vertices and 3 edges

If the graph contains isolated vertices (not connected to any other vertex) or a particular order

of vertices is desired, the list of vertices has to be speciﬁed ﬁrst.

>graph([d,b,c,a],%{[a,b],[b,c],[a,c]%})

an undirected unweighted graph with 4 vertices and 3 edges

2.1.5. Creating paths and trails

A directed graph can also be created from a list of nvertices and a permutation of order n.

The resulting graph consists of a single directed path with the vertices ordered according to the

permutation.

>graph([a,b,c,d],[1,2,3,0])

a directed unweighted graph with 4 vertices and 3 arcs

Alternatively, one may specify edges as a trail.

>digraph([a,b,c,d],trail(b,c,d,a))

a directed unweighted graph with 4 vertices and 3 arcs

Using trails is also possible when creating undirected graphs. Also, some vertices in a trail may

be repeated, which is not allowed in a path.

>graph([a,b,c,d],trail(b,c,d,a,c))

an undirected unweighted graph with 4 vertices and 4 edges

There is also the possibility of specifying several trails in a sequence, which is useful for designing

more complex graphs.

>graph(trail(1,2,3,4,2),trail(3,5,6,7,5,4))

an undirected unweighted graph with 7 vertices and 9 edges

2.1.6. Specifying adjacency or weight matrix

A graph can be created from a single square matrix A= [aij]nof order n. If it contains only ones

and zeros and has zeros on its diagonal, it is assumed to be the adjacency matrix for the desired

graph. Otherwise, if an element outside the set f0;1gis encountered, it is assumed that the matrix

of edge weights is passed as input, causing the resulting graph to be weighted accordingly. In each

case, exactly nvertices will be created and i-th and j-th vertex will be connected iﬀ aij =/ 0. If the

matrix is symmetric, the resulting graph will be undirected, otherwise it will be directed.

>graph([[0,1,1,0],[1,0,0,1],[1,0,0,0],[0,1,0,0]])

an undirected unweighted graph with 4 vertices and 3 edges

>graph([[0,1.0,2.3,0],[4,0,0,3.1],[0,0,0,0],[0,0,0,0]])

a directed weighted graph with 4 vertices and 4 arcs

2.1 General graphs 11

List of vertex labels can be speciﬁed before the matrix.

>graph([a,b,c,d],[[0,1,1,0],[1,0,0,1],[1,0,0,0],[0,1,0,0]])

an undirected unweighted graph with 4 vertices and 3 edges

When creating a weighted graph, one can ﬁrst specify the list of nvertices and the set of edges,

followed by a square matrix Aof order n. Then for every edge fi; j gor arc (i; j)the element

aij of Ais assigned as its weight. Other elements of Aare ignored.

>digraph([a,b,c],%{[a,b],[b,c],[a,c]%}, [[0,1,2],[3,0,4],[5,6,0]])

a directed weighted graph with 3 vertices and 3 arcs

When a special graph is desired, one just needs to pass its name to the graph command. An

undirected unweighted graph will be returned.

>graph("petersen")

an undirected unweighted graph with 10 vertices and 15 edges

2.2. Promoting to directed and undirected graphs

2.2.1. Converting edges to pairs of arcs

To promote an existing undirected graph to a directed one or an unweighted graph to a weighted

one, use the commands make_directed and make_weighted, respectively.

The command make_directed is called with one or two arguments, an undirected graph G(V ;

E)and optionally a square matrix of order jVj. Every edge fi; j g 2 Eis replaced with the pair

of arcs (i; j)and (j ; i). If matrix Ais speciﬁed, aij and aji are assigned as weights of these arcs,

respectively. Thus a directed (and possibly weighted) graph is created and returned.

>make_directed(cycle_graph(4))

C4: a directed unweighted graph with 4 vertices and 8 arcs

>make_directed(cycle_graph(4), [[0,0,0,1],[2,0,1,3],[0,1,0,4],[5,0,4,0]])

C4: a directed weighted graph with 4 vertices and 8 arcs

2.2.2. Assigning weight matrix to an unweighted graph

The command make_weighted accepts one or two arguments, an unweighted graph G(V ; E)and

optionally a square matrix Aof order jVj. If the matrix speciﬁcation is omitted, a square matrix

of ones is assumed. Then a copy of Gis returned where each edge/arc (i; j)2Egets aij assigned

as its weight. If Gis an undirected graph, it is assumed that Ais symmetric.

>make_weighted(graph(%{[1,2],[2,3],[3,1]%}), [[0,2,3],[2,0,1],[3,1,0]])

an undirected weighted graph with 3 vertices and 3 edges

2.3. Cycle and path graphs

2.3.1. Cycle graphs

The command cycle_graph is used for constructing a cycle graph of arbitrary order.

12 Constructing graphs

cycle_graph accepts a positive integer nor a list of distinct vertices as its only argument and

returns the graph consisting of a single cycle through the speciﬁed vertices in the given order. If n

is speciﬁed it is assumed to be the desired number of vertices, in which case they will be created

and labeled with the ﬁrst nintegers (starting from 0 in Xcas mode and from 1 in Maple mode).

The resulting graph will be given the name Cn, for example C4 for n= 4.

>C5:=cycle_graph(5)

C5: an undirected unweighted graph with 5 vertices and 5 edges

>draw_graph(C5)

0

1

23

4

>cycle_graph(["a","b","c","d","e"])

C5: an undirected unweighted graph with 5 vertices and 5 edges

2.3.2. Path graphs

The command path_graph is used for constructing a path graph of arbitrary length.

path_graph accepts a positive integer nor a list of distinct vertices as its only argument and

returns a graph consisting of a single path through the speciﬁed vertices in the given order. If n

is speciﬁed it is assumed to be the desired number of vertices, in which case they will be created

and labeled with the ﬁrst nintegers (starting from 0 in Xcas mode resp. from 1 in Maple mode).

Note that a path cannot intersect itself. Paths that are allowed to cross themselves are called trails

(see the command trail).

>path_graph(5)

an undirected unweighted graph with 5 vertices and 4 edges

>path_graph(["a","b","c","d","e"])

an undirected unweighted graph with 5 vertices and 4 edges

2.3.3. Trails of edges

If the dummy command trail is called with a sequence of vertices as arguments, it returns the

symbolic expression representing the trail of edges through the speciﬁed vertices. The resulting

symbolic object is recognizable by graph and digraph commands. Note that a trail may cross

itself (some vertices may be repeated in the given sequence).

>T:=trail(1,2,3,4,2):; graph(T)

Done;an undirected unweighted graph with 4 vertices and 4 edges

2.4. Complete graphs

2.4.1. Complete graphs with multiple vertex partitions

The command complete_graph is used for construction of complete (multipartite) graphs.

2.4 Complete graphs 13

If complete_graph is called with a single argument, a positive integer nor a list of distinct vertices,

it returns the complete graph with the speciﬁed vertices. If integer nis speciﬁed, it is assumed that

it is the desired number of vertices and they will be created and labeled with the ﬁrst nintegers

(starting from 0 in Xcas mode and from 1 in Maple mode).

If a sequence of positive integers n1; n2; :::; nkis passed as argument, complete_graph returns the

complete multipartite graph with partitions of size n1; n2; :::; nk.

>K5:=complete_graph(5)

an undirected unweighted graph with 5 vertices and 10 edges

>draw_graph(K5)

0

1

23

4

>K3:=complete_graph([a,b,c])

an undirected unweighted graph with 3 vertices and 3 edges

>edges(K3)

f[a; b];[a; c];[b; c]g

>K33:=complete_graph(3,3)

an undirected unweighted graph with 6 vertices and 9 edges

>draw_graph(K33)

0 1 2

3 4 5

2.4.2. Complete trees

To construct the complete binary tree of depth n, use the command complete_binary_tree which

accepts n(a positive integer) as its only argument.

>complete_binary_tree(2)

an undirected unweighted graph with 7 vertices and 6 edges

To construct the complete k-ary tree of the speciﬁed depth use the command complete_kary_tree.

complete_kary_tree accepts kand n(positive integers) as its arguments and returns the complete

k-ary tree of depth n. For example, to get a ternary tree with two levels, input:

>complete_kary_tree(3,2)

an undirected unweighted graph with 13 vertices and 12 edges

14 Constructing graphs

2.5. Sequence graphs

2.5.1. Creating graphs from degree sequences

The command sequence_graph is used for constructing the graph from its degree sequence.

sequence_graph accepts a list Lof positive integers as its only argument and, if Lrepresents a

graphic sequence, the corresponding graph Gwith jLjvertices is returned. If the argument is not

a graphic sequence, an error is returned.

>sequence_graph([3,2,4,2,3,4,5,7])

an undirected unweighted graph with 8 vertices and 15 edges

The graph Gis constructed in O(jLj2log jLj)time by using the algorithm of Havel and Hakimi.

2.5.2. Validating graphic sequences

The command is_graphic_sequence is used to check whether a list of integers represents the

degree sequence of some graph or not.

is_graphic_sequence accepts a list Lof positive integers as its only argument and returns true if

there exists a graph G(V ; E)with degree sequence fdeg v:v2Vgequal to Land false otherwise.

The algorithm, which has the complexity O(jLj2), is based on the theorem of Erd®s and Gallai.

>is_graphic_sequence([3,2,4,2,3,4,5,7])

true

2.6. Intersection graphs

2.6.1. Interval graphs

The command interval_graph is used for construction of interval graphs.

interval_graph accepts a sequence or list of real-line intervals as its argument and returns an

undirected unweighted graph with these intervals as vertices (the string representations of the

intervals are used as labels), each two of them being connected with an edge if and only if the

corresponding intervals intersect.

>G:=interval_graph(0..8,1..pi,exp(1)..20,7..18,11..14,17..24,23..25)

an undirected unweighted graph with 7 vertices and 10 edges

>draw_graph(G)

2.6.2. Kneser graphs

The commands kneser_graph and odd_graph are used for construction of Kneser graphs.

2.6 Intersection graphs 15

kneser_graph accepts two positive integers n≤20 and kas its arguments and returns the Kneser

graph K(n; k). The latter is obtained by setting all k-subsets of a set of nelements as vertices

and connecting each two of them if and only if the corresponding sets are disjoint. Therefore each

Kneser graph is the complement of a certain intersection graph.

Kneser graphs can get exceedingly complex even for relatively small values of nand k. Note that

the number of vertices in K(n; k)is equal to n

k.

>kneser_graph(5,2)

an undirected unweighted graph with 10 vertices and 15 edges

>G:=kneser_graph(8,1)

an undirected unweighted graph with 8 vertices and 28 edges

>draw_graph(G,spring,labels=false)

The command odd_graph is used for creating so-called odd graphs, which are Kneser graphs with

parameters n= 2 d+ 1 and k=dfor d>1.

odd_graph accepts a positive integer d≤8as its only argument and returns d-th odd graph

K(2 d+ 1; d). Note that the odd graphs with d > 8will not be constructed as they are too big to

handle.

>odd_graph(3)

an undirected unweighted graph with 10 vertices and 15 edges

2.7. Special graphs

2.7.1. Hypercube graphs

The command hypercube_graph is used for creating hypercube graphs.

hypercube_graph accepts a positive integer nas its only argument and returns the hypercube

graph of dimension non 2nvertices. The vertex labels are strings of binary digits of length n.

Two vertices are joined by an edge if and only if their labels diﬀer in exactly one character. The

hypercube graph for n= 2 is a square and for n= 3 it is a cube.

>H:=hypercube_graph(3)

an undirected unweighted graph with 8 vertices and 12 edges

>draw_graph(H,planar)

16 Constructing graphs

>H:=hypercube_graph(5)

an undirected unweighted graph with 32 vertices and 80 edges

2.7.2. Star graphs

The command star_graph is used for creating star graphs.

star_graph accepts a positive integer nas its only argument and returns the star graph with n+ 1

vertices, which is equal to the complete bipartite graph complete_graph(1,n) i.e. a n-ary tree

with one level.

>G:=star_graph(5)

an undirected unweighted graph with 6 vertices and 5 edges

>draw_graph(G)

2.7.3. Wheel graphs

The command wheel_graph is used for creating wheel graphs.

wheel_graph accepts a positive integer nas its only argument and returns the wheel graph with

n+ 1 vertices.

>G:=wheel_graph(5)

an undirected unweighted graph with 6 vertices and 10 edges

>draw_graph(G)

2.7.4. Web graphs

The command web_graph is used for creating web graphs.

web_graph accepts two positive integers aand bas its arguments and returns the web graph with

parameters aand b, namely the Cartesian product of cycle_graph(a) and path_graph(b).

>G:=web_graph(7,3)

an undirected unweighted graph with 21 vertices and 35 edges

2.7 Special graphs 17

>draw_graph(G,labels=false)

2.7.5. Prism graphs

The command prism_graph is used for creating prism graphs.

prism_graph accepts a positive integer nas its only argument and returns the prism graph with

parameter n, namely petersen_graph(n,1).

>G:=prism_graph(5)

an undirected unweighted graph with 10 vertices and 15 edges

>draw_graph(G)

2.7.6. Antiprism graphs

The command antiprism_graph is used for creating antiprism graphs.

antiprism_graph accepts a positive integer nas its only argument and returns the antiprism

graph with parameter n, which is constructed from two concentric cycles of nvertices by joining

each vertex of the inner to two adjacent nodes of the outer cycle.

>G:=antiprism_graph(7)

an undirected unweighted graph with 14 vertices and 28 edges

>draw_graph(G)

2.7.7. Grid graphs

The command grid_graph resp. torus_grid_graph is used for creating rectangular resp. torus

grid graphs.

18 Constructing graphs

grid_graph accepts two positive integers mand nas its arguments and returns the mby ngrid

on m·nvertices, namely the Cartesian product of path_graph(m) and path_graph(n).

>G:=grid_graph(15,20)

an undirected unweighted graph with 300 vertices and 565 edges

>draw_graph(G,spring)

Connecting vertices in the opposite corners of the generated grid yields an interesting new graph.

>G:=add_edge(G,[["14:0","0:19"],["0:0","14:19"]])

an undirected unweighted graph with 300 vertices and 567 edges

>draw_graph(G,plot3d)

In the following example, the Möbius strip is constructed by connecting the vertices in the opppo-

site sides of a narrow grid graph.

>G:=grid_graph(20,3)

an undirected unweighted graph with 60 vertices and 97 edges

>G:=add_edge(G,[["0:0","19:2"],["0:1","19:1"],["0:2","19:0"]])

an undirected unweighted graph with 60 vertices and 100 edges

>draw_graph(G,plot3d,labels=false)

torus_grid_graph accepts two positive integers mand nas its arguments and returns the mby n

torus grid on m n vertices, namely the Cartesian product of cycle_graph(m) and cycle_graph(n).

>G:=torus_grid_graph(8,3)

an undirected unweighted graph with 24 vertices and 48 edges

>draw_graph(G,spring,labels=false)

2.7 Special graphs 19

2.7.8. Sierpi«ski graphs

The command sierpinski_graph is used for creating Sierpi«ski-type graphs Sk

nand STk

n[9].

sierpinski_graph accepts two positive integers nand kas its arguments (and optionally the

symbol triangle as the third argument) and returns the Sierpi«ski (triangle) graph with parame-

ters nand k.

The Sierpi«ski triangle graph STk

nis obtained by contracting all non-clique edges in Sk

n. To detect

such edges the variant of the algorithm by Bron and Kerbosch, developed by Tomita et al. in

[20], is used, which can be time consuming for n > 6.

In particular, ST3

nis the well-known Sierpi«ski sieve2.1 graph of order n.

>S:=sierpinski_graph(4,3)

an undirected unweighted graph with 81 vertices and 120 edges

>draw_graph(S,spring)

>sierpinski_graph(4,3,triangle)

an undirected unweighted graph with 42 vertices and 81 edges

>sierpinski_graph(5,3,triangle)

an undirected unweighted graph with 123 vertices and 243 edges

A drawing of the graph produced by the last command line is shown in Figure 4.1.

2.7.9. Generalized Petersen graphs

The command petersen_graph is used for creating generalized Petersen graphs P(n; k).

petersen_graph accepts two arguments, nand k(positive integers). The second argument may

be omitted, in which case k= 2 is assumed. The graph P(n; k), which is returned, is a connected

cubic graph consisting of—in Schläﬂi notation—an inner star polygon fn; kgand an outer regular

polygon fngsuch that the npairs of corresponding vertices in inner and outer polygons are

connected with edges. For k= 1 the prism graph of order nis obtained.

The well-known Petersen graph is equal to the generalized Petersen graph P(5;2). It can also be

constructed by calling graph("petersen").

2.1.https://en.wikipedia.org/wiki/Sierpinski_triangle

20 Constructing graphs

>draw_graph(graph("petersen"))

To obtain the dodecahedral graph P(10;2), input:

>petersen_graph(10)

an undirected unweighted graph with 20 vertices and 30 edges

To obtain Möbius–Kantor graph P(8;3), input:

>G:=petersen_graph(8,3)

an undirected unweighted graph with 16 vertices and 24 edges

>draw_graph(G)

0 1

2

3

45

6

78 9

10

11

1213

14

15

Note that Desargues, Dürer and Nauru graphs are also generalized Petersen graphs P(10;3),P(6;

2) and P(12;5), respectively.

2.7.10. LCF graphs

The command lcf_graph is used for constructing a cubic Hamiltonian graph from its LCF nota-

tion2.2.

lcf_graph takes one or two arguments, a list Lof nonzero integers, called jumps, and optionally

a positive integer n, called exponent (by default, n= 1). The command returns the graph on njLj

vertices obtained by iterating the sequence of jumps ntimes.

For example, the following command line creates the Frucht graph.

>F:=lcf_graph([-5,-2,-4,2,5,-2,2,5,-2,-5,4,2])

an undirected unweighted graph with 12 vertices and 18 edges

>draw_graph(F,planar)

2.2. For the details about LCF notation, see https://en.wikipedia.org/wiki/LCF_notation.

2.7 Special graphs 21

The following command line constructs the truncated octahedral graph.

>G:=lcf_graph([3,-7,7,-3],6)

an undirected unweighted graph with 24 vertices and 36 edges

>draw_graph(G,planar,labels=false)

2.8. Isomorphic copies of graphs

The commands isomorphic_copy,permute_vertices and relabel_vertices are used for con-

structing isomorphic copies of existing graphs.

2.8.1. Creating an isomorphic copy of a graph

The command isomorphic_copy accepts two arguments, a graph G(V ; E)and a permutation σ

of order jVj, and returns the copy of graph Gwith vertices rearranged according to σ.

>G:=isomorphic_copy(path_graph([1,2,3,4,5]),randperm(5))

an undirected unweighted graph with 5 vertices and 4 edges

>vertices(G)

[2;5;3;4;1]

2.8.2. Permuting graph vertices

The command permute_vertices accepts two arguments, a graph G(V ; E)and a list Lof length

jVjcontaining all vertices from Vin a certain order, and returns a copy of Gwith vertices

rearranged as speciﬁed by L.

>G:=permute_vertices(path_graph([a,b,c,d]),[b,d,a,c])

an undirected unweighted graph with 4 vertices and 3 edges

>vertices(G)

[b; d; a; c]

2.8.3. Relabeling graph vertices

The command relabel_vertices accepts two arguments, a graph G(V ; E)and a list Lof vertex

labels, and returns the copy of Gwith vertices relabeled with labels from L.

>P:=path_graph([1,2,3,4])

an undirected unweighted graph with 4 vertices and 3 edges

>edges(P)

22 Constructing graphs

f[1;2];[2;3];[3;4]g

>G:=relabel_vertices(P,[a,b,c,d])

an undirected unweighted graph with 4 vertices and 3 edges

>edges(G)

f[a; b];[b; c];[c; d]g

2.9. Subgraphs

2.9.1. Extracting subgraphs

To extract the subgraph of G(V ; E)formed by edges from L⊂E, use the command subgraph

which accepts two arguments: Gand L.

>K5:=complete_graph(5)

an undirected unweighted graph with 5 vertices and 10 edges

>S:=subgraph(K5,[[1,2],[2,3],[3,4],[4,1]])

an undirected unweighted graph with 4 vertices and 4 edges

>draw_graph(highlight_subgraph(K5,S))

2.9.2. Induced subgraphs

To obtain the subgraph of Ginduced by set of vertices L⊂V, use the command induced_sub-

graph.

induced_subgraph accepts two arguments Gand Land returns the subgraph of Gformed by all

edges in Ewhich have endpoints in L.

>G:=graph("petersen")

an undirected unweighted graph with 10 vertices and 15 edges

>S:=induced_subgraph(G,[5,6,7,8,9])

an undirected unweighted graph with 5 vertices and 5 edges

>draw_graph(highlight_subgraph(G,S))

2.9 Subgraphs 23

2.9.3. Underlying graphs

For every graph G(V ; E)there is an undirected and unweighted graph U(V ; E0), called the

underlying graph of G, where E0is obtained from Eby dropping edge directions.

To construct Uuse the command underlying_graph which accepts Gas its only argument. The

result is obtained by copying Gand “forgetting” the directions of edges as well as their weights.

>G:=digraph(%{[[1,2],6],[[2,3],4],[[3,1],5],[[3,2],7]%})

a directed weighted graph with 3 vertices and 4 arcs

>U:=underlying_graph(G)

an undirected unweighted graph with 3 vertices and 3 edges

>edges(U)

f[1;2];[1;3];[2;3]g

2.10. Operations on graphs

2.10.1. Graph complement

The command graph_complement is used for constructing complements of graphs.

graph_complement accepts a graph G(V ; E)as its only argument and returns the complement

Gc(V ; Ec)of G, where Ecis the largest set containing only edges/arcs not present in G.

>C5:=cycle_graph(5)

C5: an undirected unweighted graph with 5 vertices and 5 edges

>draw_graph(C5)

0

1

23

4

>G:=graph_complement(C5)

an undirected unweighted graph with 5 vertices and 5 edges

>draw_graph(G)

0

1

23

4

2.10.2. Seidel switching

The command seidel_switch is used for Seidel switching in graphs.

24 Constructing graphs

seidel_switch accepts two arguments, an undirected and unweighted graph G(V ; E)and a list

of vertices L⊂V. The result is a copy of Gin which, for each vertex v2L, its neighbors become

its non-neighbors and vice versa.

>S:=seidel_switch(cycle_graph(5),[1,2])

an undirected unweighted graph with 5 vertices and 7 edges

>draw_graph(S)

0

1

23

4

2.10.3. Transposing graphs

The command reverse_graph is used for reversing arc directions in digraphs.

reverse_graph accepts a graph G(V ; E)as its only argument and returns the reverse graph GT(V ;

E0)of Gwhere E0=f(j ; i): (i; j)2Eg, i.e. returns the copy of Gwith the directions of all edges

reversed.

Note that reverse_graph is deﬁned for both directed and undirected graphs, but gives meaningful

results only for directed graphs.

GTis also called the transpose graph of Gbecause adjacency matrices of Gand GTare transposes

of each other (hence the notation).

>G:=digraph(6, %{[1,2],[2,3],[2,4],[4,5]%})

a directed unweighted graph with 6 vertices and 4 arcs

>GT:=reverse_graph(G)

a directed unweighted graph with 6 vertices and 4 arcs

>edges(GT)

f[2;1];[3;2];[4;2];[5;4]g

2.10.4. Union of graphs

The command graph_union is used for constructing union of two or more graphs.

graph_union accepts a sequence of graphs Gk(Vk; Ek)for k= 1;2; :::; n as its argument and returns

the graph G(V ; E)where V=V1[V2[···[Vkand E=E1[E2[···[Ek.

>G1:=graph([1,2,3],%{[1,2],[2,3]%})

an undirected unweighted graph with 3 vertices and 2 edges

>G2:=graph([1,2,3],%{[3,1],[2,3]%})

an undirected unweighted graph with 3 vertices and 2 edges

>G:=graph_union(G1,G2)

an undirected unweighted graph with 3 vertices and 3 edges

>edges(G)

2.10 Operations on graphs 25

f[1;2];[1;3];[2;3]g

2.10.5. Disjoint union of graphs

To construct disjoint union of graphs use the command disjoint_union.

disjoint_union accepts a sequence of graphs Gk(Vk; Ek)for k= 1;2; :::; n as its argument and

returns the graph obtained by labeling all vertices with strings k:v where v2Vkand all edges with

strings k:e where e2Ekand calling the graph_union command subsequently. As all vertices and

edges are labeled diﬀerently, it follows jVj=Pk=1

njVkjand jEj=Pk=1

njEkj.

>G:=disjoint_union(cycle_graph([1,2,3]),path_graph([1,2,3]))

an undirected unweighted graph with 6 vertices and 5 edges

>draw_graph(G)

2.10.6. Joining two graphs

The command graph_join is used for joining graphs.

graph_join accepts two graphs Gand Has its arguments and returns the graph which is obtained

by connecting all the vertices of Gto all vertices of H. The vertex labels in the resulting graph

are strings of the form 1:u and 2:v where uis a vertex in Gand vis a vertex in H.

>G:=graph_join(path_graph(2),graph(3))

an undirected unweighted graph with 5 vertices and 7 edges

>draw_graph(G,spring)

1:0

1:1

2:0

2:1 2:2

2.10.7. Power graphs

The command graph_power is used for constructing the powers of a graph.

graph_power accepts two arguments, a graph G(V ; E)and a positive integer k, and returns the

k-th power Gkof Gwith vertices Vsuch that v; w 2Vare connected with an edge if and only if

there exists a path of length at most kin G.

The graph Gkis constructed from its adjacency matrix Akwhich is obtained by adding powers of

the adjacency matrix Aof G:

Ak=X

i=1

k

Ak:

26 Constructing graphs

The above sum is obtained by assigning Ak Aand repeating the instruction Ak (Ak+I)Afor

k¡1times, so exactly kmatrix multiplications are required.

>G:=graph(trail(1,2,3,4,5))

an undirected unweighted graph with 5 vertices and 4 edges

>draw_graph(G,circle)

>P2:=graph_power(G,2)

an undirected unweighted graph with 5 vertices and 7 edges

>draw_graph(P2,circle)

>P3:=graph_power(G,3)

an undirected unweighted graph with 5 vertices and 9 edges

>draw_graph(P3,circle)

2.10.8. Graph products

There are two distinct operations for computing the product of two graphs: Cartesian product and

tensor product. These operations are available in Giac as the commands cartesian_product and

tensor_product, respectively.

The command cartesian_product accepts a sequence of graphs Gk(Vk; Ek)for k= 1;2; :::; n as its

argument and returns the Cartesian product G1×G2×···×Gnof the input graphs. The Cartesian

product G(V ; E) = G1×G2is the graph with list of vertices V=V1×V2, labeled with strings v1:v2

where v12V1and v22V2, such that (u1:v1,u2:v2)2Eif and only if u1is adjacent to u2and v1=v2

or u1=u2and v1is adjacent to v2.

>G1:=graph(trail(1,2,3,4,1,5))

an undirected unweighted graph with 5 vertices and 5 edges

>draw_graph(G1,circle)

2.10 Operations on graphs 27

>G2:=star_graph(3)

an undirected unweighted graph with 4 vertices and 3 edges

>draw_graph(G2,circle=[1,2,3])

>G:=cartesian_product(G1,G2)

an undirected unweighted graph with 20 vertices and 35 edges

>draw_graph(G)

The command tensor_product accepts a sequence of graphs Gk(Vk; Ek)for k= 1;2; :::; n as its

argument and returns the tensor product G1×G2×···×Gnof the input graphs. The tensor product

G(V ; E) = G1×G2is the graph with list of vertices V=V1×V2, labeled with strings v1:v2 where

v12V1and v22V2, such that (u1:v1,u2:v2)2Eif and only if u1is adjacent to u2and v1is adjacent

to v2.

>T:=tensor_product(G1,G2)

an undirected unweighted graph with 20 vertices and 30 edges

>draw_graph(T)

2.10.9. Transitive closure graph

The command transitive_closure is used for constructing the transitive closure graph of the

given graph. Transitive closure of a (directed) graph G(V ; E)is the graph T(V ; E 0)in which two

vertices v; w 2Vare connected by an edge (arc) e=vw 2E0if and only if there exists a (directed)

path from vto win G.

28 Constructing graphs

transitive_closure accepts one or two arguments, the input graph Gand optionally the option

weighted=true (or simply weighted) or the option weighted=false (which is the default). The

command returns the transitive closure Tof the input graph G. If Gis a digraph, then Tis also a

digraph. When weighted=true is speciﬁed, the graph Tis weighted such that the weight of edge

v w 2E0is equal to the length (or weight, if Gis weighted) of the shortest path from vto win G.

The lengths/weights of the shortest paths are obtained by the command allpairs_distance if G

is weighted resp. the command vertex_distance if Gis unweighted. Therefore Tis constructed

in at most O(jVj3)time if weighted=true resp. O(jVjjEj)time if weighted=false.

>G:=digraph([1,2,3,4,5,6],%{[1,2],[2,3],[2,4],[4,5],[3,5]%})

a directed unweighted graph with 6 vertices and 5 arcs

>draw_graph(G)

>T:=transitive_closure(G,weighted)

a directed weighted graph with 6 vertices and 9 arcs

>draw_graph(T)

>G:=assign_edge_weights(G,1,99)

a directed weighted graph with 6 vertices and 5 arcs

>draw_graph(G)

>draw_graph(transitive_closure(G,weighted=true))

2.10 Operations on graphs 29

2.10.10. Line graph

The command line_graph is used for constructing the line graph of an undirected graph G(V ; E).

line_graph accepts the input graph Gas its only argument and returns the line graph L(G)with

jEjdistinct vertices, one vertex for each edge in E. Two vertices v1and v2in L(G)are adjacent if

and only if the corresponding edges e1; e22Ehave a common endpoint. The vertices in L(G)are

labeled with strings in form v-w, where e=vw 2E.

>K4:=complete_graph([1,2,3,4])

an undirected unweighted graph with 4 vertices and 6 edges

>L:=line_graph(K4)

an undirected unweighted graph with 6 vertices and 12 edges

>draw_graph(L,spring)

2.10.11. Plane dual graph

The command plane_dual is used for constructing the plane dual graph of an undirected bicon-

nected planar graph.

plane_dual accepts one argument, the input graph G(V ; E)or the list Fof faces of a planar

embedding of G, and returns the graph Hwith faces of Gas its vertices in which two vertices are

adjacent if and only if they share an edge as faces of G.

Note that the concept of dual graph is usually deﬁned for multigraphs2.3. By the strict deﬁnition,

every planar multigraph has the corresponding dual multigraph; moreover, the dual of the latter

is equal to the former. Since Giac does not support multigraphs, a simpliﬁed deﬁnition suitable

for simple graphs is used.

The algorithm runs in O(jVj2)time.

>H:=hypercube_graph(3)

an undirected unweighted graph with 8 vertices and 12 edges

>draw_graph(H,spring)

The cube has six faces, hence its plane dual graph Dhas six vertices. Also, every face obviously

shares an edge with exactly four other faces, so the degree of each vertex in Dis equal to 4.

>D:=plane_dual(H)

2.3. See https://en.wikipedia.org/wiki/Dual_graph for the strict deﬁnition of plane dual graph.

30 Constructing graphs

an undirected unweighted graph with 6 vertices and 12 edges

>draw_graph(D,spring)

A graph isomorphic to Dis obtained when passing a list of faces of Hto the plane_dual command.

The order of vertices is determined by the order of faces.

>is_planar(H,F)

Done;true

>plane_dual(F)

an undirected unweighted graph with 6 vertices and 12 edges

2.11. Random graphs

2.11.1. Random general graphs

The commands random_graph and random_digraph are used for generating general graphs at

random.

random_graph and random_digraph both accept two arguments. The ﬁrst argument is a positive

integer nor a list of labels Lof length n. The second argument is a positive real number p < 1or

a positive integer m. The command returns a random (di)graph on nvertices (using elements of

Las vertex labels) in which each edge/arc is inserted with probability por which contains exactly

medges/arcs chosen at random.

>G:=random_digraph(10,0.2)

a directed unweighted graph with 10 vertices and 15 arcs

>draw_graph(G,spring,labels=false)

>G:=random_graph(1000,0.01)

an undirected unweighted graph with 1000 vertices and 4922 edges

>is_connected(G)

true

>is_biconnected(G)

2.11 Random graphs 31

false

>G:=random_graph(100,99)

an undirected unweighted graph with 100 vertices and 99 edges

>is_tree(G)

false

>draw_graph(G,spring)

2.11.2. Random bipartite graphs

The command random_bipartite_graph is used for generating bipartite graphs at random.

random_bipartite_graph accepts two arguments. The ﬁrst argument is either a positive integer

nor a list of two positive integers aand b. The second argument is either a positive real number

p < 1or a positive integer m. The command returns a random bipartite graph on nvertices (or

with two partitions of sizes aand b) in which each possible edge is present with probability p(or

medges are inserted at random).

>G:=random_bipartite_graph([3,4],0.5)

an undirected unweighted graph with 7 vertices and 8 edges

>draw_graph(G)

>G:=random_bipartite_graph(30,60)

an undirected unweighted graph with 30 vertices and 60 edges

2.11.3. Random trees

The command random_tree is used for generating tree graphs uniformly at random.

random_tree accepts a positive integer nas its only argument and returns a random tree generated

on nnodes (i.e. inserts n¡1edges in the initially empty graph).

>T:=random_tree(30)

an undirected unweighted graph with 30 vertices and 29 edges

32 Constructing graphs

>draw_graph(T,labels=false)

2.11.4. Random planar graphs

The command random_planar_graph is used for generating random planar graphs, controlling

edge density and vertex connectivity.

random_planar_graph accepts two or three arguments, a positive integer n(or a list Lof length

n), a positive real number p < 1and optionally an integer k2f0;1;2;3g(by default, k= 1). The

command returns a random k-connected planar graph on nvertices (using elements of Las vertex

labels).

The result is obtained by ﬁrst generating a random maximal planar graph and then attempting

to remove each edge with probability p, maintaining the k-connectivity of the graph (if k= 0, the

graph may be disconnected). The running time is O(jVj)if k= 0,O(jVj2)if k2f1;2gand O(jVj3)

if k= 3.

The following command line generates a biconnected planar graph.

>G:=random_planar_graph(20,0.8,2)

an undirected unweighted graph with 20 vertices and 25 edges

>draw_graph(G,planar,labels=false)

The command line below generates a triconnected planar graph.

>G:=random_planar_graph(15,0.9,3)

an undirected unweighted graph with 15 vertices and 25 edges

>draw_graph(G,planar,labels=false)

The next command line generates a disconnected planar graph with high probability.

>G:=random_planar_graph(30,0.9,0)

an undirected unweighted graph with 30 vertices and 23 edges

>is_forest(G)

2.11 Random graphs 33

true

>draw_graph(G,spring,labels=false)

By default, a connected planar graph is generated, like in the following example.

>G:=random_planar_graph(15,0.618)

an undirected unweighted graph with 15 vertices and 19 edges

>is_connected(G)

true

>is_biconnected(G)

false

>articulation_points(G)

[1;2;4;10;11]

>draw_graph(G,planar)

2.11.5. Random regular graphs

The command random_regular_graph is used for generating random d-regular graphs on a certain

set of vertices, using the algorithm presented in [17]2.4.

random_regular_graph accepts two mandatory arguments, a positive integer n(or a list Lof

length n) and a nonnegative integer d. Optionally, the option connected may be speciﬁed as the

third argument, indicating that the generated graph must be 1-connected (by default no restriction

is made). The command creates nvertices (using elements of Las vertex labels) and returns a

random d-regular (connected) graph on these vertices.

Note that a d-regular graph on nvertices exists if and only if n > d + 1 and n d is even. If these

conditions are not met, random_regular_graph returns an error.

This algorithm generates regular graphs with approximately uniform probability. It means that

for n!1 and dnot growing so quickly with nthe probability distribution converges to uniformity.

The runtime of the algorithm is negligible for n6100. For n > 200 the algorithm is considerably

slower.

>G:=random_regular_graph(16,3)

an undirected unweighted graph with 16 vertices and 24 edges

2.4. See Algorithm 2 on page 2.

34 Constructing graphs

>is_regular(G)

true

>degree_sequence(G)

[3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3]

>draw_graph(G,spring)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

2.11.6. Random tournaments

The command random_tournament is used for generating random tournaments. A tournament of

order nis a graph obtained by assigning a direction to each edge in a complete graph Kn(for each

edge there are two possible directions).

random_tournament accepts a positive integer n(or a list Lof length n) as its only argument and

returns a random tournament on nvertices. If Lis speciﬁed, its elements are used to label the

vertices.

>G:=random_tournament([1,2,3,4])

a directed unweighted graph with 4 vertices and 6 arcs

>is_tournament(G)

true

>draw_graph(G)

2.11.7. Random ﬂow networks

Giac]

2.11.8. Randomizing edge weights

The command assign_edge_weights is used for assigning weights to edges of a graph at random.

assign_edge_weights accepts two or three arguments. The ﬁrst argument is always the input

graph G(V ; E). If only two arguments are given, the second one is an interval a..b of real numbers.

Otherwise, if three arguments are given, the second resp. the third argument is a positive integer

mresp. n. The command operates such that for each edge e2E, its weight is chosen uniformly

from the real interval [a; b)or from the set of integers lying between mand n, including both m

and n. After assigning weights to all edges, the modiﬁed copy of Gis returned.

2.11 Random graphs 35

>G:=assign_edge_weights(grid_graph(5,3),1,99)

an undirected weighted graph with 15 vertices and 22 edges

>draw_graph(G,spring)

>G:=assign_edge_weights(graph_complement(complete_graph(2,3,4)),e..pi)

an undirected weighted graph with 9 vertices and 10 edges

>draw_graph(G)

36 Constructing graphs

Chapter 3

Modifying graphs

3.1. Modifying vertices of a graph

3.1.1. Adding and removing single vertices

For adding and removing vertices to/from graphs use the commands add_vertex and

delete_vertex, respectively.

The command add_vertex accepts two arguments, a graph G(V ; E)and a single label vor a list

of labels L, and returns the graph G0(V[fvg; E)or G00 (V[L; E)if a list Lis given.

>K5:=complete_graph([1,2,3,4,5])

an undirected unweighted graph with 5 vertices and 10 edges

>add_vertex(K5,6)

an undirected unweighted graph with 6 vertices and 10 edges

>add_vertex(K5,[a,b,c])

an undirected unweighted graph with 8 vertices and 10 edges

Note that vertices already present in Gwon't be added. For example:

>add_vertex(K5,[4,5,6])

an undirected unweighted graph with 6 vertices and 10 edges

The command delete_vertex accepts two arguments, a graph G(V ; E)and a single label vor a

list of labels L, and returns the graph

G0(Vnfvg;fe2E:eis not incident to vg)

or, if Lis given,

G00 (VnL; fe2E:eis not incident to any v2Lg):

If any of the speciﬁed vertices does not belong to G, an error is returned.

>delete_vertex(K5,2)

an undirected unweighted graph with 4 vertices and 6 edges

>delete_vertex(K5,[2,3])

an undirected unweighted graph with 3 vertices and 3 edges

3.2. Modifying edges of a graph

3.2.1. Adding and removing single edges

For adding and removing edges or arcs to/from graphs use the commands add_edge or add_arc

and delete_edge and delete_arc, respectively.

37

The command add_edge accepts two arguments, an undirected graph G(V ; E)and an edge or a list

of edges or a trail of edges (entered as a list of vertices), and returns the copy of Gwith the speciﬁed

edges inserted. Edge insertion implies creation of its endpoints if they are not already present.

>C4:=cycle_graph(4)

C4: an undirected unweighted graph with 4 vertices and 4 edges

>add_edge(C4,[1,3])

C4: an undirected unweighted graph with 4 vertices and 5 edges

>add_edge(C4,[1,3,5,7])

C4: an undirected unweighted graph with 6 vertices and 7 edges

The command add_arc works similarly to add_edge but applies only to directed graphs. Note that

the order of endpoints in an arc matters.

>add_arc(digraph(trail(a,b,c,d,a)),[[a,c],[b,d]])

a directed unweighted graph with 4 vertices and 6 arcs

When adding edge/arc to a weighted graph, its weight should be speciﬁed alongside its endpoints,

or it will be assumed that it equals to 1.

>add_edge(graph(%{[[1,2],5],[[3,4],6]%}),[[2,3],7])

an undirected weighted graph with 4 vertices and 3 edges

3.2.2. Accessing and modifying edge weights

The commands get_edge_weight and set_edge_weight are used to access and modify the weight

of an edge/arc in a weighted graph, respectively.

set_edge_weight accepts three arguments: a weighted graph G(V ; E), edge/arc e2Eand the

new weight w, which may be any number. It returns the modiﬁed copy of G.

The command get_edge_weight accepts two arguments, a weighted graph G(V ; E)and an edge

or arc e2E. It returns the weight of e.

>G:=set_edge_weight(graph(%{[[1,2],4],[[2,3],5]%}),[1,2],6)

an undirected weighted graph with 3 vertices and 2 edges

>get_edge_weight(G,[1,2])

6

3.2.3. Contracting edges

The command contract_edge is used for contracting (collapsing) edges in a graph.

contract_edge accepts two arguments, a graph G(V ; E)and an edge/arc e= (v; w)2E, and

merges wand vinto a single vertex, deleting the edge e. The resulting vertex inherits the label of

v. The command returns the modiﬁed graph G0(Vnfwg; E0).

>K5:=complete_graph(5)

an undirected unweighted graph with 5 vertices and 10 edges

>contract_edge(K5,[1,2])

38 Modifying graphs

an undirected unweighted graph with 4 vertices and 6 edges

To contract a set fe1; e2; :::; ekg⊂Eof edges in G, none two of which are incident (i.e. when the

given set is a matching in G), one can use the foldl command. In the following example, the

complete graph K5is obtained from Petersen graph by edge contraction.

>P:=graph("petersen")

an undirected unweighted graph with 10 vertices and 15 edges

>G:=foldl(contract_edge,P,[0,5],[1,6],[2,7],[3,8],[4,9])

an undirected unweighted graph with 5 vertices and 10 edges

>draw_graph(G)

0

1

23

4

3.2.4. Subdividing edges

The command subdivide_edges is used for subdividing edges of a graph.

subdivide_edges accepts two or three arguments, a graph G(V ; E), a single edge/arc or a list

of edges/arcs in Eand optionally a positive integer r(which defaults to 1). Each of the speciﬁed

edges/arcs will be subdivided with exactly rnew vertices, labeled with the smallest available

integers. The resulting graph, which is homeomorphic to G, is returned.

If the endpoints of the edge being subdivided have valid coordinates, the coordinates of the inserted

vertices will be computed accordingly.

>G:=graph("petersen")

an undirected unweighted graph with 10 vertices and 15 edges

>G:=subdivide_edges(G,[2,3])

an undirected unweighted graph with 11 vertices and 16 edges

>G:=subdivide_edges(G,[[1,2],[3,4]])

an undirected unweighted graph with 13 vertices and 18 edges

>G:=subdivide_edges(G,[0,1],2)

an undirected unweighted graph with 15 vertices and 20 edges

>draw_graph(G)

0

1

23

4

5

6

78

9

10

11

12

13

14

3.2 Modifying edges of a graph 39

3.3. Using attributes

3.3.1. Graph attributes

The graph structure maintains a set of attributes as tag-value pairs which can be accessed and

modiﬁed by the user.

The command set_graph_attribute is used for modifying the existing graph attributes or adding

new ones. It accepts two arguments, a graph Gand a sequence or list of graph attributes in form

tag=value where tag is any string. Alternatively, attributes may be speciﬁed as a sequence of two

lists [tag1,tag2,...] and [value1,value2,...]. The command sets the speciﬁed values to the

indicated attribute slots, which are meant to represent some global properties of the graph G, and

returns the modiﬁed copy of G.

The previously set graph attribute values can be fetched with the command get_graph_attribute

which accepts two arguments: a graph Gand a sequence or list of tags. The corresponding values

will be returned in a sequence or list, respectively. If some attribute is not set, undef is returned

as its value.

To list all graph attributes of Gfor which the values are set, use the list_graph_attributes

command which takes Gas its only argument.

To discard a graph attribute, use the discard_graph_attribute command. It accepts two argu-

ments: a graph Gand a sequence or list of tags to be cleared, and returns the modiﬁed copy of G.

Two tags are normally being used by the CAS commands: directed and weighted, so it is not advis-

able to overwrite their values using this command (instead, use make_directed,make_weighted

and underlying_graph commands). Another attribute used internally is name, which holds the

name of the respective graph (as a string).

>G:=digraph(trail(1,2,3,1))

a directed unweighted graph with 3 vertices and 3 arcs

>G:=set_graph_attribute(G,"name"="C3","message"="this is some text")

C3: a directed unweighted graph with 3 vertices and 3 arcs

>get_graph_attribute(G,"message")

this is some text

>list_graph_attributes(G)

[directed =true;weighted =false;name =C3;message =this is some text]

>G:=discard_graph_attribute(G,"message")

C3: a directed unweighted graph with 3 vertices and 3 arcs

>list_graph_attributes(G)

[directed =true;weighted =false;name =C3]

3.3.2. Vertex attributes

For every vertex of a graph, the list of attributes in form of tag-value pairs is maintained, which

can be accessed and modiﬁed by the user.

The command set_vertex_attribute is used for modifying the existing vertex attributes or

adding new ones. It accepts three arguments, a graph G(V ; E), a vertex v2Vand a sequence or list

of attributes in form tag=value where tag is any string. Alternatively, attributes may be speciﬁed

as a sequence of two lists [tag1,tag2,...] and [value1,value2,...]. The command sets the

speciﬁed values to the indicated attributes of the vertex vand returns the modiﬁed copy of G.

40 Modifying graphs

The previously set attribute values for vcan be fetched with the command get_vertex_attribute

which accepts three arguments: G,vand a sequence or list of tags. The corresponding values will

be returned in a sequence or list, respectively. If some attribute is not set, undef is returned as

its value.

To list all attributes of vfor which the values are set, use the list_vertex_attributes command

which takes two arguments, Gand v.

The discard_vertex_attribute command is used for discarding attribute(s) assigned to some

vertex v2V. It accepts three arguments: G,vand a sequence or list of tags to be cleared, and

returns the modiﬁed copy of G.

The attributes label,color,shape and pos are also used internally. These hold the vertex label, color,

shape and coordinates in a drawing, respectively. If the color is not set for a vertex, the latter is

drawn in yellow. The shape attribute may have one of the following values: square,triangle,diamond,

star or plus. If the shape attribute is not set or has a diﬀerent value, the circled shape is applied

when drawing the vertex.

The following example shows how to change individual labels and colors.

>T:=complete_binary_tree(3)

an undirected unweighted graph with 15 vertices and 14 edges

>T:=set_vertex_attribute(T,5,"label"="root","color"=red)

an undirected unweighted graph with 15 vertices and 14 edges

>draw_graph(T,tree="root")

0

1

2

3 4

root

6

7 8 9 10

11 12

13 14

A vertex may also hold custom attributes.

>T:=set_vertex_attribute(T,"root","depth"=3,"shape"="square")

an undirected unweighted graph with 15 vertices and 14 edges

>list_vertex_attributes(T,"root")

[label =root;color =r e d; shape =square;depth = 3]

>T:=discard_vertex_attribute(T,"root","color")

an undirected unweighted graph with 15 vertices and 14 edges

>list_vertex_attributes(T,"root")

[label =root;shape =square;depth = 3]

3.3.3. Edge attributes

For every edge of a graph, the list of attributes in form of key-value pairs is maintained, which can

be accessed and modiﬁed by the user.

The command set_edge_attribute is used for modifying the existing edge attributes or adding

new ones. It accepts three arguments, a graph G(V ; E), an edge/arc e2Eand a sequence or list

of attributes in form tag=value where tag is any string. Alternatively, attributes may be speciﬁed

as a sequence of two lists [tag1,tag2,...] and [value1,value2,...]. The command sets the

speciﬁed values to the indicated attributes of the edge/arc eand returns the modiﬁed copy of G.

3.3 Using attributes 41

The previously set attribute values for ecan be fetched with the command get_edge_attribute

which accepts three arguments: G,eand a sequence or list of tags. The corresponding values will

be returned in a sequence or list, respectively. If some attribute is not set, undef is returned as

its value.

To list all attributes of efor which the values are set, use the list_edge_attributes command

which takes two arguments, Gand e.

To discard attribute(s) assigned to ecall the discard_edge_attribute command, which accepts

three arguments: G,eand a sequence or list of tags to be cleared, and returns the modiﬁed copy

of G.

The attributes weight,color,style,pos and temp are also used internally. They hold the edge weight,

color, line style, the coordinates of the weight label anchor (and also the coordinates of the arrow)

and true if the edge is temporary. If the color attribute is not set for an edge, the latter is drawn

in blue, unless it is a temporary edge, in which case it is drawn in light grey. The style attribute

may have one of the following values: dashed,dotted or bold. If the style attribute is not set or has

a diﬀerent value, the solid line style is applied when drawing the edge.

The following example illustrates the possibilities of using edge attributes.

>T:=complete_binary_tree(3)

an undirected unweighted graph with 15 vertices and 14 edges

>T:=set_edge_attribute(T,[1,4],"cost"=12.8,"message"="this is some text")

an undirected unweighted graph with 15 vertices and 14 edges

>list_edge_attributes(T,[1,4])

[cost =12.8;message =this is some text]

>T:=discard_edge_attribute(T,[1,4],"message")

an undirected unweighted graph with 15 vertices and 14 edges

>T:=set_edge_attribute(T,[1,4],"style"="dotted","color"=magenta)

an undirected unweighted graph with 15 vertices and 14 edges

>list_edge_attributes(T,[1,4])

[color =m a g e n t a; style =dotted;cost =12.8]

>T:=set_edge_attribute(T,[5,11],"temp"=true)

an undirected unweighted graph with 15 vertices and 14 edges

>draw_graph(T)

0

1 2

3 4 5 6

7 8 9 10 11 12 13 14

42 Modifying graphs

Chapter 4

Import and export

4.1. Importing graphs

4.1.1. Loading graphs from dot ﬁles

The command import_graph is used for importing a graph from text ﬁle in dot format4.1.

import_graph accepts a string filename as its only argument and returns the graph constructed

from instructions written in the ﬁle filename or undef on failure. The passed string should contain

the path to a ﬁle in dot format. The ﬁle extension .dot may be omitted in the filename since dot

is the only supported format. The alternative extension is .gv,4.2 which must be explicitly speciﬁed.

If a relative path to the ﬁle is speciﬁed, i.e. if it does not contain a leading forward slash, the

current working directory (which can be obtained by calling the pwd command) will be used as the

reference. The working directory can be changed by using the command cd.

For example, assume that the ﬁle example.dot is saved in the directory Documents/dot/ with the

following contents:

graph "Example graph" {

a [label="Foo"];

b [shape=diamond,color=red];

a -- b [style=bold];

b -- c [color=green];

b -- d [style=dotted];

}

To import the graph, input:

>G:=import_graph("Documents/dot/example.dot")

Example graph: an undirected unweighted graph with 4 vertices and 3 edges

>draw_graph(G)

Foo

b

c d

4.1.2. The dot ﬁle format overview

Giac has some basic support for dot language4.3. Each dot ﬁle is used to hold exactly one graph

and should consist of a single instance of the following environment:

strict? (graph | digraph) name? {

...

}

4.1.https://en.wikipedia.org/wiki/DOT_(graph_description_language)

4.2. Although it is recommended to use .gv as the extension for dot ﬁles to avoid a certain confusion between diﬀerent

ﬁle types, Giac uses the .dot extension because it coincides with the format name. This may change in the future.

4.3. For the complete syntax deﬁnition see https://www.graphviz.org/doc/info/lang.html.

43

The keyword strict may be omitted, as well as the name of the graph, as indicated by the question

marks. The former is used to diﬀerentiate between simple graphs (strict) and multigraphs (non-

strict). Since Giac supports only simple graphs, strict is redundant.

For specifying undirected graphs the keyword graph is used, while the digraph keyword is used

for undirected graphs.

The graph/digraph environment contains a series of instructions describing how the graph should

be built. Each instruction ends with the semicolon (;) and has one of the following forms.

syntax creates

vertex_name [attributes]? isolated vertices

V1 <edgeop> V2 <edgeop> ::: <edgeop> Vk [attributes]? edges and trails

graph [attributes] graph attributes

Here, attributes is a comma-separated list of tag-value pairs in form tag=value,<edgeop> is

-- for undirected and -> for directed graphs. Each of V1,V2 etc. is either a vertex name or a set

of vertex names in form {vertex_name1 vertex_name2 ...}. In the case a set is speciﬁed, each

vertex from that set is connected to the neighbor operands. Every speciﬁed vertex will be created

if it does not exist yet.

Any line beginning with #is ignored. C-like line and block comments are recognized and skipped

as well.

Using the dot syntax it is easy to specify a graph with adjacency lists. For example, the following

is the contents of a ﬁle which deﬁnes the octahedral graph with 6 vertices and 12 edges.

# octahedral graph

graph "octahedron" {

1 -- {3 6 5 4};

2 -- {3 4 5 6};

3 -- {5 6};

4 -- {5 6};

}

4.2. Exporting graphs

The command export_graph is used for saving graphs to disk in dot or L

ATE

X format.

4.2.1. Saving graphs in dot format

export_graph accepts two mandatory arguments, a graph Gand a string filename, and writes G

to the ﬁle speciﬁed by filename, which must be a path to the ﬁle, either relative or absolute; in

the former case the current working directory will be used as the reference. If only two arguments

are given the graph is saved in dot format. The ﬁle name may be entered with or without .dot

extension. The command returns 1 on success and 0 on failure.

>export_graph(G,"Documents/dot/copy_of_philosophers")

1

4.2.2. Saving graph drawings in L

A

TE

X format

When calling the export_graph command, an optional third argument in form latex[=<params>]

may be given. In that case the drawing of G(obtained by calling the draw_graph command) will

be saved to the L

ATE

X ﬁle indicated by filename (the extension .tex may be omitted). Optionally,

one can specify a parameter or list of parameters params which will be passed to the draw_graph

command.

44 Import and export

For example, let us create a picture of the Sierpi«ski sieve graph of order n= 5, i.e. the graph ST3

5.

>G:=sierpinski_graph(5,3,triangle)

an undirected unweighted graph with 123 vertices and 243 edges

>export_graph(G,"Documents/st53.tex",latex=[spring,labels=false])

1

The L

ATE

X ﬁle obtained by exporting a graph is easily converted into an EPS ﬁle, which can

subsequently be inserted4.4 in a paper, report or some other document. A Linux user simply needs

to launch a terminal emulator, navigate to the directory in which the exported ﬁle, in this case

st53.tex, is stored and enter the following command:

latex st53.tex && dvips st53.dvi && ps2eps st53.ps

This will produce the (properly cropped) st53.eps ﬁle in the same directory. Afterwards, it is

recommended to enter

rm st53.tex st53.aux st53.log st53.dvi st53.ps

to delete the intermediate ﬁles. The above two commands can be combined in a simple shell script

which takes the name of the exported ﬁle (without the extension) as its input argument:

#!/bin/bash

# convert LaTeX to EPS

latex $1.tex

dvips $1.dvi

ps2eps $1.ps

rm $1.tex $1.aux $1.log $1.dvi $1.ps

Assuming that the script is stored under the name latex2eps in the same directory as st53.tex,

to do the conversion it is enough to input:

bash latex2eps st53

The drawing produced in our example is shown in Figure 4.1.

Fig. 4.1. drawing of the Sierpi«ski graph ST3

5using L

AT

E

X and PSTricks

4.4. Alternatively, a PSTricks picture from the body of the .tex ﬁle can be copied to some other L

AT

E

X document.

4.2 Exporting graphs 45

Chapter 5

Graph properties

5.1. Basic properties

5.1.1. Listing vertices and edges

The command vertices or graph_vertices resp. edges is used for extracting set of vertices

resp. set of edges from a graph.

vertices or graph_vertices accepts a graph G(V ; E)as its only argument and returns the set

of vertices Vin the same order in which they were created.

edges accepts one or two arguments, a graph G(V ; E)and optionally the identiﬁer weights. The

command returns the set of edges E(in a non-meaningful order). If weights is speciﬁed, each edge

is paired with the corresponding weight (in this case Gmust be a weighted graph).

>G:=hypercube_graph(2)

an undirected unweighted graph with 4 vertices and 4 edges

>vertices(G)

[00;01;10;11]

>C:=graph("coxeter")

an undirected unweighted graph with 28 vertices and 42 edges

>vertices(C)

[a1; a2; a7; z1; a3; z2; a4; z3; a5; z4; a6; z5; z6; z7; b1; b3; b6; b2; b4; b7; b5; c1; c4; c5; c2; c6; c3; c7]

>H:=digraph([[0,2.32,0,0.25],[0,0,0,1.32],[0,0.50,0,0],[0.75,0,3.34,0]])

a directed weighted graph with 4 vertices and 6 arcs

>edges(H)

f[0;1];[0;3];[1;3];[2;1];[3;0];[3;2]g

>edges(H,weights)

f[[0;1];2.32];[[0;3];0.25];[[1;3];1.32];[[2;1];0.5];[[3;0];0.75];[[3;2];3.34]g

5.1.2. Vertex degrees

The command vertex_degree is used for computing the degree of a vertex, i.e. counting the

vertices adjacent to it.

vertex_degree accepts two arguments, a graph G(V ; E)and a vertex v2V, and returns the

cardinality of the set fw2V: (v; w)2Eg, i.e. the number of vertices in Vwhich are adjacent to v.

When dealing with directed graphs, one can also use the specialized command vertex_in_degree

resp. vertex_out_degree which accepts the same arguments as vertex_degree but returns the

number of arcs (w; v)2Eresp. the number of arcs (v; w)2E, where w2V.

>G:=graph(trail(1,2,3,4,1,5,6,7,1,8,9,4))

47

an undirected unweighted graph with 9 vertices and 11 edges

>draw_graph(G)

>vertex_degree(G,1)

5

>T:=random_tournament([1,2,3,4,5])

a directed unweighted graph with 5 vertices and 10 arcs

>draw_graph(T)

>vertex_out_degree(T,1)

3

>vertex_in_degree(T,5)

2

To obtain the list of degrees of all vertices v2V, use the degree_sequence command.

degree_sequence accepts a graph G(V ; E)as its only argument and returns the list of degrees of

vertices from Vin the same order as returned by the command vertices. If Gis a digraph, arc

directions are ignored.

>degree_sequence(G)

[5;2;2;3;2;2;2;2;2]

5.1.3. Vertex adjacency

The command has_edge is used for checking if two vertices in an undirected graph are adjacent

or not.

has_edge accepts two arguments, the input graph G(V ; E)and a list [u,v] where u; v 2V. The

command returns true if uv 2Eand false otherwise.

For digraphs, there is the similar command has_arc with the same input syntax. Note, however,

that the order of vertices uand vmatters this time.

>G:=graph(trail(1,2,3,4,5,2))

an undirected unweighted graph with 5 vertices and 5 edges

>has_edge(G,[1,2])

true

48 Graph properties

>has_edge(G,[2,1])

true

>has_edge(G,[1,3])

false

>D:=digraph(trail(1,2,3,4,5,2))

a directed unweighted graph with 5 vertices and 5 arcs

>has_arc(D,[1,2])

true

>has_arc(D,[2,1])

false

The command neighbors is used for obtaining the list of vertices in a graph that are adjacent to

the particular vertex or the complete adjacency structure of the graph, in sparse form.

neighbors accepts one or two arguments. The ﬁrst, mandatory argument is the input graph

G(V ; E). The second, optional argument is a vertex v2V. The command returns the list of

neighbors of vin Gif vis given and the list of lists of neighbors for all vertices in V, in order of

vertices(G), otherwise.

Note that neighbors works for undirected as well as for directed graphs, but ignores edge directions

in the latter case.

>neighbors(G,3)

[2;4]

>neighbors(G)

f[2];[1;3;5];[2;4];[3;5];[2;4]g

The command departures resp. arrivals is used for determining all neighbors of a vertex vin a

digraph which are the heads resp. the tails of the corresponding arcs.

departures resp. arrivals accepts one or two arguments, the input digraph G(V ; E)and option-

ally a vertex v2V, and returns the list Lvcontaining all vertices w2Vfor which v w 2E

resp. wv 2E. If vis omitted, the list of lists Lvfor every v2Vis returned.

>G:=digraph(trail(1,2,3,4,2,5,1,6,7,8,4))

a directed unweighted graph with 8 vertices and 10 arcs

>draw_graph(G,spring)

1

2

3

4

5

6

7

8

>departures(G,2); arrivals(G,2); departures(G,1); arrivals(G,1)

[3;5];[1;4];[2;6];[5]

5.1.4. Edge incidence

The command incident_edges is used for obtaining edges incident to the given vertex in a graph.

5.1 Basic properties 49

incident_edges accepts two argument, the input graph G(V ; E)and a vertex v2Vor a list of

vertices L⊂V. The command returns the list of edges e1; e2; :::; ek2Ewhich have vas one of its

endpoints.

Note that edge directions are ignored when Gis a digraph. To obtain only outgoing or incoming

edges, use the commands departures and arrivals, respectively.

>G:=cycle_graph([1,2,3,4,5])

C5: an undirected unweighted graph with 5 vertices and 5 edges

>incident_edges(G,1)

f[1;2];[1;5]g

>incident_edges(G,[2,4,5])

f[1;2];[1;5];[2;3];[3;4];[4;5]g

>G:=random_tournament([1,2,3,4,5])

a directed unweighted graph with 5 vertices and 10 arcs

>incident_edges(G,2)

f[2;1];[2;3];[2;5];[4;2]g

5.2. Algebraic properties

5.2.1. Adjacency matrix

The command adjacency_matrix is used for obtaining the adjacency matrix of a graph G(V ; E)

where V=fv1; v2; :::; vng.

adjacency_matrix accepts the input graph Gas its only argument and returns the square matrix

A= [aij]of order nsuch that, for i; j = 1;2; :::; n,

aij =1, if the set Econtains edge/arc vivj,

0;otherwise:

Note that tr (A) = 0. Also, the adjacency matrix of an undirected graph is always symmetrical.

>G:=graph("octahedron")

an undirected unweighted graph with 6 vertices and 12 edges

>A:=adjacency_matrix(G)

0

B

B

B

B

B

B

@

011110

101101

110011

110011

101101

011110

1

C

C

C

C

C

C

A

>transpose(A)==A

true

>D:=digraph(trail(1,2,3,4,5,2,6,7,3,8,1))

a directed unweighted graph with 8 vertices and 10 arcs

50 Graph properties

>draw_graph(D)

1

2

3

4

5 6

7 8

>A:=adjacency_matrix(D)

0

B

B

B

B

B

B

B

B

B

B

@

01000000

00100100

00010001

00001000

01000000

00000010

00100000

10000000

1

C

C

C

C

C

C

C

C

C

C

A

>transpose(A)==A

false

5.2.2. Weight matrix

The command weight_matrix is used for obtaining the weight matrix of a weighted graph G(V ; E)

where V=fv1; v2; :::; vng.

weight_matrix accepts the input graph Gas its only argument and returns the square matrix

M= [mij]of order nsuch that mij equals zero if viand vjare not adjacent and the weight of the

edge/arc vivjotherwise, for all i; j = 1;2; :::; n (note that the weight of an edge/arc may be any

real number).

Note that tr (M) = 0. Also, the weight matrix of an undirected graph is always symmetrical.

>G:=graph(%{[[1,2],1],[[2,3],2],[[4,5],3],[[5,2],4]%})

an undirected weighted graph with 5 vertices and 4 edges

>weight_matrix(G)

0

B

B

B

B

@

01000

10204

02000

00003

04030

1

C

C

C

C

A

5.2.3. Incidence matrix

The command incidence_matrix is used for obtaining the incidence matrix of a graph.

incidence_matrix accepts the input graph G(V ; E), where V=fv1; v2; :::; vngand E=fe1; e2; :::;

emg, as its only argument and returns the n×mmatrix B= [bi j]such that, for all i= 1;2; :::; n

and j= 1;2; :::; m,

bij =1;if the vertex viis incident to the edge ej,

0;otherwise

5.2 Algebraic properties 51

if Gis undirected resp.

bij =8

<

:

1;if the vertex viis the head of the arc ej,

¡1;if the vertex viis the tail of the arc ej,

0;otherwise

if Gis directed.

>K4:=complete_graph([1,2,3,4])

an undirected unweighted graph with 4 vertices and 6 edges

>edges(K4)

f[1;2];[1;3];[1;4];[2;3];[2;4];[3;4]g

>incidence_matrix(K4)

0

B

B

@

111000

100110

010101

001011

1

C

C

A

>DG:=digraph(trail(1,2,3,4,5,3),trail(1,5,2,4,1))

a directed unweighted graph with 5 vertices and 9 arcs

>draw_graph(DG)

1

2

34

5

>edges(DG)

f[1;2];[1;5];[2;3];[2;4];[3;4];[4;1];[4;5];[5;2];[5;3]g

>incidence_matrix(DG)

0

B

B

B

B

@

¡1¡10001000

1 0 ¡1¡100010

0010¡10001

00011¡1¡1 0 0

0100001¡1¡1

1

C

C

C

C

A

5.2.4. Characteristic polynomial

The command graph_charpoly or charpoly is used for obtaining the characteristic polynomial

of an undirected graph.

graph_charpoly or charpoly accepts one or two arguments, the input graph G(V ; E)and option-

ally a value or symbol x. The command returns p(x), where pis the characteristic polynomial of

the adjacency matrix of G.

>G:=graph(%{[1,2],[2,3]%})

an undirected unweighted graph with 3 vertices and 2 edges

>charpoly(G,x)

52 Graph properties

x3¡2x

>charpoly(G,3)

21

>G:=graph("shrikhande")

an undirected unweighted graph with 16 vertices and 48 edges

>charpoly(G,x)

x16 ¡48 x14 ¡64 x13 +768 x12 +1536 x11 ¡5888 x10 ¡15360 x9+23040 x8+81920 x7¡

36864 x6¡245760 x5¡32768 x4+393216 x3+196608 x2¡262144 x¡196608

5.2.5. Graph spectrum

The command graph_spectrum is used for obtaining the spectrum of eigenvalues of a graph.

graph_spectrum accepts the input graph Gas its only argument and returns the list in which

every element is an eigenvalue of the adjacency matrix of Gpaired with its multiplicity.

>C5:=cycle_graph(5)

C5: an undirected unweighted graph with 5 vertices and 5 edges

>gs:=graph_spectrum(C5)

0

B

B

B

B

@

2 1

5

p¡1

22

¡5

p¡1

22

1

C

C

C

C

A

>p:=charpoly(C5,x)

x5¡5x3+ 5 x¡2

>expand(roots(p))==expand(gs)

true

The last result indicates that gs and roots(p) are equal.

5.2.6. Seidel spectrum

The command seidel_spectrum is used for obtaining the Seidel spectrum of a graph.

seidel_spectrum accepts the input graph G(V ; E)as its only argument and returns the list in

which every element is an eigenvalue of the matrix J¡I¡2Apaired with its multiplicity. Here Jis

all-one n×nmatrix, Iis the identity matrix of order n,Ais the adjacency matrix of Gand n=jVj.

>G:=graph("clebsch")

an undirected unweighted graph with 16 vertices and 40 edges

>seidel_spectrum(G)

¡310

5 6

>P:=graph("petersen")

an undirected unweighted graph with 10 vertices and 15 edges

5.2 Algebraic properties 53

>seidel_spectrum(P)

¡3 5

3 5

5.2.7. Integer graphs

The command is_integer_graph is used for determining if a graph is an integer graph, i.e. if its

spectrum consists only of integers.

is_integer_graph accepts the input graph Gas its only argument. The return value is true if

Gis an integer graph and false otherwise.

>G:=graph("levi")

an undirected unweighted graph with 30 vertices and 45 edges

>is_integer_graph(G)

true

>factor(charpoly(G,x))

x10 (x¡3) (x¡2)9(x+ 2)9(x+ 3)

5.3. Connectivity

5.3.1. Vertex connectivity

The commands is_connected,is_biconnected and is_triconnected are used for determining

if a graph is connected, biconnected or triconnected, respectively.

All three commands accept only one argument, the input graph G(V ; E). They return true if G

possesses the required type of connectivity and false otherwise.

Gis connected or 1-connected if for every pair v; w 2Vthere exists a path with endpoints uand

vin Gor in the underlying graph of Gif the latter is directed.

Gis biconnected or 2-connected if it remains connected after removing a vertex from G.

Gis triconnected or 3-connected if it remains connected after removing a pair of distinct vertices

from G.

The strategy for checking 1- and 2-connectivity is to use depth-ﬁrst search (see [7] and [18]). Both

algorithms run in O(jVj+jEj)time. The algorithm for checking 3-connectivity is quite simple but

less eﬃcient: it works by choosing a vertex v2Vand checking if the subgraph induced by Vnfvg

is biconnected, moving on to the next vertex if so, and repeating the process until all vertices are

visited exactly once or a non-biconnected subgraph is found for some v. In the latter case the input

graph is not triconnected. The complexity of this algorithm is O(jVjjEj).

>G:=graph_complement(complete_graph(2,3,4))

an undirected unweighted graph with 9 vertices and 10 edges

>is_connected(G)

false

>C:=connected_components(G)

f[0;1];[2;3;4];[5;6;7;8]g

>H:=induced_subgraph(G,C[2])

54 Graph properties

an undirected unweighted graph with 4 vertices and 6 edges

>is_connected(H)

true

>is_biconnected(path_graph(5))

false

>is_biconnected(cycle_graph(5))

true

>is_triconnected(graph("petersen"))

true

>is_triconnected(cycle_graph(5))

false

5.3.2. Connected and biconnected components

The command connected_components resp. biconnected_components is used for decomposing

a graph into connected resp. biconnected components.

connected_components resp. biconnected_components accept the input graph G(V ; E)as its

only argument and returns the minimal partition fV1; V2; :::; Vkgof Vsuch that the subgraph Gi⊂G

induced by Viis connected resp. biconnected for each i= 1;2; :::; k. The partition is returned as a

list of lists V1; V2; :::; Vk.

The connected components of Gare easily obtained by depth-ﬁrst search in O(jVj+jEj)time. To

ﬁnd the biconnected components of G,Tarjan's algorithm is used [18], which also runs in linear

time.

>G:=graph_complement(complete_graph(3,5,7))

an undirected unweighted graph with 15 vertices and 34 edges

>is_connected(G)

false

>C:=connected_components(G)

f[0;1;2];[3;4;5;6;7];[8;9;10;11;12;13;14]g

>G:=highlight_subgraph(G,induced_subgraph(G,C[1]))

an undirected unweighted graph with 15 vertices and 34 edges

>G:=highlight_subgraph(G,induced_subgraph(G,C[2]),magenta,cyan)

an undirected unweighted graph with 15 vertices and 34 edges

>draw_graph(G)

0

12

3

4

56

7

8

9

10

1112

13

14

>H:=graph(trail(1,2,3,4,2),trail(4,5,6,7,5))

an undirected unweighted graph with 7 vertices and 8 edges

5.3 Connectivity 55

>draw_graph(H)

1

2

3

45

6

7

>is_biconnected(H)

false

>biconnected_components(H)

f[1;2];[2;3;4];[4;5];[5;6;7]g

5.3.3. Graph rank

The command graph_rank is used for computing the rank of a graph.

graph_rank accepts one or two arguments, the input graph G(V ; E)and optionally a set of edges

S⊂E(by default S=E), and returns jVj¡kwhere kis the number of connected components of

the spanning subgraph of Gwith edge set S.

>G:=graph(%{[1,2],[3,4],[4,5]%})

an undirected unweighted graph with 5 vertices and 3 edges

>graph_rank(G)

3

>graph_rank(G,[[1,2],[3,4]])

2

5.3.4. Articulation points

The command articulation_points is used for obtaining the articulation points of a graph,

i.e. cut vertices, if any.

articulation_points accepts the input graph G(V ; E)as its only argument and returns the list

of articulation points of G. A vertex v2Vis an articulation point of Gif the subgraph H⊂G

induced by Vnfvgis disconnected.

The articulation points of Gare found by depth-ﬁrst serach in O(jVj+jEj)time [7].

>articulation_points(path_graph([1,2,3,4]))

[2;3]

>articulation_points(cycle_graph(1,2,3,4))

[]

5.3.5. Strongly connected components

The command strongly_connected_components is used for decomposing a graph into strongly

connected components. A (di)graph His strongly connected if for each pair (v; w)of distinct

vertices in Hthere is a (directed) path from vto win H.

56 Graph properties

strongly_connected_components accepts the input graph G(V ; E)as its only argument and

returns the minimal partition fV1; V2; :::; Vkgof Vsuch that the subgraph Gi⊂Ginduced by Viis

strongly connected for each i= 1;2; :::; k. The result is returned as a list of lists V1; V2; :::; Vk.

The strategy is to use Tarjan's algorithm for strongly connected components [18], which runs in

O(jVj+jEj)time.

Note that an undirected graph is strongly connected if and only if it is connected.

The command is_strongly_connected can be used to determine if the given graph Gis strongly

connected. It accepts Gas its only argument and returns true if Ghas exactly one strongly

connected component and false otherwise.

>G:=digraph([1,2,3],%{[1,2],[1,3],[2,3],[3,2]%})

a directed unweighted graph with 3 vertices and 4 arcs

>draw_graph(G)

1

23

>is_connected(G)

true

>is_strongly_connected(G)

false

>strongly_connected_components(G)

f[1];[2;3]g

5.3.6. Edge connectivity

5.4. Trees

5.4.1. Tree graphs

The command is_tree is used for determining if the particular graph is a tree. An undirected

graph G(V ; E)is a tree if jVj=jEj+ 1 and Gis connected.

is_tree accepts the input graph Gas its only argument and returns true if Gis a tree and false

otherwise.

The only expensive step in the algorithm is determining whether Gis connected. The condition

jVj=jEj+ 1 is checked ﬁrst, hence the algorithm runs in O(jVj)time.

>is_tree(complete_binary_tree(3))

true

>is_tree(cycle_graph(5))

false

5.4 Trees 57

5.4.2. Forest graphs

The command is_forest is used for determining if the particular graph is a forest, i.e. if its

connected components are all trees.

is_forest accepts the input graph Gas its only argument and returns true if Gis a forest and

false otherwise.

The only expensive step in the algorithm is the decomposition of Gto connected components.

Therefore the algorithm runs in O(jVj+jEj)time.

>L:=[]:; for k from 10 to 30 do L.append(random_tree(k)); od:;

Done;Done

>G:=disjoint_union(op(L))

an undirected unweighted graph with 420 vertices and 399 edges

>is_connected(G)

false

>is_forest(G)

true

5.4.3. Height of a tree

The command tree_height is used for determining the height of a tree with respect to the speciﬁed

root node. The height of a tree is the length of the longest path in that tree that has the root node

as one of its endpoints.

tree_height accepts two arguments, the input tree graph G(V ; E)and a vertex r2V, which is

used as the root node. The command returns the height of Gwith respect to r.

The strategy is to start a depth-ﬁrst search from the root node and look for the deepest node.

Therefore the algorithm runs in O(jVj)time.

>G:=random_tree(1000)

an undirected unweighted graph with 1000 vertices and 999 edges

>r:=rand(1000)

296

>tree_height(G,r)

20

5.4.4. Lowest common ancestor of a pair of nodes

The command lowest_common_ancestor determines the lowest common ancestor (LCA) of a pair

of nodes in a tree, or for every element of a list of such pairs.

lowest_common_ancestor accepts two mandatory arguments, the input tree graph G(V ; E)and

the root node r2V. There are two possibilities for specifying the nodes to operate on: either the

nodes u; v 2Vare given as the third and the fourth argument, or a list of pairs of nodes in form

[[u1,v1],[u2,v2],...,[uk,vk]], where ui; vi2Vand ui=/ vifor i= 1;2; :::; k, is given as the

third argument. The command returns the LCA of uand vor the list containing LCA of every

pair of nodes ui; vifor i= 1;2; :::; k.

The strategy is to use Tarjan's oﬄine LCA algorithm [19]. The implementation is simple and

uses the disjoint-set (union-ﬁnd) data structure. It runs in nearly linear time.

58 Graph properties

In the following example, the algorithm eﬃciency is tested on a large random tree with 10000 nodes.

The lowest common ancestors for the list Lcotaining 100 pairs of vertices, chosen at random, need

to be determined.

>G:=random_tree(10000)

an undirected unweighted graph with 10000 vertices and 9999 edges

3.562 sec

>V:=vertices(G):; L:=[]:; for k from 1 to 100 do L.append(rand(2,V)); od:;

Done;Done;Done

>lowest_common_ancestor(G,0,L):;

9.409 sec

5.5. Distance

5.5.1. Vertex distance

The command vertex_distance is used for computing the length of the shortest path between

two vertices of a graph.

vertex_distance accepts three arguments, the input graph G(V ; E), a vertex v2Vcalled the

source and a vertex w2Vcalled the target, or a list L⊂Vof target vertices. The command returns

the distance between vand was the number of edges in a shortest path from vto w, or the list

of distances if a list of target vertices is given.

>G:=graph("petersen") // Xcas mode

an undirected unweighted graph with 10 vertices and 15 edges

>vertex_distance(G,1,3)

2

>vertex_distance(G,1,[3,6,9])

[2;1;2]

5.5.2. All-pairs vertex distance

5.5.3. Diameter of a graph

5.5.4. Girth of a graph

The commands girth and odd_girth are used for computing the (odd) girth of an undirected

unweighted graph.

girth resp. odd_girth accepts the input graph G(V ; E)as its only argument and returns the girth

resp. odd girth of G. The (odd) girth of Gis deﬁned to be the length of the shortest (odd) cycle

in G. If there is no (odd) cycle in G, the command returns +1.

The strategy is to apply breadth-ﬁrst search from each vertex of the input graph. The runtime is

therefore O(jVjjEj).

>G:=graph("petersen")

an undirected unweighted graph with 10 vertices and 15 edges

>girth(G)

5.5 Distance 59

5

>G:=hypercube_graph(3)

an undirected unweighted graph with 8 vertices and 12 edges

>G:=subdivide_edges(G,["000","001"])

an undirected unweighted graph with 9 vertices and 13 edges

>girth(G)

4

>odd_girth(G)

5

>G:=complete_binary_tree(2)

an undirected unweighted graph with 7 vertices and 6 edges

>girth(G)

+1

5.6. Acyclic graphs

5.6.1. Checking if a graph is acyclic

The command is_acyclic is used for checking that the given digraph has no directed cycle. A

directed graph with no directed cycle is said to be acyclic.

is_acyclic accepts the input digraph G(V ; E)as its only argument and returns true if Gis

acyclic and false otherwise.

The algorithm attempts to ﬁnd topological order for its vertices. If that succeeds, the graph is

acyclic, otherwise not. The algorithm runs in O(jVj+jEj)time.

>is_acyclic(digraph(trail(1,2,3,4,5)))

true

>is_acyclic(digraph(trail(1,2,3,4,5,2)))

false

5.6.2. Topological sorting

The command topologic_sort or topological_sort is used for ﬁnding a linear ordering of

vertices of an acyclic digraph which is consistent with the arcs of the digraph.

topologic_sort accepts the input graph G(V ; E)as its only argument and returns the list of

vertices of Gin a particular order: a vertex uprecedes a vertex vif u v 2E, i.e. if there is an arc

from uto v.

Note that topological sorting is possible only if the input graph is acyclic. If this condition is not

met, topologic_sort returns an error. Otherwise, it ﬁnds the required ordering by applying

Kahn's algorithm [13], which runs in O(jVj+jEj)time.

>G:=digraph(%{[c,a],[c,b],[c,d],[a,d],[b,d],[a,b]%})

a directed unweighted graph with 4 vertices and 6 arcs

>is_acyclic(G)

60 Graph properties

true

>topologic_sort(G)

[c; a; b; d]

5.6.3. st ordering

The command st_ordering is used for ﬁnding a st-orientation in an undirected biconnected graph

with respect to the given source and sink nodes.

st_ordering accepts three or four arguments: the input graph G(V ; E), a vertex s2Vcalled

the source, a vertex t2Vcalled the target or sink such that st 2Eand optionally an unassigned

identiﬁer D. The command returns the permutation σwhich deﬁnes a particular order of vertices

in V. That ordering deﬁnes the orientation for each edge e2E, which causes Gto become acyclic

with a single source sand sink t. The ordering deﬁned by σis the topological ordering of the

resulting digraph. If the optional argument Dis given, the digraph is stored to it.

The orientation of e=uv 2Eis determined by the ordinals nand mof its endpoints uand v,

respectively, which are assigned by the permutation σ. If n < m, then uis the head and vis the

tail of the corresponding arc, and vice versa otherwise.

Note that the input graph Ghas a st-orientation if and only if Gis biconnected. Furthermore, if

the latter is true, a st-orientation can be computed for any pair s; t 2Vsuch that st 2E.

If the input graph is not biconnected, st_ordering returns an error. Otherwise, it applies the

algorithm of Even and Tarjan [5], which runs in O(jVj+jEj)time, to ﬁnd st-ordering for the

given pair of vertices.

>G:=graph(%{[a,b],[a,c],[a,d],[b,c],[b,d],[c,d]%})

an undirected unweighted graph with 4 vertices and 6 edges

>vertices(G)

[a; b; c; d]

>st_ordering(G,a,d,D)

[0;2;1;3]

>draw_graph(D)

a b

cd

5.7. Vertex matching

5.7.1. Maximum matching

The command maximum_matching is used for ﬁnding maximum matching in undirected graphs.

maximum_matching accepts the input graph G(V ; E)as its only argument and returns a list of

edges e1; e2; :::; em2Esuch that eiand ejare not adjacent (i.e. have no common endpoints) for all

16i < j 6m, under condition that mis maximal. Edges ekfor k= 1; :::; m represent the matched

pairs of vertices in G.

5.7 Vertex matching 61

The command applies Edmonds' blossom algorithm5.1 [4], which ﬁnds maximum matching in

O(jVj2jEj)time.

>G:=graph("octahedron")

an undirected unweighted graph with 6 vertices and 12 edges

>maximum_matching(G)

f[1;3];[6;4];[5;2]g

>G:=graph("soccerball")

an undirected unweighted graph with 60 vertices and 90 edges

>draw_graph(highlight_edges(G,maximum_matching(G)),labels=false)

5.7.2. Maximum matching in bipartite graphs

If the input graph is bipartite, maximum matching can be found much faster by using the

bipartite_matching command which applies the algorithm of Hopcroft and Karp [10].

bipartite_matching accepts an undirected, unweighted bipartite graph Gas its only argument

and returns a sequence containing two elements: the size of the maximum matching and the list

of edges connecting matched pairs of vertices. The algorithm runs in O¡jVj

pjEjtime.

>G:=graph("desargues")

an undirected unweighted graph with 20 vertices and 30 edges

>is_bipartite(G)

true

>n,M:=bipartite_matching(G)

10;f[0;1];[2;3];[4;5];[6;7];[8;9];[10;13];[11;18];[12;15];[14;17];[16;19]g

>draw_graph(highlight_edges(G,M))

5.1. For a good description of the blossom algorithm, see https://en.wikipedia.org/wiki/Blossom_algorithm.

62 Graph properties

5.8. Cliques

5.8.1. Clique graphs

The graph is a clique if it is complete, i.e. if each two of its vertices are adjacent to each other. To

check if a graph is a clique one can use the is_clique command.

is_clique accepts a graph G(V ; E)as its only argument and returns true if Gis a complete

graph; else the returned value is false.

>K5:=complete_graph(5)

an undirected unweighted graph with 5 vertices and 10 edges

>is_clique(K5)

true

>G:=delete_edge(K5,[1,2])

an undirected unweighted graph with 5 vertices and 9 edges

>is_clique(G)

false

5.8.2. Triangle-free graphs

The command is_triangle_free is used for determining is the particular graph triangle-free. A

graph is triangle-free if it contains no clique of cardinality equal to 3, and hence no cliques with

cardinality greater than two.

triangle_free accepts the input graph Gas its only argument and returns true if Gis triangle-

free and false otherwise.

The strategy is to check whether tr (A3) = 0, where Ais the adjacency matrix of G. If the last

equality holds, the graph is triangle-free. This method is very fast as just one matrix multiplication

needs to be carried out completely. Additionally, the matrix Ais sparse, so a large number of

vertices usually does not cause memory problems.

>is_triangle_free(graph("soccerball"))

true

>is_triangle_free(graph("tetrahedron"))

false

5.8.3. Maximal cliques

Each subgraph of a graph G(V ; E)which is itself a complete graph is called a clique in G. A clique

is maximal if it cannot be extended by adding more vertices from Vto it. To count all maximal

cliques in a graph one can use the clique_stats command.

clique_stats accepts Gas the only mandatory argument. If it is the only argument given, the

command returns a list of pairs, each pair consisting of two integers: clique cardinality k(ﬁrst) and

the number nk>0of k-cliques in G(second). Therefore, the sum of second members of all returned

pairs is equal to the total count of all maximal cliques in G. As an optional second argument one

may give a positive integer kor an interval m.. nwith integer bounds. In the ﬁrst case only the

number of k-cliques for the given kis returned; in the second case, only cliques with cardinality

between mand n(inclusive) are counted.

5.8 Cliques 63

The strategy used to ﬁnd all maximal cliques is a variant of the algorithm of Bron and Kerbosch

as described in [20]. Its worst-case running time is O(3jVj/3). However, the performance is usually

almost instantaneous for graphs with 100 vertices or less.

>G:=random_graph(50,0.5)

an undirected unweighted graph with 50 vertices and 588 edges

>clique_stats(G)

0

B

B

B

B

B

B

@

314

4185

5370

6201

747

8 5

1

C

C

C

C

C

C

A

>G:=random_graph(100,0.5)

an undirected unweighted graph with 100 vertices and 2461 edges

>clique_stats(G,5)

3124

>G:=random_graph(500,0.25)

an undirected unweighted graph with 500 vertices and 31257 edges

>clique_stats(G,5..7)

0

@

5153444

618486

7355

1

A1.218 sec

5.8.4. Maximum clique

The largest maximal clique in the graph G(V ; E)is called maximum clique. The command max-

imum_clique can be used to ﬁnd one in the given graph.

maximum_clique accepts the graph Gas its only argument and returns maximum clique in G

as a list of vertices. The clique may subsequently be extracted from Gusing the command

induced_subgraph.

The strategy used to ﬁnd maximum clique is an improved variant of the classical algorithm by

Carraghan and Pardalos developed by Östergård in [15].

In the following examples, the maximum cliques were obtained almost instantly.

>G:=sierpinski_graph(5,5)

an undirected unweighted graph with 3125 vertices and 7810 edges

>maximum_clique(G)

[1560;1561;1562;1563;1564]

>G:=random_graph(300,0.3)

an undirected unweighted graph with 300 vertices and 13380 edges

>maximum_clique(G)

[46;64;144;183;208;241;244;261]

>G:=graph_complement(complete_graph(4,3))

64 Graph properties

an undirected unweighted graph with 7 vertices and 9 edges

>cliq:=maximum_clique(G)

[0;1;2;3]

>draw_graph(highlight_subgraph(G,induced_subgraph(G,cliq)))

5.8.5. Minimum clique cover

The minimum clique cover for the graph G(V ;E)is the smallest set S=fC1; C2; :::; Ckgof cliques in

Gsuch that for every v2Vthere exists i6ksuch that v2Ci. In Giac, such cover can be obtained

by calling the clique_cover command.

clique_cover accepts graph Gas its mandatory argument and returns the smallest possible cover.

Optionally, a positive integer may be passed as the second argument. In that case the requirement

that kis less or equal to the given integer is set. If no such cover is found, clique_cover returns

empty list.

The strategy is to ﬁnd the minimal vertex coloring in the complement Gcof G(note that these

two graphs share the same set of vertices). Each set of equally colored vertices in Gccorresponds

to a clique in G. Therefore, the color classes of Gcmap to the elements C1; :::; Ckof the minimal

clique cover in G.

There is a special case in which Gis triangle-free, which is treated separately. Such a graph G

contains only 1- and 2-cliques; in fact, every clique cover in Gconsists of a matching Mtogether

with the singleton cliques (i.e. the isolated vertices which remain unmatched). The total number

of cliques in the cover is equal to jVj¡jMj, hence to ﬁnd the minimal cover one just needs to ﬁnd

maximum matching in G, which can be done in polynomial time.

>G:=random_graph(30,0.2)

an undirected unweighted graph with 30 vertices and 88 edges

>clique_cover(G)

f[0;2;7];[1;3];[4;10;13;14];[5;6];[8;15;26];[9;22;25];[11;16];[12;17;23];[18;20;24];[19;28];

[21;27;29]g

To ﬁnd minimal clique cover in the truncated icosahedral graph it suﬃces to ﬁnd maximum

matching, since it is triangle-free.

>clique_cover(graph("soccerball"))

f[1;2];[3;16];[4;5];[6;7];[8;49];[9;10];[11;12];[13];[14;15];[17;18];[19;20];[21;22];[23];[24;25];

[26;30];[27;28];[29;48];[31;32];[33;46];[34;35];[36;37];[38;39];[40];[41;42];[43;44];[45;47];

[50];[51;52];[53;54];[55;57];[56;60];[58;59]g

The vertices of Petersen graph can be covered with ﬁve, but not with three cliques.

>clique_cover(graph("petersen"),3)

[]

>clique_cover(graph("petersen"),5)

5.8 Cliques 65

f[0;1];[2;3];[4;9];[5;7];[6;8]g

5.9. Vertex coloring

To color vertices of a graph G(V ; E)means to assign to each vertex v2Va positive integer.

Each integer represents a distinct color. The key property of a graph coloring is that the colors

of adjacent vertices must diﬀer from one another. Two diﬀerent colorings of Gmay use diﬀerent

number of colors.

5.9.1. Greedy coloring

The command greedy_color is used for coloring vertices of a graph in a greedy fashion.

greedy_color accepts one mandatory argument, the input graph G. Optionally, a permutation p

of order jVjmay be passed as the second argument. Vertices are colored one by one in the order

speciﬁed by p(or in the default order if pis not given) such that each vertex gets the smallest

available color. The list of vertex colors is returned in the order of vertices(G).

Generally, diﬀerent choices of permutation pproduce diﬀerent colorings. The total number of

diﬀerent colors may not be the same each time. The complexity of the algorithm is O(jVj+jEj).

>G:=graph("petersen")

an undirected unweighted graph with 10 vertices and 15 edges

>greedy_color(G)

[1;2;1;2;3;2;1;3;3;2]

>L:=greedy_color(G,randperm(10))

[1;2;1;4;3;4;1;3;2;2]

Observe that a diﬀerent number of colors is obtained by executing the last command line. To

display the colored graph, input:

>draw_graph(highlight_vertex(G,vertices(G),L),labels=false)

The ﬁrst six positive integers are always mapped to the standard Xcas colors, as indicated in

Table 5.1. Note that the color 0 (black) and color 7 (white) are swapped; a vertex with color 0 is

uncolored or white, and vertex with color 7 is black. Also note that Xcas will map the numbers

greater than 7 to colors too, but the number of available colors is limited.

5.9.2. Minimal coloring

The vertex coloring of Gis minimal (or optimal) if the smallest possible number of colors is used.

To obtain such a coloring use the command minimal_vertex_coloring.

minimal_vertex_coloring accepts one mandatory argument, the graph G. Optionally, a symbol

sto may be passed as the second argument. The command returns the vertex colors in order of

vertices(G) or, if the second argument is given, stores the colors as vertex attributes and returns

the modiﬁed copy of G.

66 Graph properties

value color

1 red

2 green

3 yellow

4 blue

5 magenta

6 cyan

7 black

Table 5.1. interpretation of abstract vertex/edge colors in Xcas

Giac requires the GLPK library5.2 to solve the minimal vertex coloring problem (MVCP), which is

converted to the equivalent integer linear programming problem and solved by using the branch-

and-bound method with speciﬁc branch/backtrack techniques [3]. Lower and upper bounds for the

number of colors nare obtained by ﬁnding a maximal clique (ncannot be lower than its cardinality)

and by using the heuristic proposed by Brélaz in [1] (which will use at least ncolors), respectively.

The algorithm is usually fast for graphs up to 40 vertices and for sparse graphs in general. For

larger, denser graphs (e.g. with edge density around 0.5, which are the most diﬃcult ones) one may

have to wait for several minutes, even hours, and sometimes for a practically inﬁnite time. Note that

MVCP is a NP-hard problem, which means that no polynomial (i.e. eﬃcient) algorithm is known.

In the following example, the Grotzsch graph is colored with minimal number of colors by ﬁrst

ﬁnding the coloring and then assigning it to the graph by using the highlight_vertex command.

>G:=graph("grotzsch")

an undirected unweighted graph with 11 vertices and 20 edges

>coloring:=minimal_vertex_coloring(G)

[4;2;3;1;1;4;1;3;2;1;2]

>draw_graph(highlight_vertex(G,vertices(G),coloring),labels=false)

To illustrate the combinatorial explosion which characterizes MVCP one can use the following

example. Note that ﬁnding an optimal coloring in Gis equivalent to ﬁnding the minimal clique

cover in its complement Gc.

First, a random graph Gwith 40 vertices and edge density 0.5 is generated. Such a graph is

considered to be relatively small.

>G:=random_graph(40,0.5)

an undirected unweighted graph with 40 vertices and 393 edges

The chromatic number is computed by solving MVCP via minimal_vertex_coloring in less than

a second.

>chromatic_number(G)

8

273 msec

5.2. GNU Linear Programming Kit, https://www.gnu.org/software/glpk/

5.9 Vertex coloring 67

Next, all maximal cliques in Gcare counted using the clique_stats command.

>S:=clique_stats(graph_complement(G))

0

B

B

B

B

@

3 5

466

5238

689

7 3

1

C

C

C

C

A

>n:=sum(col(S,1))

401

To obtain the minimal coloring, a naive algorithm must check if a combination of 2;3; :::; 8maximal

cliques forms a cover in Gc. In the worst case it will check Pk=2

8n

kcombinations, the number

which is computed by the next command line.

>sum(comb(n,k),k=2..8)

15776262844602110

The magnitude of the above result (≈1.6 ×1017) indicates that the algorithm would run practically

forever. (In particular, assuming that the algorithm requires 1µs to test one combination of

cliques, the runtime is about 5070 years.) The fact that chromatic_number required only quarter

of a second to obtain minimal coloring indicates that the implemented algorithm is far more

sophisticated than a simple brute-force approach.

Note that solving MVCP for diﬀerent graphs of exactly the same size (but which do not share the

same edge structure) may take quite diﬀerent time in each instance. For example, the time required

to color a graph with 50 vertices and edge density 0.5 may take any value between six seconds and

six minutes. Also note that some graphs will take exponential time (that is, “forever”) to obtain

the coloring. Table 5.2 shows the runtimes (in seconds) of solving MVCP for random graphs with

10 kvertices and edge density d

10 for k= 1;2; :::; 7and d= 1;2; :::; 5, using Intel i3-7130U processor

at 2.70 GHz. For each pair (k; d), ten graphs were generated and the average runtime was recorded

in the table.

5.9.3. Chromatic number

The command chromatic_number is used for exact computation and approximation of the chro-

matic number of a graph.

chromatic_number accepts one mandatory argument, the input graph G(V ; E), and optionally a

second argument. To obtain only upper and lower bound for the chromatic number (which is much

faster than computing exactly) the option approx or interval should be passed as the second

argument. Alternatively, an unassigned identiﬁer is passed as the second argument; in that case

the corresponding coloring will be stored to it in form of a list of colors of the individual vertices,

ordered as in vertices(G).

The command returns the chromatic number χGof the graph Gin the case of exact computation.

If the option approx or interval is given, an interval lb..ub is returned, where lb is the best

lower bound and ub the best upper bound for χGfound by the algorithm.

The strategy is call minimal_vertex_coloring in the case of exact computation. When approx-

imating the chromatic number, the algorithm will establish the lower bound by searching for

maximum clique. The timeout for this operation is set to 5 seconds as it can be time consuming. If

the maximum clique is not found after that time, the largest clique found is used. Then, an upper

bound is established by by using the heuristic proposed by Brélaz in [1]. Obtaining the bounds

for χGis usually very fast, but the diﬀerence between the bounds grows with jVj.

Unless the input graph is sparse enough, the algorithm slows down considerably for jVj>40.

68 Graph properties

number of vertices edge density

0.1 0.2 0.3 0.4 0.5

10 0.0008892 0.0010818 0.0006116 0.0005825 0.0006331

20 0.0014682 0.00378 0.0038329 0.0077918 0.0067932

30 0.0021163 0.0173315 0.0372468 0.111016 0.143657

40 0.0252134 0.177707 0.626175 1.67746 2.31473

50 0.130089 1.83819 17.3564 120.181 246.161

Table 5.2. average runtime of the algorithm for minimal coloring (in seconds)

>chromatic_number(graph("grotzsch"),cols)

4

>cols

[4;2;3;1;1;4;1;3;2;1;2]

>G:=random_graph(30,0.75)

an undirected unweighted graph with 30 vertices and 313 edges

>chromatic_number(G)

10

>G:=random_graph(300,0.05)

an undirected unweighted graph with 300 vertices and 2196 edges

>chromatic_number(G,approx)

4..7

5.9.4. k-coloring

The command is_vertex_colorable is used for determining whether the vertices of a graph can

be colored with at most kcolors.

is_vertex_colorable accepts two or three arguments: the input graph G(V ; E), a positive integer

kand optionally an unassigned identiﬁer. The command returns true if Gcan be colored using

at most kcolors and false otherwise. If an identiﬁer is given, a coloring using at most kcolors is

stored to it as a list of vertex colors, in the order of vertices(G).

The strategy is to ﬁrst apply a simple greedy coloring procedure which runs in linear time. If

the number of required colors is greater than k, the heuristic proposed by Brélaz in [1] is used,

which runs in quadratic time. If the number of required colors is still larger than k, the algorithm

attempts to ﬁnd the chromatic number χGusing kas the upper bound in the process.

>G:=graph("grotzsch")

an undirected unweighted graph with 11 vertices and 20 edges

>is_vertex_colorable(G,3)

false

>is_vertex_colorable(G,4)

true

>G:=random_graph(70,0.2)

an undirected unweighted graph with 70 vertices and 469 edges

>chromatic_number(G,approx)

5.9 Vertex coloring 69

5..6

>is_vertex_colorable(G,5)

false

818 msec

From the results of the last two command lines it follows that χG= 6. Finding χGby utilizing the

next command line is simpler, but requires much more time.

>chromatic_number(G)

6

92.7 sec

5.10. Edge coloring

70 Graph properties

Chapter 6

Traversing graphs

6.1. Walks and tours

6.1.1. Eulerian graphs

The command is_eulerian is used for determining whether the given graph is an Eulerian graph

and for ﬁnding Eulerian trails in such graphs.

is_eulerian accepts one or two arguments, the input graph G(V ; E)and optionally an unassigned

identiﬁer T, and returns true if Gis Eulerian and false otherwise. If Tis given, the corresponding

Eulerian trail is stored to it.

The graph Gis Eulerian if it has a trail covering all its edges. Such a trail is called Eulerian trail.

An Eulerian trail may be closed, in which case it is called Eulerian cycle. Note that every edge

e2Emust be visited, i.e. “strolled through”, exactly once. However, the edge endpoints (i.e. the

vertices in G) may be visited more than once.

The strategy is to apply Hierholzer's algorithm for ﬁnding an Eulerian path [8]. It works by

covering one cycle at a time in the input graph. The required time is O(jEj).

>is_eulerian(complete_graph(4))

false

>purge(T):; is_eulerian(complete_graph([1,2,3,4,5]),T); T

Done;true;[1;2;3;4;1;5;2;4;5;3;1]

6.1.2. Hamiltonian graphs

6.2. Optimal routing

6.2.1. Shortest paths in unweighted graphs

The command shortest_path is used to ﬁnd the shortest path between two vertices in an undi-

rected unweighted graph.

shortest_path accepts three arguments: a graph G(V ; E), the source vertex s2Vand the target

vertex t2Vor a list Tof target vertices. The shortest path from source to target is returned. If more

targets are speciﬁed, the list of shortest paths from the source to each of these vertices is returned.

The strategy is to run breadth-ﬁrst traversal on the graph Gstarting from the source vertex s.

The complexity of the algorithm is therefore O(jVj+jEj).

>G:=graph("dodecahedron")

an undirected unweighted graph with 20 vertices and 30 edges

>shortest_path(G,1,16)

[1;6;11;16]

71

>paths:=shortest_path(G,1,[16,19])

f[1;6;11;16];[1;5;10;14;19]g

>H:=highlight_trail(G,paths,[red,green])

an undirected unweighted graph with 20 vertices and 30 edges

>draw_graph(H)

1

25

6

3

7

4

89

10

1115

12

13

14

16

17

18

19

20

6.2.2. Cheapest paths in weighted graphs

The command dijkstra is used to ﬁnd the cheapest path between two vertices of an undirected

weighted graph.

dijkstra accepts two or three arguments: a weighted graph G(V ; E)with nonnegative weights, a

vertex s2Vand optionally a vertex t2Vor list Tof vertices in V. It returns the cheapest path

from sto tor, if more target vertices are given, the list of such paths to each target vertex t2T,

computed by Dijkstra's algorithm in O(jVj2)time. If no target vertex is speciﬁed, all vertices in

Vnfsgare assumed to be targets.

A cheapest path from sto tis represented with a list [[v1,v2,...,vk],c] where the ﬁrst element

consists of path vertices with v1=sand vk=t, while the second element cis the weight (cost) of

that path, equal to the sum of weights of its edges.

>

6.2.3. Traveling salesman problem

6.3. Spanning trees

6.3.1. Constructing a spanning tree

The command spanning_tree accepts one or two arguments, an undirected graph Gand optionally

a vertex r2V. It returns the spanning tree Tof Grooted in ror, if none is given, in the ﬁrst

vertex in the list V, obtained by depth-ﬁrst traversal in O(jVj+jEj)time.

6.3.2. Minimal spanning tree

The command minimal_spanning_tree accepts an undirected graph G(V ; E)as its only argument

and returns its minimal spanning tree obtained by Kruskal's algorithm in O(jEjlog jVj)time.

6.3.3. Counting all spanning trees

The command number_of_spanning_trees is used for counting all spanning trees in a graph.

number_of_spanning_trees accepts the input graph G(V ; E)as its only argument and returns

the total number nof mutually diﬀerent spanning trees in G.

72 Traversing graphs

The strategy is based on Theorem 2.2.12 (Matrix Tree Theorem) in [24], page 86. First the adja-

cency matrix Aand the degree sequence δof Gare obtained. Then the matrix B= ∆ ¡Ais

computed, where ∆is the diagonal matrix of order jVjcorresponding to δ. The last row and the

last column of Bare popped out, yielding the matrix Cof order jVj¡1. Now n=det C.

>number_of_spanning_trees(graph("octahedron"))

384

>number_of_spanning_trees(graph("dodecahedron"))

5184000

>number_of_spanning_trees(hypercube_graph(4))

42467328

>number_of_spanning_trees(graph("soccerball"))

375291866372898816000

6.3 Spanning trees 73

Chapter 7

Visualizing graphs

7.1. Drawing graphs by using various methods

To visualize a graph use the draw_graph command. It is capable to produce a drawing of the given

graph using one of the several built-in methods.

7.1.1. Overview

draw_graph accepts one or two arguments, the mandatory ﬁrst one being the graph G(V ; E). This

command assigns 2D or 3D coordinates to each vertex v2Vand produces a visual representation

of Gbased on these coordinates. The second (optional) argument is a sequence of options. Each

option is one of the following:

•labels=true or false: controls the visibility of vertex labels and edge weights (by default

true, i.e. the labels and weights are displayed)

•spring: draw the graph Gusing a multilevel force-directed algorithm

•tree[=r or [r1,r2,...]]: draw the tree or forest G, optionally specifying root nodes for

each tree

•bipartite: draw the bipartite graph Gkeeping the vertex partitions separated

•circle[=L] or convexhull[=L]: draw the graph Gby setting the hull vertices from list

L⊂V(assuming L=Vby default) on the unit circle and all other vertices in origin,

subsequently applying a force-directed vertex placement algorithm to generate the layout

while keeping the hull vertices ﬁxed

•planar or plane: draw the planar graph Gusing a force-directed algorithm

•plot3d: draw the connected graph Gas if the spring option was enabled, but with vertex

positions in 3D instead of 2D

•any unassigned identiﬁer P: when given, the vertex coordinates will be stored to it in form

of a list

The style options spring,tree,circle,planar and plot3d cannot be mixed, i.e. at most one can

be speciﬁed. The option labels may be combined with any of the style options. Note that edge

weights will not be displayed when using plot3d option when drawing a weighted graph.

When no style option is speciﬁed, the algorithm ﬁrst checks if the graph Gis a tree or if it is

bipartite, in which cases it is drawn accordingly. Otherwise, the graph is drawn as if the option

circle was speciﬁed.

Tree, circle and bipartite drawings can be obtained in linear time with a very small overhead,

allowing graphs to be drawn quickly no matter the size. The force-directed algorithms are more

expensive and operating in the time which is quadratic in the number of vertices. Their performance

is, nevertheless, practically instantaneous for graphs with several hundreds of vertices (or less).

7.1.2. Drawing disconnected graphs

When the input graph has two or more connected components, each component is drawn separately

and the drawings are subsequently arranged such that the bounding box of the whole drawing has

the smallest perimeter under condition that as little space as possible is wasted inside the box.

75

For example, the command lines below draw a sparse random planar graph.

>G:=random_planar_graph(100,0.9,0)

an undirected unweighted graph with 100 vertices and 74 edges

>draw_graph(G,planar)

7.1.3. Spring method

When the option spring is speciﬁed, the input graph is drawn using the force-directed algorithm

described in [11] (for an example of such a drawing see Figure 4.1). The idea, originally due

to Fruchterman and Reingold [6], is to simulate physical forces in a spring-electrical model

where the vertices and edges represent equally charged particles and springs connecting them,

respectively.

In a spring-electrical model, each vertex is being repulsed by every other vertex with a force

inversely proportional to the distance between them. At the same time, it is attracted to each of its

neighbors with a force proportional to the square of the distance. Assuming that xvis the vector

representing the position of the vertex v2V, the total force Fvapplied to vis equal to

Fv=X

w2Vnfvg¡C K2

kxv¡xwk2(xv¡xw) + X

w2N(v)

kxv¡xwk

K(xv¡xw);

where N(v)is the set of neighbors of vand C,Kare certain positive real constants (actually, K

may be any positive number, it aﬀects only the scaling of the entire layout). Applying the forces

iteratively and updating vertex positions in each iteration (starting from a random layout) leads the

system to the state of minimal energy. By applying a certain “cooling” scheme to the model which

cuts down the force magnitude in each iteration. the layout “freezes” after a number of iterations

large enough to achieve the minimal energy state.

The force-directed method is computationally expensive and for larger graphs the pleasing layout

cannot be obtained most of the time since the algorithm, starting with a random initial layout,

gets easily “stuck” in the local energy minimum (ideally, the vertex positions should settle in the

global minimal energy constellation). To avoid this a multilevel scheme is applied. The input graph

is iteratively coarsened, either by removing the vertices from a maximal independent vertex set

or contracting the edges of a maximal matching in each iteration. Each coarsening level is then

processed by the force-directed algorithm, starting from the deepest (coarsest) one and lifting the

obtained layout to the ﬁrst upper level, using it as the initial layout for that level. The lifting is

achieved by using the prolongation matrix technique described in [12]. To support drawing of large

graphs (with 1000 vertices or more), the matrices used in the lifting process are stored as sparse

matrices. The multilevel algorithm is signiﬁcantly faster than the original, single-level one and

usually produces better results.

Graph layouts obtained by using force-directed method have a unique property of reﬂecting sym-

metries in the design of the input graph, if any. Thus the drawings become more appealing and

illustrate the certain properties of the input graph better. To make the symmetry more prominent,

the drawing is rotated such that the axis, with respect to which the layout exhibits the largest

symmetry score, becomes vertical. As the symmetry detection is in general very computationally

expensive—up to O(jVj7)when using the symmetry measure of Purchase [23], for example—the

algorithm deals only with the convex hull and the barycenter of the layout, which may not always

be enough to produce the optimal result. Nevertheless, this approach is very fast and seems to

work most of the time for graphs with a high level of symmetry (for example the octahedral graph).

76 Visualizing graphs

For example, the following command lines produce a drawing of the tensor product of two graphs

using the force-directed algorithm.

>G1:=graph(trail(1,2,3,4,5,2))

an undirected unweighted graph with 5 vertices and 5 edges

>G2:=star_graph(3)

an undirected unweighted graph with 4 vertices and 3 edges

>G:=tensor_product(G1,G2)

an undirected unweighted graph with 20 vertices and 30 edges

>draw_graph(G,spring,labels=false)

The following command lines demonstrate drawing of a much larger graph.

>S:=sierpinski_graph(5,4)

an undirected unweighted graph with 1024 vertices and 2046 edges

>draw_graph(S,spring)

Note that vertex labels are automatically suppressed because of the large number of vertices. On

our system, the algorithm took less than 2 seconds to produce the layout.

The spring method is also used for creating 3D graph layouts, which are obtained by passing the

option plot3d to the draw_graph command.

>draw_graph(graph("soccerball"),plot3d,labels=false)

>G1:=graph("icosahedron"):; G2:=graph("dodecahedron"):;

Done;Done

7.1 Drawing graphs by using various methods 77

>G1:=highlight_edges(G1,edges(G1),red)

an undirected unweighted graph with 12 vertices and 30 edges

>G2:=highlight_edges(G2,edges(G2),magenta)

an undirected unweighted graph with 20 vertices and 30 edges

>G:=disjoint_union(G1,G2)

an undirected unweighted graph with 32 vertices and 60 edges

>draw_graph(G,plot3d,labels=false)

y

x

z

7.1.4. Drawing trees

When the tree[=r] option is speciﬁed and the input graph Gis a tree (and r2V), it is drawn using

a fast but simple node positioning algorithm inspired by the well-known algorithm of Walker [22],

using the ﬁrst vertex (or the vertex r) as the root node. When drawing a rooted tree, one usually

requires the following aesthetic properties [2].

A1. The layout displays the hierarchical structure of the tree, i.e. the y-coordinate of a node is

given by its level.

A2. The edges do not cross each other.

A3. The drawing of a sub-tree does not depend on its position in the tree, i.e. isomorphic sub-

trees are drawn identically up to translation.

A4. The order of the children of a node is displayed in the drawing.

A5. The algorithm works symmetrically, i.e. the drawing of the reﬂection of a tree is the reﬂected

drawing of the original tree.

The algorithm implemented in Giac generally satisﬁes all the above properties but A3. Instead,

it tries to spread the inner sub-trees evenly across the available horizontal space. It works by

organizing the structure of the input tree into levels by using depth-ﬁrst search and laying out

each level subsequently, starting from the deepest one and climbing up to the root node. In the

end, another depth-ﬁrst traversal is made, shifting the sub-trees horizontally to avoid intersections

between their edges. The algorithm runs in O(jVj)time and uses the minimum of horizontal space

to draw the tree with respect to the speciﬁed root node r.

For example, the following command line produces the drawing of a random tree on 100 nodes.

>draw_graph(random_tree(100))

78 Visualizing graphs

7.1.5. Drawing planar graphs

The algorithm implemented in Giac which draws planar graphs uses augmentation techniques

to extend the input graph Gto a graph G0, which is homeomorphic to some triconnected graph,

by adding temporary edges. The augmented graph G0is then drawn using Tutte's barycentric

method [21], a force-directed algorithm which puts each vertex in the barycenter of its neighbors.

It is guaranteed that a (non-strict) convex drawing will be produced, without edge crossings. In

the end, the duplicate of the outer face and the temporary edges inserted during the augmentation

stage are removed.

Tutte's algorithm requires that the vertices of the chosen outer face are initially ﬁxed somewhere

the boundary of a convex polygon. In addition, to produce a more ﬂexible layout, the outer face is

duplicated such that the subgraph induced by the vertices on both the outer face and its duplicate

is a prism graph. Then only the duplicates of the outer face vertices are ﬁxed, allowing the outer

face itself to take a more natural shape. The duplicate of the outer face is removed after a layout

is produced.

The augmentation process consists of two parts. Firstly, the input graph Gis decomposed into

biconnected components called blocks using the depth-ﬁrst search (see [7], page 25). Each block is

then decomposed into faces (represented by cycles of vertices) using Demoucron's algorithm (see

[7], page 88, with a correction proposed in [14]). Embeddings obtained for each blocks are then

combined by adding one temporary edge for each articulation point, joining the two corresponding

blocks. Figure 7.1 shows the outer faces of two blocks B1and B2, connected by an articulation

point (cut vertex). The temporary edge (shown in blue) is added to join B1and B2into a single

block. After “folding up” the tree of blocks, the algorithm picks the largest face in the resulting

biconnected graph to be the outer face of the planar embedding.

The second part of the augmentation process consists of recursively decomposing each non-convex

inner face into several convex polygons by adding temporary edges. An inner face f= (v1; :::; vn)

is non-convex if there exist kand lsuch that 16k < l ¡1< n and either vkvl2E, in which case

the edge vkvlis a chord (see Figure 7.2 for an example) or there exists a face g= (w1; w2; :::; vk; :::;

vl; :::; wm¡1; wm)such that the vertices vk+1; :::; vl¡1are not contained in g(see Figure 7.3 for an

example). In Figures 7.1,7.2 and 7.3, the temporary edges added by the algorithm are drawn in

green.

B1

B2

temp. edge

Fig. 7.1. joining two blocks

f

chord

Fig. 7.2. a chorded face

f

g

vl

vk

Fig. 7.3. two adjacent faces

This method of drawing planar graphs operates in O(jVj2)time. Nevertheless, it is quite fast

for graphs up to 1000 vertices, usually producing results in less than a second. The drawback of

this method is that it sometimes creates clusters of vertices which are very close to each other,

resulting in a very high ratio of the area of the largest inner face to the area of the smallest inner

face. However, if the result is not satisfactory, one should simply redraw the graph and repeat the

process until a better layout is found. The planar embedding will in general be diﬀerent each time.

Another drawback of this method is that sparse planar graphs are sometimes drawn poorly.

The following example shows that the above described improvement of the barycentric method

handles non-triconnected graphs well.

7.1 Drawing graphs by using various methods 79

>G:=graph(trail(1,2,3,4,5,6,7,8,9,10,1),trail(11,12,6,11,1,12))

an undirected unweighted graph with 12 vertices and 15 edges

>draw_graph(G,planar)

Note that the inner diamond-like shape in the above drawing would end up ﬂattened—making the

two triangular faces invisible—if the input graph was not augmented. It is so because the vertices

with labels 11 and 12 are “attracted” to each other (namely, the two large faces are “inﬂating”

themselves to become convex), causing them to merge eventually.

In the following example the input graph Gis connected but not biconnected (it has two articu-

lation points). It is obtained by removing a vertex from the Sierpi«ski triangle graph ST3

3. Note

that the syntax mode is set to Xcas in this example, so the ﬁrst vertex label is zero.

>G:=sierpinski_graph(3,3,triangle)

an undirected unweighted graph with 15 vertices and 27 edges

>G:=delete_vertex(G,3)

an undirected unweighted graph with 14 vertices and 23 edges

>draw_graph(G,planar,labels=false)

In the above example, several redraws were required to obtain a good planar embedding.

7.1.6. Circular graph drawings

The drawing method selected by specifying the option circle=L or convexhull=L when calling

draw_graph on a triconnected graph G(V ; E), where L⊂Vis a set of vertices in G, uses the

following strategy. First, positions of the vertices from Lare ﬁxed so that they form a regular

polygon on the unit circle. Other vertices, i.e. all vertices from VnL, are placed in origin. Then

an iterative force-directed algorithm [16], similar to Tutte's barycentric method, is applied to

obtain the ﬁnal layout.

This approach gives best results for symmetrical graphs such as generalized Petersen graphs. In

addition, if the input graph is planar, the drawing will also be planar (there is a possibility, however,

that some very short edges may cross each other as the number of force update iterations is limited).

In the following example the Sierpi«ski graph S4

2is drawn using the above method. Note that the

command lines below are executed in Xcas mode.

>G:=sierpinski_graph(2,4)

an undirected unweighted graph with 16 vertices and 30 edges

>draw_graph(G,circle=[0,1,4,5,7,13,15,14,11,10,8,2])

80 Visualizing graphs

7.2. Custom vertex positions

7.2.1. Setting vertex positions

The command set_vertex_positions is used to assign custom coordinates to vertices of a graph

to be used when drawing the graph.

set_vertex_positions accepts two arguments, the graph G(V ; E)and the list Lof positions to be

assigned to vertices in order of vertices(G). The positions may be complex numbers, lists of coor-

dinates or points (geometrical objects created with the command point). set_vertex_positions

returns the copy G0of Gwith the given layout stored in it.

Any subsequent call to draw_graph with G0as an argument and without specifying the drawing

style will result in displaying vertices at the stored coordinates. However, if a drawing style is

speciﬁed, the stored layout is ignored (although it stays stored in G0).

>G:=digraph([1,2,3,4,5],%{[1,2],[2,3],[3,4],[2,5]%})

a directed unweighted graph with 5 vertices and 4 arcs

>draw_graph(G,circle)

>H:=set_vertex_positions(G,[[0,0],[0.5,0],[1.0,0],[1.5,0],[0.5,1]])

a directed unweighted graph with 5 vertices and 4 arcs

>draw_graph(H)

7.2.2. Generating vertex positions

Vertex positions can be generated for a particular graph Gby using the draw_graph command with

the additional argument Pwhich should be an unassigned identiﬁer. After the layout is obtained,

it will be stored to Pas a list of positions (complex numbers for 2D drawings or points for 3D

drawings) for each vertex in order of vertices(G).

7.2 Custom vertex positions 81

This feature combines well with the set_vertex_positions command, as when one obtains the

desired drawing of the graph Gby calling draw_graph, the layout coordinates can be easily stored

to the graph for future reference. In particular, each subsequent call of draw_graph with Gas an

argument will display the stored layout. The example below illustrates this property by setting a

custom layout to the octahedral graph.

>G:=graph("octahedron")

an undirected unweighted graph with 6 vertices and 12 edges

>draw_graph(G)

>draw_graph(G,P,spring):;

Now Pcontains vertex coordinates, which can be permanently stored to G:

>G:=set_vertex_positions(G,P)

an undirected unweighted graph with 6 vertices and 12 edges

>draw_graph(G)

It should be noted that, after a particular layout is ﬁxed, it stays valid when some edges or vertices

are removed or when an edge is contracted. The stored layout becomes invalid only if a new vertex

is added to the graph (unless its position is speciﬁed by set_vertex_attribute upon the creation)

or if the position attribute of an existing vertex is discarded.

7.3. Highlighting parts of a graph

7.3.1. Highlighting vertices

The command highlight_vertex is used for changing color of one or more vertices in a graph.

highlight_vertex accepts two or three arguments: the graph G(V ; E), a vertex v2Vor a list

L⊂Vof vertices and optionally the new color (or a list of colors) for the selected vertices (the

default color is green). It returns a modiﬁed copy of Gin which the speciﬁed vertices are colored

with the speciﬁed color.

>G:=graph("dodecahedron")

an undirected unweighted graph with 20 vertices and 30 edges

>L:=maximum_independent_set(G)

82 Visualizing graphs

[2;4;6;12;13;10;16;19]

>draw_graph(highlight_vertex(G,L))

7.3.2. Highlighting edges and trails

To highlight an edge or a set of edges in a graph, use the highlight_edges command. If the edges

form a trail, it is usually more convenient to use the highlight_trail command (see below).

highlight_edges accepts two or three arguments: the graph G(V ; E), an edge eor a list of edges

Land optionally the new color (or a list of colors) for the selected edges (the default color is red).

It returns a modiﬁed copy of Gin which the speciﬁed edges are colored with the speciﬁed color.

>M:=maximum_matching(G)

f[1;2];[5;4];[6;11];[3;8];[7;12];[9;13];[10;15];[14;19];[16;17]g

>draw_graph(highlight_edges(G,M))

>S:=spanning_tree(G)

an undirected unweighted graph with 20 vertices and 19 edges

>draw_graph(highlight_edges(G,edges(S),magenta))

highlight_trail accepts two or three arguments: the input graph G(V ; E), a list L⊂Vor a

list [L1,L2,...,Lk] of such lists (each list represents the vertices of the corresponding trail) and

optionally a positive integer cor a list of positive integers [c1,c2,...,ck]. The command returns

the copy of Gin which edges between consecutive vertices in Lare highlighted with color c(by

default red) or the trail represented by Liis highlighted with color cifor i= 1;2; :::; k.

Note that a trail can cross itself, which means that the elements of Lare not required to be unique.

>draw_graph(highlight_trail(G,[6,15,20,19,18,17,16,11,7,2,3,8,13,9,14,10]))

7.3 Highlighting parts of a graph 83

1

25

6

3

7

4

89

10

1115

12

13

14

16

17

18

19

20

7.3.3. Highlighting subgraphs

The command highlight_subgraph is used for highlighting subgraph(s) of the given graph.

highlight_subgraph accepts two or four arguments: the graph G(V ; E), a subgraph Sof G

or a list of subgraphs of Gand optionally the new colors for edges and vertices of the selected

subgraph(s), respectively. It returns a modiﬁed copy of Gwith the selected subgraph(s) colored

as speciﬁed.

>G:=graph(%{[1,2],[2,3],[3,1],[3,4],[4,5],[5,6],[6,4]%})

an undirected unweighted graph with 6 vertices and 7 edges

>A:=articulation_points(G)

[3;4]

>B:=biconnected_components(G)

[[4;6;5];[3;4];[1;3;2]]

>H:=highlight_vertex(G,A,magenta)

an undirected unweighted graph with 6 vertices and 7 edges

>draw_graph(H)

>S:=induced_subgraph(G,B[0])

an undirected unweighted graph with 3 vertices and 3 edges

>H:=highlight_subgraph(G,S)

an undirected unweighted graph with 6 vertices and 7 edges

>draw_graph(H,spring)

84 Visualizing graphs

Bibliography

[1] Daniel Brélaz. New Methods to Color the Vertices of a Graph. Communications of the ACM, 22:251–256, 1979.

[2] Cristoph Buchheim, Michael Jünger, and Sebastian Leipert. Improving Walker's Algorithm to Run in Linear

Time. In M. T. Goodrich and S. G. Kobourov, editors, Graph Drawing 2002, Lecture Notes in Computer

Science vol 2528, pages 344–353. Springer-Verlag Berlin Heidelberg, 2002.

[3] Isabel M. Díaz and Paula Zabala. A Branch-and-Cut Algorithm for Graph Coloring. Discrete Applied Math-

ematics, 154:826–847, 2006.

[4] Jack Edmonds. Paths, Trees, and Flowers. In Gessel I. and GC. Rota, editors, Classic Papers in Combinatorics,

pages 361–379. Birkhäuser Boston, 2009. Modern Birkhäuser Classics.

[5] Shimon Even and Robert E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2:339–344,

1976.

[6] T. M. J. Fruchterman and E. M. Reingold. Graph Drawing by Force-Directed Placement. Software: Practice

and Experience, 21:1129–1164, 1991.

[7] Alan Gibbons. Algorithmic graph theory. Cambridge University Press, 1985.

[8] Carl Hierholzer. Ueber die möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu

umfahren. Mathematische Annalen, 6:30–32, 1873.

[9] Andreas M. Hinz, Sandi Klavºar, and Sara S. Zemlji£. A survey and classiﬁcation of Sierpi«ski-type graphs.

Discrete Applied Mathematics, 217:565–600, 2017.

[10] John E. Hopcroft and Richard M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs.

SIAM Journal on Computing, 2:225–231, 1973.

[11] Yifan Hu. Eﬃcient and High Quality Force-Directed Graph Drawing. Mathematica Journal, 10:37–71, 2005.

[12] Yifan Hu and Jennifer Scott. A Multilevel Algorithm for Wavefront Reduction. SIAM Journal on Scientiﬁc

Computing, 23:1352–1375, 2001.

[13] Arthur B. Kahn. Topological sorting of large networks. Communications of the ACM, 5:558–562, 1962.

[14] Wendy Myrwold and Willian Kocay. Errors in graph embedding algorithms. Journal of Computer and System

Sciences, 77:430–438, 2011.

[15] Patric R. J. Östergård. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics,

120:197–207, 2002.

[16] Bor Plestenjak. An Algorithm for Drawing Planar Graphs. Software: Practice and Experience, 29:973–984,

1999.

[17] Angelika Steger and Nicholas C. Wormald. Generating random regular graphs quickly. Combinatorics Prob-

ability and Computing, 8:377–396, 1999.

[18] Robert E. Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1:146–160,

1972.

[19] Robert E. Tarjan. Applications of path compression on balanced trees. Journal of the ACM, 26:690–715, 1979.

[20] Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all

maximal cliques and computational experiments. Theoretical Computer Science, 363:28–42, 2006.

[21] W. T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, s3-13:743–767, 1963.

[22] John Q. Walker II. A nodepositioning algorithm for general trees. Software: Practice and Experience,

20:685–705, 1990.

[23] E. Welch and S. Kobourov. Measuring Symmetry in Drawings of Graphs. Computer Graphics Forum,

36:341–351, 2017.

[24] Douglas B. West. Introduction to Graph Theory. Pearson Education, 2002.

85

Command Index

antiprism_graph .................. 18

complete_binary_tree ............... 14

complete_graph .................. 13

complete_kary_tree . . . . . . . . . . . . . . . . 14

cycle_graph .................... 12

digraph ....................... 10

graph ......................... 9

grid_graph ..................... 18

hypercube_graph .................. 16

interval_graph .................. 15

is_graphic_sequence ............... 15

kneser_graph .................... 15

lcf_graph ..................... 21

odd_graph ..................... 15

path_graph ..................... 13

petersen_graph . . . . . . . . . . . . . . . . . . 20

prism_graph .................... 18

sequence_graph . . . . . . . . . . . . . . . . . . 15

sierpinski_graph ................. 20

star_graph ..................... 17

torus_grid_graph ................. 18

trail ........................ 13

web_graph ..................... 17

wheel_graph .................... 17

87