Use the K -Neighborhood Subgraphs to Compute Canonical Labelings of Graphs

Jianqiang Hao, Yunzhan Gong, Jianzhi Sun and Li Tan
Additional contact information
Jianqiang Hao: Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, No. 11, Fu Cheng Road, Beijing 100048, China
Yunzhan Gong: State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, No 10, Xitucheng Road, Haidian District, Beijing 100876, China
Jianzhi Sun: Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, No. 11, Fu Cheng Road, Beijing 100048, China
Li Tan: Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, No. 11, Fu Cheng Road, Beijing 100048, China

Mathematics, 2019, vol. 7, issue 8, 1-35

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 (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/8/690/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/8/690/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:8:p:690-:d:253870

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().