# Graph -- a class for graphs

## Description

This class represents simple graphs. This class extends HyperGraph and hence inherits all HyperGraph methods.

 i1 : R = QQ[w,x,y,z]; i2 : G = graph(R, {{w,x},{w,y},{w,z},{y,z}}); i3 : vertices G o3 = {w, x, y, z} o3 : List i4 : edges G o4 = {{w, x}, {w, y}, {w, z}, {y, z}} o4 : List i5 : ring G o5 = R o5 : PolynomialRing

Like hypergraphs, graphs are associated with a polynomial ring whose variables are the vertices of the graph. Isolated vertices should not appear in the edge list. As a consequence, the edgeIdeal of a graph is always generated by quadratics. The fact that isolated vertices are not edges in a graph affects the output of the methods connectedComponents, numConnectedComponents, and isConnected. One can use connectedGraphComponents, numConnectedGraphComponents, and isConnectedGraph to ensure that each isolated vertex is counted as a separate connected component.

## Functions and methods returning a graph :

• antiCycle -- returns a graph of an anticycle
• "antiCycle(List)" -- see antiCycle -- returns a graph of an anticycle
• "antiCycle(Ring)" -- see antiCycle -- returns a graph of an anticycle
• "antiCycle(Ring,ZZ)" -- see antiCycle -- returns a graph of an anticycle
• "completeGraph(List)" -- see completeGraph -- returns a complete graph
• "completeGraph(Ring)" -- see completeGraph -- returns a complete graph
• "completeGraph(Ring,ZZ)" -- see completeGraph -- returns a complete graph
• "completeMultiPartite(Ring,List)" -- see completeMultiPartite -- returns a complete multipartite graph
• "completeMultiPartite(Ring,ZZ,ZZ)" -- see completeMultiPartite -- returns a complete multipartite graph
• cycle -- returns a graph cycle
• "cycle(List)" -- see cycle -- returns a graph cycle
• "cycle(Ring)" -- see cycle -- returns a graph cycle
• "cycle(Ring,ZZ)" -- see cycle -- returns a graph cycle
• graph -- constructor for Graph
• "graph(HyperGraph)" -- see graph -- constructor for Graph
• "graph(Ideal)" -- see graph -- constructor for Graph
• "graph(List)" -- see graph -- constructor for Graph
• "graph(MonomialIdeal)" -- see graph -- constructor for Graph
• "graph(PolynomialRing,List)" -- see graph -- constructor for Graph

## Methods that use a graph :

• "allEvenHoles(Graph)" -- see allEvenHoles -- returns all even holes in a graph
• "allOddHoles(Graph)" -- see allOddHoles -- returns all odd holes in a graph
• "cliqueComplex(Graph)" -- see cliqueComplex -- returns the clique complex of a graph
• "cliqueNumber(Graph)" -- see cliqueNumber -- computes the clique number of a graph
• "complementGraph(Graph)" -- see complementGraph -- returns the complement of a graph or hypergraph
• "getCliques(Graph)" -- see getCliques -- returns cliques in a graph
• "getCliques(Graph,ZZ)" -- see getCliques -- returns cliques in a graph
• "getMaxCliques(Graph)" -- see getMaxCliques -- returns maximal cliques in a graph
• "hasOddHole(Graph)" -- see hasOddHole -- tells whether a graph contains an odd hole
• "hyperGraph(Graph)" -- see hyperGraph -- constructor for HyperGraph
• "independenceNumber(Graph)" -- see independenceNumber -- determines the independence number of a graph
• "inducedGraph(Graph,List)" -- see inducedGraph -- returns the induced subgraph of a graph
• "isBipartite(Graph)" -- see isBipartite -- determines if a graph is bipartite
• "isChordal(Graph)" -- see isChordal -- determines if a graph is chordal
• "isForest(Graph)" -- see isForest -- determines whether a (hyper)graph is a forest
• "isLeaf(Graph,ZZ)" -- see isLeaf -- determines if an edge (or vertex) is a leaf of a (hyper)graph
• "isPerfect(Graph)" -- see isPerfect -- determines whether a graph is perfect
• "numTriangles(Graph)" -- see numTriangles -- returns the number of triangles in a graph
• "smallestCycleSize(Graph)" -- see smallestCycleSize -- returns the size of the smallest induced cycle of a graph
• "spanningTree(Graph)" -- see spanningTree -- returns a spanning tree of a graph

## For the programmer

The object Graph is a type, with ancestor classes HyperGraph < HashTable < Thing.