Use the <i>K</i>-Neighborhood Subgraphs to Compute Canonical Labelings of Graphs

Abstract

This paper puts forward an innovative theory and method to calculate the canonical labelings of graphs that are distinct to N a u t y ’s. It shows the correlation between the canonical labeling of a graph and the canonical labeling of its complement graph. It regularly examines the link between computing the canonical labeling of a graph and the canonical labeling of its o p e n k- n e i g h b o r h o o d s u b g r a p h . It defines d i f f u s i o n d e g r e e s e q u e n c e s and e n t i r e d i f f u s i o n d e g r e e s e q u e n c e . For each node of a graph G, it designs a characteristic m _ N e a r e s t N o d e to improve the precision for calculating canonical labeling. Two theorems established here display how to compute the first nodes of M a x Q ( G ) . Another theorem presents how to determine the second nodes of M a x Q ( G ) . When computing C m a x ( G ) , if M a x Q ( G ) already holds the first i nodes u 1 , u 2 , ⋯ , u i , Diffusion and Nearest Node theorems provide skill on how to pick the succeeding node of M a x Q ( G ) . Further, it also establishes two theorems to determine the C m a x ( G ) of disconnected graphs. Four algorithms implemented here demonstrate how to compute M a x Q ( G ) of a graph. From the results of the software experiment, the accuracy of our algorithms is preliminarily confirmed. Our method can be employed to mine the frequent subgraph. We also conjecture that if there is a node v ∈ S ( G ) meeting conditions C m a x ( G − v ) ⩽ C m a x ( G − w ) for each w ∈ S ( G ) ∧ w ≠ v , then u 1 = v for M a x Q ( G ) .

Keywords

• canonical labeling
• open k-neighborhood subgraph
• algorithm
• adjacency matrix
• diffusion degree sequence
• entire diffusion degree sequences