Fractional graph isomorphism

In graph theory, a fractional isomorphism of graphs whose adjacency matrices are denoted A and B is a doubly stochastic matrix D such that DA = BD. If the doubly stochastic matrix is a permutation matrix, then it constitutes a graph isomorphism.

Computational complexity

Whereas the graph isomorphism problem is not known to be decidable in polynomial time and not known to be NP-complete, the fractional graph isomorphism problem is decidable in polynomial time because it is a special case of the linear programming problem, for which there is an efficient solution.

Equivalence to coarsest equitable partition

Two graphs are also fractionally isomorphic if they have a common coarsest equitable partition. A partition of a graph is a collection of pairwise disjoint sets of vertices whose union is the vertex set of the graph. A partition is equitable if for any pair of vertices u and v in the same block of the partition and any block B of the partition, both u and v have the same number of neighbors in B. An equitable partition P is coarsest if each block in any other equitable partition is a subset of a block in P. Two coarsest equitable partitions P and Q are common if there is a bijection f from the blocks of P to the blocks of Q such for any blocks B and C in P, the number of neighbors in C of any vertex in B equals the number of neighbors in f(C) of any vertex in f(B).

See also

• Graph isomorphism

References

• Scheinerman, Edward; Ullman, Daniel (December 20, 2013). Fractional Graph Theory. Dover Publications. ISBN 978-0486485935.