Invariants and Operations - GraphFilter/GraphFilter GitHub Wiki
Invariants are graph properties that depends only on the abstract structure, not on particular labeling or drawings of the graph. Examples include the number of vertices and the number of edges. Here we list all the graph operations and invariants already inserted in the project, with the respective library used for implementation.
They can be used in the writing of (in)equations or after filtering, to study the output graphs.
Chromatic number (χ) | Matching number (ν) | Radius (r) | |||
Number of vertices (n) | Number of components (w) | Vertex connectivity (ϰ) | |||
Number of edges (Е) | Degree regularity (dᵣ) | Edge connectivity (λ) | |||
Clique number (ω) | Maximum degree (Δ) | Minimum edge cover number (mec) | |||
Independence number (⍺) | Minimum degree (ẟ) | Number of triangles (Τ) | |||
Total domination number (Ɣₜ) | Average degree (dₐ) | Wiener Index (W) | |||
Domination number (Ɣ) | Vertex cover number (τ) | Number of Spanning trees (ʈ) | |||
Girth (ɡ) | Diameter (diam) | Density (Ɗ) |
Spectral | ||
---|---|---|
Largest M-eigenvalue M=A, L, Q, N, S, D, DL, DQ, E |
2th Largest M-eigenvalue M=A, L, Q, N, S, D, DL, DQ, E |
Smallest M-Eigenvalue M=A, Q, N, S, D, DL, DQ, E |
M-Energy M=A, L, Q, N, S, D, DL, DQ, E |
Algebraic connectivity (ac) | Estrada Index (EE) |
Nullity (η) | Number main M-eigenvalue M=A, D, Q, S |
Rank M- matrix M=A, L, Q, D, N |
Determinant M M=A, L, Q, N, S, D, DL, DQ, E |
The definition of M matrices can be found in Dictionary Matrix M.
To build the in(equations) the user can calculate the numeric invariants not only in the graph, but can also use the line graph and complement
They can be used in the conditions or after filtering, to study the output graphs.
Structural | |||
---|---|---|---|
Planar | Regular | Connected | Triangle-free |
Biconnected | Tree | Bipartite | Bull-free |
Self-complementary | Eulerian | Regular Transmission | Claw-free |
Chordal | Has bridge | Is threshold | Cubic |
Spectral * | |
---|---|
Some M-eigenvalue integer M=A, L, Q, S, N, D, DL or DQ |
M-integral M=A, L, Q, N, S, D, DL, DQ, E |
Largest M-eigenvalue is integer M=A, L, Q, N, S, D, DL, DQ, E |
Matrix M is invertible M=A, L, Q, N, S, D, E |
They are invariants that are neither numeric nor boolean, but can be used to study the graphs returned in the filtering.
Structural | |
---|---|
Dominating Set | Eigenvector Centrality |
Maximum Clique | Closeness Centrality |
Minimum edge cover (set) | Betweeness Centrality |
Maximum Matching Set | Harmonic Centrality |
Maximum Independent Set | Transmission |
Spectral * | |
---|---|
Spectrum M M= A, L, Q, N, D, S, DL, DQ, E |
M-Matrix M= A, I, L, Q, N, D, S, DL, DQ, E |
Eigenvectors M= A, L, Q, N, D, S, DL, DQ, E |
You can also use several usual functions in mathematics:
Trigonometric | Basic | Functions | Utils | Logic | Constants | Symbols |
---|---|---|---|---|---|---|
Sine | Sum | Natural Logarithm | Floor | AND | PI | Equal |
Cosine | Subtraction | Logarithm | Ceiling | OR | Different | |
Tangent | Division | Square Root | Modulus | Less Than | ||
Product | Modulus | Greater Than | ||||
Power | Less or Equal Than | |||||
Greater or Equal Than |
These are basic operations that are applied to a single graph and return another graph.
Graph Operations | |
---|---|
Complementary Graph | Line Graph |
Clique Maximal | Graph |
- A: Adjacency
- L: Laplacian
- Q: Signless Laplacian
- N: Normalized Laplacian
- D: Distance
- DL: Distance Laplacian
- DQ: Distance Signless Laplacian
- S: Seidel
- E: Eccentricity
The definitions is available on Dictionary Matrix M.