English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

It is confirmed in this work that the graph isomorphism can be tested inpolynomial time, which resolves a longstanding problem in the theory ofcomputation. The contributions are in three phases as follows. 1. A descriptiongraph $\tilde{A}$ to a given graph $A$ is introduced so that labels to verticesand edges of $\tilde{A}$ indicate the identical or different amounts of walksof any sort in any length between vertices in $A$. Three processes are thendeveloped to obtain description graphs. They reveal relations among matrixpower, spectral decomposition and adjoint matrices, which is of independentinterest. 2. We show that the stabilization of description graphs can beimplemented via matrix-power stabilization, a new approach to distinguishvertices and edges to graphs. The approach is proven to be equivalent in thepartition of vertices to Weisfeiler-Lehman (WL for short) process. The specificSquare-and-Substitution (SaS) process is more succinct than WL process. Thevertex partitions to our stable graphs are proven to be \emph{strongly}equitable partitions, which is important in the proofs of our main conclusion.Some properties on stable graphs are also explored. 3. A class of graphs namedbinding graphs is proposed and proven to be graph-isomorphism complete. Thevertex partition to the stable graph of a binding graph is the automorphismpartition, which allows us to confirm graph-isomorphism problem is incomplexity class $\mathtt{P}$. Since the binding graph to a graph is so simplein construction, our approach can be readily applied in practice. Some examplesare supplied as illustrations to the contexts, and a brief suggestion toimplementation of SaS process is also given in the appendix.

Description Graphs, Matrix-Power Stabilizations and Graph Isomorphism in Polynomial Time