Tyshkevich Decomposition Toolkit - About

Overview

This toolkit provides a comprehensive suite for working with Tyshkevich decomposition and unigraph composition. Tyshkevich decomposition is a method for decomposing a graph into indecomposable components. Unigraph composition is a method for composing two or more graphs into a single graph.

We recommend reading the accompanying paper before interacting with this tool to fully understand the underlying concepts and algorithms. The paper is available at add paper link here.

Available Tools

1. Compose Graphs

Compose two graphs by their degree sequences. The second graph must be a split graph. Enter degree sequences in the format: degree^count (e.g., "5^2, 4^3, 1^1" represents 2 vertices of degree 5, 3 vertices of degree 4, and 1 vertex of degree 1). The composition operation is described in the key concepts section.

2. Compose Unigraphs

Compute the composition of two unigraphs. Configure two graphs using various graph types (C₅, mK₂, U2, U3, split graphs, etc.) and their parameters, then compute their composition. You can also apply transformations (inverse, complement, complement of inverse) to each graph before composing them. The composition operation is described in the key concepts section.

3. Random Unigraph Generator

Generate random unigraphs with specified properties. Choose the number of vertices and the number of basic components, and the tool will generate random unigraph components and compose them into a final result. The composition operation is described in the key concepts section.

4. Graph Decomposition and Unigraph Detection Tool

Decompose a graph (provided as a degree sequence) into its basic components. The tool will determine if the graph is a unigraph and show the full decomposition into components. The decomposition operation is described in the key concepts section.

5. Distinguishing Number and Fixing Number

Similar to the decomposition tool, but also computes the distinguishing number and fixing number for the graph. The tool provides the compacted version of the decomposition and the distinguishing number and fixing number of each component. The decomposition operation is described in the key concepts section.

6. Clique size, independence number, vertex cover number and chromatic number

Decompose a graph (provided as a degree sequence) into its basic components and compute fundamental graph properties: clique size, independence number, vertex cover number, and chromatic number. The tool determines if the graph is a unigraph and calculates these key structural characteristics. The decomposition operation is described in the key concepts section.

Key Concepts

Degree Sequence: The vertex degrees of a graph listed in decreasing order.
Graph Composition: The operation of combining two graphs into a single graph via adding edges between every vertex in G0 and partition A (the clique) in G1.
Graph Decomposition: The operation of converting a graph into its indecomposable components by reversing the graph composition operation.
Unigraph: A graph that is completely determined by its degree sequence.
Split Graph: A graph whose vertices can be partitioned into two sets so that one induces a clique while the other induces an stable or independent set. If we want to specify the partition, we write it as (G,A,B) where A is the set that induces a clique and B is the set that induces a stable set.
Clique size: The size of a largest clique in the graph.
Independence number: The size of a largest stable set in the graph.
Vertex cover number: The minimum number of vertices needed to cover all the edges of the graph.
Chromatic number: The minimum number of colors needed for a proper vertex coloring of the graph.
Distinguishing Number: The minimum number of colors needed to color the vertices of the graph such that only the trivial automorphism preserves the coloring.
Fixing Number: The minimum size of a set of vertices so that the trivial automorphism is the only automorphism that fixes every element in the set is the trivial automorphism.

Getting Started

Choose a tool from the tabs above to begin working with unigraphs. Each tool provides interactive controls and displays results in real-time.