Square-Free Graph

A square-free graph is a graph containing no graph cycles of length four. A simple graph is square-free iff

where is the adjacency matrix of the graph, is the matrix trace, is the number of edges of the graph, and denotes the element of .

The numbers of square-free simple graphs on , 2, 3, ... nodes are 1, 2, 4, 8, 18, 44, 117, 351, ... (OEIS A006786), the first few of which are illustrated above.

The numbers of square-free simple connected graphs on , 2, 3, ... nodes are 1, 1, 2, 3, 8, 19, 57, ... (OEIS A077269), the first few of which are illustrated above.

Graphs with girth are automatically square-free, while square-free graphs with girth 3 are rarer.

Wolfram Web Resources